• Home
  • Subscribe
  • Contribute Us
    • Share Your Interview Experience
  • Contact Us
  • About
    • About CSEstack
    • Campus Ambassador
  • Forum & Discus
  • Tools for Geek
  • LeaderBoard
CSEstack

What do you want to Learn Today?

  • Programming
    • Tutorial- C/C++
    • Tutorial- Django
    • Tutorial- Git
    • Tutorial- HTML & CSS
    • Tutorial- Java
    • Tutorial- MySQL
    • Tutorial- Python
    • Competitive Coding Challenges
  • CSE Subject
    • (CD) Compiler Design
    • (CN) Computer Network
    • (COA) Computer Organization & Architecture
    • (DBMS) Database Management System
    • (DS) Data Structure
    • (OS) Operating System
    • (ToA) Theory of Automata
    • (WT) Web Technology
  • Interview Questions
    • Interview Questions- Company Wise
    • Interview Questions- Coding Round
    • Interview Questions- Python
    • Interview Questions- REST API
    • Interview Questions- Web Scraping
    • Interview Questions- HR Round
    • Aptitude Preparation Guide
  • GATE 2022
  • Linux
  • Trend
    • Full Stack Development
    • Artificial Intelligence (AI)
    • BigData
    • Cloud Computing
    • Machine Learning (ML)
  • Write for Us
    • Submit Article
    • Submit Source Code or Program
    • Share Your Interview Experience
  • Tools
    • IDE
    • CV Builder
    • Other Tools …
  • Jobs

Find an Index of Array Such that Sum of Left and Right Subarray is Equal

Aniruddha Chaudhari/9396/0
CodePython

This is one of the questions that was asked in the competitive coding round for Morgan Stanley.

Problem statement:

You have given an array (list in the case of Python). Find the index of the element in the array such that the sum of all the elements left to the index is equal to the sum of all the elements right to the index.

This question can also be asked as

Split the array into equal sum subarrays.

Example:

Input (given array list):
[2, 4, 5, 1, 2, 3]

Output:
2

Explanation:
The left and right sub array for the index "2" is [2, 4] and [1, 2, 3]. The sum of both the sub array is 6. 

There are multiple ways to find the index of the array such that the sum of the left and right subarray is equal.

Method 1

Algorithm

  • Traverse each element in the list.
  • Check the sum of the left and right sub-array.
  • If the sum of the left and right sub-array is the same, print the index.

This is not an efficient solution. Traversing each element in the list will take O(n) time. And find the sum of the subarray for each index will take O(n) time. So the total complexity of this algorithm is O(n^2).

When I was solving this question on the HackerRank coding round of Morgan Stanley, some of the test cases were failing as it was taking more time.

Can we solve it in a more efficient way or in O(n) time?

Yes, you can.

Method 2

Suppose, the given array is [2, 4, 5, 1, 2, 3]

Algorithm

  • Traverse the array from the left and calculate the cumulative sum of each element. New array formed: [2, 6, 11, 12, 14, 17] (says array “sum_letf”).
  • Here, the last element in the new array is nothing but the sum of the given array.
  • Take a sum as the first element in the new array. At each element, subtract the element value from the previously calculated value. New array formed: [17, 15, 11, 6, 5, 3] (says array “sum_right”)
  • Now compare the two new arrays and find the first matching element. Here matching element is 11 at the index of 2

Python Program

As the second method is efficient we are going to write a Python program for it.

Prerequisite:

  • Python List Tutorial which includes iterating over each element in the list and append() new element.
sample = [2, 4, 5, 1, 2, 3]
 
sum = 0
 
sum_left=[]
for val in sample:
    sum += val
    sum_left.append(sum)
     
sum_right=[]
for val in sample:
    sum_right.append(sum)
    sum -= val

for i in range(len(sum_left)):
    if sum_left[i] == sum_right[i]:
        print(f"Matching index is {i}.")
        break

Output:

Matching index is 2.

Complexity

To calculate the “sum_left” and “sum_right” array it takes O(n) time each. To find the matching element in the new arrays, it takes O(n) time. The total complexity of this algorithm is O(n)+O(n)+O(n) which is equivalent of O(n).

This is more efficient than the first method considering time complexity.

The only drawback of this implementation is extra space. We have created additional two arrays of size ‘n’.

