Find equilibrium point in an array

This video explains how to find equilibrium point in an array. 2 methods are explained which involves a preprocessing efficient method which works in just O(N) time. This program is frequently asked in interviews in software companies. CODE LINK is present in description below. If you find any difficulty or have any query then do COMMENT below. PLEASE help our channel by SUBSCRIBING and LIKE our video if you found it helpful...CYA :)

[ankitanand]

Man, you are one of the best teachers that is available on youtube thanks a lot for your explanation videos.

[dayanandraut]

i was stuck in this problem for a long time. this video cleared all my doubts. thanks.

[SIVANAGAKRISHNA]

Thank you! Also, Since left sum equals right sum at equilibrium, iterate & check if
2*(sum until now excluding current element) equals total sum excluding current element. Which reduces space complexity as well

[satyasahoo]

If we take only 2 extra variables Lsum=a[0] and calculate only once Rsum=sum of all elements from a[2] till end. And update every time Lsum=Lsum+arr[i] and Rsum=Rsum-arr[i+1] for all i from 1 to n-2, then we can get rid of space requirement of O(n).

[topthingwhichyoushouldkn]

vaise toh ma comment nahi likhta par yaha ma pighal gaya

bhai bahut achi explanation thi gayi

khas kar ki jo tum explanation deta ho na usma
thanks for this awesome video and make moree and more cool videos like this

[utkarshgupta]

The hard work he has done to make 246 videos in this series is really unimaginable !! Great man !!

[RajGupta-gkos]

We can use the binary search to also find the eq. for example the arr = 1 2 6 4 0 -1 we make two extra variables j and k and j = 0 index and k = n-1 then do simple binary search so the mid point be 3 index and then we use a for loop to add int one = j + mid - 1 and int two = mid + k then binary search will be 1) condition if(one == two ) return mid else if (one > two) e = mid - 1 else s = mid+ 1 ... this method will solve the prblm in O(n) complexity with O(1) space complexity

[shwetanksudhanshu]

The diagram explanation makes it even more clear thanks

[himavaishnavijidugu]

Thank you so much for the great explaination.
I got struked in the logic of the problem.Tq for the approach.

[-AmanHussain]

Great Explanantion sir are great keep going

[prosenjitghosh]

My approach is much easier and space complexity O(1)
equilibriumPoint(a, n)
{
if(n==1) return 1;
if(n==2) return -1;
//First Calculate total sum
var totalSum=0;
for(var i=0;i<n;i++){
totalSum+=a[i];
}
var sum=0;
for(var j=0;j<n;j++){
//Total sum minus current element divided by two should be
//equal with sum before this point
if((totalSum-a[j])/2==sum){
return j+1;
}
sum+=a[j];
}
return -1;
}

[arijitroy]

The code for his implementation is:


public int pivotIndex(int[] nums) {
int sum[]=new int[nums.length];
sum[0]=nums[0];//calculate the sum of all the elements
for(int i=1;i<nums.length;i++){
sum[i]=nums[i]+sum[i-1];
}
int total=sum[nums.length-1];
for(int i=0;i<nums.length;i++){
int left=sum[i]-nums[i];//formula for left sum
int right=total-sum[i];//formula for right sum
if(left==right)//if left and right matches return index
return i;
}
return -1;
}

[explore_with_shanu]

Do i need to take extraa array to store sum of array ??
If yes ?
I would increase space

[gauravpratap]

why we are iterating till n-1 and not to whole array of size N ?

[Yash-ukib]

sir ur algorithm and approach is excellent...
keep making such videos...

[ritwik]

thanks sir for these videos plz make more videos on arrays

[nmn]

class Solution {
public:
int pivotIndex(vector<int>& nums) {
int n=nums.size();
int ans=-1;
vector<int>prefix;
int sum=0;
for(int i=0;i<n;i++){
sum+=nums[i];
prefix.push_back(sum);
}
int total=prefix[n-1];
for(int i=0;i<n;i++){
int left=prefix[i]-nums[i];
int right=total-prefix[i];
if(left==right){
return i;
}
}
return -1;
}
};

[sandeepsreenivas]

Why can't we take

leftSum = sum[i-1];

[hornyjesus_]

Creating the sum[ ] takes O(N²) time right?

[eftekarahmedefat]

// java code



public static int equilibriumPoint(long arr[], int n) {

// Your code here
long sum = 0;
int left = 0, right = n - 1;

while(left < right) {
if(sum > 0)
sum = sum - arr[right--];
else
sum = sum + arr[left++];
}

if(sum != 0) return -1;

return right + 1;
}