Program to find an element in array such that sum of left array is equal to sum of right array

An algorithm to find the element in array such that the sum of its left elements is equal to the sum of its right elements in javascript.

Example

Input:
[2, 1, 9 ,3]
[1, 2, 3]

Output:
9
-1

Element on the left (2+1) subarray and right (3) subarray of 9 are equal.

We are going to see three different solution for this problem.

Method 1: Brute Force approach.

Implementation

• We are going to use two nested loops.
• In the outer loop start from the second element in the array.
• Then calculate its left and right sum and check them if they are equal or not.

let solution1 = (arr, n = arr.length) => {
  //Return if there is only one element in the array
  if(arr.length === 1){
    return arr[0];
  }
  
  for(let i = 1; i < n; i++){
    //Calculate the left sum for the current element
    let leftSum = 0;
    for(let j = i-1; j >= 0; j--){
      leftSum += arr[j];
    }
    
    //Calculate the right sum for the current element
    let rightSum = 0;
    for(let k = i+1; k < n; k++){
      rightSum += arr[k];
    }
    
    //If equal then return the elm
    if(leftSum === rightSum){
      return arr[i];
    }
  }
  
  return -1;
}

Input:
console.log(solution1([2, 7, 3, 5, 2, 2]));

Output:
3

Time complexity: O(n ^ 2).
Space complexity: O(1).

---

Method 2: In O(n) but with extra space.

Implementation

• We are going to use two different arrays to calculate and store the left sum and right sum of each elements.
• Then compare the left and right sum for each elements.

let solution2 = (arr, n = arr.length) => {
  //Return if there is only one element in the array
  if(arr.length === 1){
    return arr[0];
  }
  
  //Calculate the left sum for each element
  let prefixSum = [];
  prefixSum[0] = arr[0];
  for(let i = 1; i < n; i++){
    prefixSum[i] = prefixSum[i - 1] + arr[i];
  }
  
  //Calculate the right sum for each element
  let suffixSum = [];
  suffixSum[n-1] = arr[n-1];
  for(let i = n-2; i >= 0; i--){
    suffixSum[i] = suffixSum[i + 1] + arr[i];
  }
  
  //Check the left sum and right sum for each element
  for(let i = 0; i < n; i++){
    if(prefixSum[i] === suffixSum[i]){
      return arr[i];
    }
  }
  
  return -1
}

Input:
console.log(solution2([2, 3, 4, 1, 4, 5]));

Output:
1

Time complexity: O(n).
Space complexity: O(n).

---

Method 3: Best approach, Time and space efficient.

Implementation to find the element with equal left and right sum.

• We are going to first calculate the sum of all the elements on the right of the first element in the array.
• Then start calculating the left sum, while calculating it we will add the element to the left sum and subtract it from right sum.
• Every time we will check if left sum is equal to right sum or not and return the element if they are equal.

let solution3 = (arr, n = arr.length) => {
  //Return if there is only one element in the array
  if(arr.length === 1){
    return arr[0];
  }
  
  let leftSum = 0, rightSum = 0;
  
  //Calculate the sum of all the right elements
  for(let i = 1; i < n; i++){
    rightSum += arr[i];
  }
  
  //Now subtract the element from the right sum
  //And add to the element to the left sum
  //Check if the rightSum === leftSum
  for(let i = 0, j = 1; j < n; i++, j++){
    rightSum -= arr[j];
    leftSum += arr[i];
    
    if(rightSum === leftSum){
      return arr[i+1];
    }
  }
  
  return -1;
}

Input:
console.log(solution2([2, 3, 4, 1, 4]));

Output:
4

Time complexity: O(n).
Space complexity: O(1).