Given an integer array arr of size N[], the task is to find the longest equilibrium subarray i.e. a subarray such that the prefix sum of the remaining array is the same as the suffix sum.
Examples:
Input: N = 3, arr[] = {10, 20, 10}
Output: 1
Explanation: The longest subarray is {20}. The remaining prefix is {10} and suffix is {10}.
Therefore only one element in the subarray.Input: N = 6, arr[] = {2, 1, 4, 2, 4, 1}
Output: 0
Explanation: The longest subarray is of size 0.
The prefix is {2, 1, 4} and suffix is {2, 4, 1} and both has some 7.Input: N = 5, arr[] = {1, 2, 4, 8, 16}
Output: -1
Approach: This problem can be solved with two pointer technique based on the following idea:
Traverse from both the end. If the sum of prefix is less then increment the front pointer, otherwise, do the opposite. In this way we will get the minimum number of elements in prefix and suffix. So the subarray will have the maximum length because the remaining array has minimum elements.
Follow the steps mentioned below to implement the idea:
- Let i be the left pointer initially at 0, and j be the right pointer initially at N-1.
- First, we will check if the sum of all elements is 0 or not. If 0 then the whole array will be the subarray.
- Initialize two variable prefixSum = 0 and suffixSum = 0.
- Traverse array from till i not equal to j.
- If prefixSum <= suffixSum, then add arr[i] in prefixSum. And increment i by one.
- Else check that if prefixSum > suffixSum, then add arr[i] in suffixSum. And decrement j by one.
- Now check that if prefixSum equal to suffixSum then return the difference between i and j.
- Otherwise, return -1.
Below is the implementation of the above approach:
C++
// C++ implementation for the above approach#include <bits/stdc++.h>using namespace std;// C++ function to find out if prefixSum// can be equal to the suffixSumint isEqual(int n, int arr[]){ // Base Case if (n == 1) { return -1; } // Checking if the sum of all elements // is 0 or not. As the whole array can // also be a subarray. int sum=0; for(int i=0;i<n;i++) { sum+=arr[i]; } if(sum==0) return n; int prefixSum = 0, suffixSum = 0; int i = 0, j = n - 1; // We are assuming that the ans is No int ans = -1; // Iterate till there is one element in the // array while (i <= j) { // If prefix sum is less or equal then // add it in the prefix sum and // increment i if (prefixSum <= suffixSum) { prefixSum += arr[i]; i++; } // If suffix sum is less then add it in // the suffix sum and decrement j else if (prefixSum > suffixSum) { suffixSum += arr[j]; j--; } // Check if both are equal or not? if they // are then make ans = "YES" and break if (prefixSum == suffixSum) { return j - i + 1; } } if (prefixSum == suffixSum) return 0; // return ans; return -1;}// Driver functionint main(){ int N = 3; int arr[] = { 10, 20, 10 }; // Function call cout << isEqual(N, arr) << "\n"; return 0;}// This code is contributed by Pushpesh Raj. |
Java
// Java implementation for the above approachimport java.util.*;public class GFG { // C# function to find out if prefixSum // can be equal to the suffixSum static int isEqual(int n, int[] arr) { // Base Case if (n == 1) { return -1; } // Checking if the sum of all elements // is 0 or not. As the whole array can // also be a subarray. int sum=0; for(int i=0;i<n;i++) { sum+=arr[i]; } if(sum==0) return n; int prefixSum = 0, suffixSum = 0; int i = 0, j = n - 1; // We are assuming that the ans is No int ans = -1; // Iterate till there is one element in the // array while (i <= j) { // If prefix sum is less or equal then // add it in the prefix sum and // increment i if (prefixSum <= suffixSum) { prefixSum += arr[i]; i++; } // If suffix sum is less then add it in // the suffix sum and decrement j else if (prefixSum > suffixSum) { suffixSum += arr[j]; j--; } // Check if both are equal or not? if they // are then make ans = "YES" and break if (prefixSum == suffixSum) { return j - i + 1; } } if (prefixSum == suffixSum) return 0; // return ans; return -1; } // Driver function public static void main(String args[]) { int N = 3; int[] arr = { 10, 20, 10 }; // Function call System.out.println(isEqual(N, arr)); }} |
Python3
# Python program for the above approachdef isEqual(n, arr): # Base Case if (n == 1): return -1 # checking if the sum of all the elements # is 0 or not. As whole array can also # be the subarray Sum=0 for i in range(n): Sum=Sum+arr[i] if(Sum==0): return n prefixSum,suffixSum = 0,0 i,j = 0,n - 1 # We are assuming that the ans is No ans = -1 # Iterate till there is one element in the # array while (i <= j): # If prefix sum is less or equal then # add it in the prefix sum and # increment i if (prefixSum <= suffixSum): prefixSum += arr[i] i += 1 # If suffix sum is less then add it in # the suffix sum and decrement j elif (prefixSum > suffixSum): suffixSum += arr[j] j -= 1 # Check if both are equal or not? if they # are then make ans = "YES" and break if (prefixSum == suffixSum): return j - i + 1 if (prefixSum == suffixSum): return 0 # return ans; return -1# Driver functionN = 3arr = [10, 20, 10]# Function callprint(isEqual(N, arr)) |
C#
// C# implementation for the above approachusing System;class GFG {// C# function to find out if prefixSum// can be equal to the suffixSumstatic int isEqual(int n, int[] arr){ // Base Case if (n == 1) { return -1; } // Checking if the sum of all elements // is 0 or not. As the whole array can // also be a subarray. int sum=0; int k; for(k=0;k<n;k++) { sum+=arr[k]; } if(sum==0) return n; int prefixSum = 0, suffixSum = 0; int i = 0, j = n - 1; // Iterate till there is one element in the // array while (i <= j) { // If prefix sum is less or equal then // add it in the prefix sum and // increment i if (prefixSum <= suffixSum) { prefixSum += arr[i]; i++; } // If suffix sum is less then add it in // the suffix sum and decrement j else if (prefixSum > suffixSum) { suffixSum += arr[j]; j--; } // Check if both are equal or not? if they // are then make ans = "YES" and break if (prefixSum == suffixSum) { return j - i + 1; } } if (prefixSum == suffixSum) return 0; // return ans; return -1;}// Driver functionpublic static void Main(){ int N = 3; int[] arr = { 10, 20, 10 }; // Function call Console.WriteLine(isEqual(N, arr));}} |
Javascript
<script> // JavaScript program for the above approach function isEqual(n, arr) { // Base Case if (n == 1) { return -1; } // Checking if the sum of all elements // is 0 or not. As the whole array can // also be a subarray. let sum=0; for(let i=0;i<n;i++) { sum+=arr[i]; } if(sum==0) return n; let prefixSum = 0, suffixSum = 0; let i = 0, j = n - 1; // We are assuming that the ans is No let ans = -1; // Iterate till there is one element in the // array while (i <= j) { // If prefix sum is less or equal then // add it in the prefix sum and // increment i if (prefixSum <= suffixSum) { prefixSum += arr[i]; i++; } // If suffix sum is less then add it in // the suffix sum and decrement j else if (prefixSum > suffixSum) { suffixSum += arr[j]; j--; } // Check if both are equal or not? if they // are then make ans = "YES" and break if (prefixSum == suffixSum) { return j - i + 1; } } if (prefixSum == suffixSum) return 0; // return ans; return -1; } // Driver function let N = 3; let arr = [10, 20, 10]; // Function call document.write(isEqual(N, arr) + "<br>"); </script> |
Output
1
Time Complexity: O(N)
Auxiliary Space: O(1)