Is there a scope to improve it?

Yes. Let’s check the next method.

Method 3

In an earlier method, we were doing three things (calculating the left sum array, calculating the right sum array, and then finding the matching element) one after another.

We can club all these three operations inside the single while loop.

Java Code

public class SplitArray { 
  static int findPivot(int[] arr) {
    int l=0;
    int r=arr.length-1;
    int lsum=arr[l];
    int rsum=arr[r];
 
    while(l<r) {
      if(lsum==rsum && l+2==r)
        return l+1;
      if(lsum<rsum)
        lsum+=arr[++l];
      else
        rsum+=arr[--r];
    }
 
    return -1;  
  }
     
  //main function
  public static void main(String args[]) 
  { 
    int arr[] = {2, 4, 5, 1, 2, 3}; 
    int size = arr.length;
    System.out.println(findPivot(arr)); 
  } 
} 

Output:

2

This code is shared by Harshit Garg.

Python Code

def findPivot(arr):
  l=0
  r=len(arr)-1
  lsum=arr[l]
  rsum=arr[r]

  while l<r:
    if lsum==rsum and l+2==r:
      return l+1
    elif lsum<rsum:
      l += 1
      lsum+=arr[l]
    else:
      r -= 1
      rsum+=arr[r]

  return -1
 
print(findPivot([2, 4, 5, 1, 2, 3]))

Output:

2

Complexity

This is the most efficient method considering both time and space complexity. The time complexity is O(n). And the space complexity is O(1) (constant time) as don’t require any extra space.

Check other competitive coding questions asked in product-based companies.

Understand the logic here to find the index of array such that sum of left and right subarray is equal. You can implement the same code in any other programming language such as C/C++ and Java.

Python Interview Questions eBook

coding challengePython
Aniruddha Chaudhari
I am complete Python Nut, love Linux and vim as an editor. I hold a Master of Computer Science from NIT Trichy. I dabble in C/C++, Java too. I keep sharing my coding knowledge and my own experience on CSEstack.org portal.

Your name can also be listed here. Got a tip? Submit it here to become an CSEstack author.

Leave a Reply Cancel reply

Why?

Why Competitive Programming Important?

Coding Challenges for Practice

  1. Count Common Factor
  2. Does it Divide
  3. Sum of Sub Arrays
  4. Pair of Desired Sum
  5. Remove Duplicate Char from String
  6. Sort String by Char Freq (Python)
  7. Sort String by Char Freq (Java)
  8. Split Array into Equal Sum Subarray
  9. Validate IP Address
  10. Validate PAN Card Number
  11. Validate Sudoku
  12. Sort Circular Rotated Array
  13. String Permutations
  14. Min Arrow to Burst Bubbles
  15. Min Cost to Paint All Houses [Amazon]
  16. HourGlass with Max Sum
  17. Max Profit by Buying/Selling Stocks
  18. Hailstone Sequence
  19. Reverse String without affecting Special Characters
  20. Secure Conversation by Encry/Decry
  21. Special Elements in Matrix
  22. Next Greater No with Same set of Digits
  23. Smallest Subarray with Sum Greater than Given Number
  24. Group Anagrams
  25. Find Duplicates in Array in O(n)
  26. Find Two Unique Numbers from Array in O(n)
  27. Number Patterns & Finding Smallest Number
  28. First Unique Element in a Stream
  29. Flip Equivalent Binary Trees [TeachMint]
  30. Minimum Cost of Merging Files [Amazon]
  31. Minimum Distance for Truck to Deliver Order [Amazon]
  32. Longest Sequence of URLs
  33. Order Task for Given Dependencies
  34. Design Music Player
  35. Multilevel Parking System Design
  36. Minimum Coins Required
  37. Max Sum Subarray
  38. Max Avg Sum of Two Subsequences
  39. Merge Overlapping Intervals
  40. Longest Balanced Substring
  41. Longest Path in a Weighted Tree
  42. Generate Balanced Parentheses
  43. PostOrder Traversal Without Recursion

© 2022 – CSEstack.org. All Rights Reserved.

  • Home
  • Subscribe
  • Contribute Us
    • Share Your Interview Experience
  • Contact Us
  • About
    • About CSEstack
    • Campus Ambassador
  • Forum & Discus
  • Tools for Geek
  • LeaderBoard