Find equilibrium point in an array

[@ankitanand5764]

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

[@techdose4u]

Welcome

[@dayanandraut5660]

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

[@SIVANAGAKRISHNA1]

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

[@k.s.saideepak5240]

Can u please elaborate

[@jyothisumer9064]

Let's say you are at index 2 => value is 6. Now left sum*2 = 3*2 = 6. Now add this result to current value that is 6, which gives 12, which is the total sum

[@indlamaheshkumarreddy9376]

excellent work

[@shwetanksudhanshu4383]

The diagram explanation makes it even more clear thanks

[@satyasahoo9573]

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).

[@chetantailor3620]

That's what I did

[@-AmanHussain]

Great Explanantion sir .......you are great keep going .....

[@RajGupta-gk5os]

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

[@top10thingwhichyoushouldkn37]

vaise toh ma comment nahi likhta par yaha ma pighal gaya bhai bahut achi explanation thi mazzzzzzzzza aaaaaa 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

[@techdose4u]

Thanks Zakir bhai :)

[@himavaishnavijidugu8170]

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

[@utkarshgupta2909]

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

[@techdose4u]

Thanks for your appreciation

[@arijitroy8390]

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

[@ritikbhardwaj4061]

Leftsum[i]=sum[i-1]

[@prosenjitghosh2218]

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

[@rasoolnadaf2221]

Answer is wrong for 1,2,3,4 elements

[@munishkumar-wl2fb]

Thank you brother for explanation.

[@Yash-uk8ib]

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

[@techdose4u]

Thanks :)

[@avinashroy7896]

great explained by you.

[@ritwik121]

thanks sir for these videos plz make more videos on arrays

[@techdose4u]

Yea will keep adding videos.

[@rasikachinnadurai1391]

Clear explanation

[@Cube2deth]

Great videos sir! Thank you very much

[@techdose4u]

Welcome :)

[@explore_with_shanu]

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

[@shashankag5361]

👌 teaching

[@TheITEngineer]

Very nice explanation bro

[@techdose4u]

Thank you so much 🙂

[@shaikhahmad1019]

we can solve it in O(1) space

[@techdose4u]

Yep....if you keep sum in a variable then it's possible.

[@ManishSharma-fi2vr]

@@techdose4u please explain

[@siddhantrai7529]

@@ManishSharma-fi2vr arr = [1,2,6,4,0,-1] sarr = [arr[0]] for i in range(1, len(arr)): sarr.append(sarr[-1]+arr[i]) for p in range(1, len(sarr)): pivot = sarr[p] left = sarr[p-1] right = sarr[-1] - pivot if left == right: print(p)

[@ManishSharma-fi2vr]

@@siddhantrai7529 Thank You

[@Sirajkhan789]

@@techdose4u wouldn't that approach be prone to more edge conditions if we have large negatives on one side of the input array? Just curious.

[@zss123456789]

I hope I'm not missing anything but I think equilibrium point is possible with array of size 2 but it comes down to how you define sum. (I think it's correct to think of [ ] as having a sum of 0)

[@techdose4u]

That depends on specifics of problem and assumption made in the problem statement :)

[@zss123456789]

I also wanted to ask, if the input list is sorted, do we have any optimization we can add to the algorithm?

[@zss123456789]

and thanks for the quick reply!

[@techdose4u]

I don't think an optimization should be possible for sorted array because we won't know without seeing, what the elements are on the left and elements on the right of curr point. Optimization would have been possible only if elements were sorted in AP, GP, HP series. Then you could have found left and right sum value in O(1) using formula. But if elements are not in series format then i dont think you can improve.

[@zss123456789]

@@techdose4u I see! Thank you so much for the information. I'm unfamiliar with AP, GP, HP series but I'll definitely look into them (but I understand that it basically means the sum up to any index can be calculated since it's part of a series)

[@dwakwe2796]

Well explained!

[@SonamSingh-fe6ib]

very nice

[@mageshkarm459]

great explanation.

[@joydeepsarkar4774]

sir just like we have calculated the sum from left to right and stored it in an array in the similar way we can also find the sum of each index from right to left and store it in another array....then using the for-loop we can compare if both the array are equal or not at that index......i did it this way and it got submitted

[@dheerajmishra8470]

Please explain the thought process of calculating the left sum

[@techdose4u]

Its simple only. You need to get sum values of left side sub array and right side subarray to check if current point is equilibrium point. If you do it normally, then you will have to find array sum everytime. So, you would want to store the sum value somewhere to retrieve range sum in just O(1). This was the idea behind using this technique. I hope you got it :)

[@nmn02]

class Solution { public: int pivotIndex(vector& nums) { int n=nums.size(); int ans=-1; vectorprefix; int sum=0; for(int i=0;i

[@dharamraj6646]

We can use given array itself to store sum , no need of using O(n) space

[@anirudhcodes]

Thank you

[@jayeshprajapati1955]

def arrayEquilibriumIndex(arr,n): n=len(arr) leftsum=0 rightsum=0 for i in range(n): rightsum+=arr[i] for i in range(n): rightsum-=arr[i] if leftsum==rightsum: return i leftsum+=arr[i] return -1

[@eftekarahmedefat3956]

// 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; }

[@venkateshthirunagiri85]

Excellent bro

[@techdose4u]

:)

[@praneethyennam9181]

super sir

[@theupsidedown9101]

Can we do it using two pointer method with time o(n) and space o(1)?

[@ManinderSingh-cw1ve]

nice

[@techdose4u]

Thanks

[@NCCSAyesha-st3hv]

Super

[@Day-je4um]

suppose there are only two elements 1 and 0 in an array .i.e [1,0]. Does it mean index 0 is equib.Index?

[@techdose4u]

Yes correct. It depends on constraints of questions though. But it should be correct.

[@omprakash007]

in case of 2 elements what will be the answer if [1,1] or both elements are same?

[@techdose4u]

I already mentioned that equilibrium point is not possible with array of size 2 ever. Please watch the video again :)

[@Day-je4um]

for only two elements both right and left sum is not possible simultaneously . Happy coding.

[@TomerBenDavid]

Which software do you use for the for annotations?

[@techdose4u]

Ink2go :)

[@sandeepsreenivas3616]

Why can't we take leftSum = sum[i-1];

[@gauravpratap4482]

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

[@kirtikhohal5025]

see we will traverse from i=1 to i=n-2, because the first element can never be an equilibrium point, as its left array doesn't exist. same last element can never be an equilibrium point as its right array doesn't exist. that's why there was also one edge condition that if the size of array is 2 , then there will be no equilibrium point

[@VishalPatel_imvishal]

Can be solved in O(N) time and O(1) space. We just need to keep the sum in variable.

[@asgarh4589]

Why are we neglecting the corner elements? Please reply

[@iamsilly8714]

Thanks!

[@aryan7069_]

other algo in my mind came start two pointers from left and right and move them according to lsum and r sum

[@mwshubham]

Leetcode 724 find pivot index

[@techdose4u]

You must have solved most leetcode problems to know this 😂

[@MariyamVlogs707]

Dream to participate but due to no proper guaindance iam unable to write a code in competitive programming how to overcome those problem suggest me any youtube channel so that I can learn from begginng to advance sir

[@techdose4u]

Erichto solves competitive programming questions. You can follow him to see how he does it.

[@MariyamVlogs707]

@@techdose4u sir Erichto plz snd hiscyoutube channel

[@MariyamVlogs707]

@@techdose4u sir erictho Iam unable to understand his english and he is fast teaching iam unable to catch properly .I want from india coder who code problems

[@keshavraghav3896]

this code is only runs on an array which is given in the video, I cant run this code if i take different array

[@neghatnazir1668]

can we solve this using 2 pointers one from left and 1 from right when the sum of two will b equal we will return the index 0(1) extra space

[@gamingKlips99]

how can we know when we should increment the left pointer and when right pointer. As the array can have negative values too.

[@scxdb9848]

2 pointer approach works for sorted array only

[@kobo3344]

Can we do this with 2 iterators?? Like i at beginning, j at end. i=0, j=n-1 i++, j--, keep adding a[i] as left_sum, a[j] as right_sum. If (left_sum == right_sum && (j == i+1[even length] || j == i+2 [odd length] ) ..........return i. if j > i anywhere break & return false.

[@shaikrasheed2861]

Sir why every programming languages have different datastructues??

[@gamingKlips99]

they dont

[@harshitbhatt5875]

how to do it in O(1) space?

[@MariyamVlogs707]

Sir please make a video on how to take a input and output in codecheif and time complexicity space complexicity @TECHDOSE

[@techdose4u]

Actually for codechef, it's better that you code in local ide and check for sample cases. Once done, just paste the code on codechef ide and submit. Its simple. If you have doubt regarding any step then let me know.

[@MariyamVlogs707]

@@techdose4u ok sir sir suggest me to learn youtubechannel for datastructure algorithms and java

[@vishalrane1439]

Can you make coding video after explanation

[@techdose4u]

Yep. Making since last 2 years :)

[@vishalrane1439]

@@techdose4u implementation and run code

[@rpg_lover]

Can't we just use maths here. Like if an array has equibrium point then it will be left sum,element, right sum such that left sum= right sum which means left sum+right sum+element=sum of array which means if left sum=(sum of array-element)/2 then element is equilibrium point this will give solution in o(n) time and o(1) space

[@techdose4u]

Thanks for further optimizing this solution. I need people like you to keep improving the solution. Your solution should work too and it's definitely better :)

[@m00oon]

bro that wont always give the correct answer.... example..... tha array is 1 2 6 4 0 0 so according to your formula answer must be 6 because 1+2=(13 - 6)/2 but 6 is not the equilibrium point since left sum is 3 and right sum is 4 .

[@rpg_lover]

@@m00oon it depends on language like in python number won't be rounded off. Anyway using maths we can have left sum and right sum(sum of array - left sum - element) at same time to compare. No need to divide

[@sakthim7160]

We can use two pointer and two variable only to solve this problem with O(n) time and 0(1) space complexity. Then why you are going for O(n) space complexity?? First pointer will point the second position and another pointer will point the n-2 element.Then variable leftsum initially have the first value of array and right sum have n-2 value of an array. No we can increment left and right sum by incrementing first pointer and decrementing the second pointer untill it meets. Now we will left and right sum, if both are equal then we can print any of the pointer bcoz both will have same Value other wise no we can print

[@techdose4u]

This wont work.... 1st requirement for 2 ptr technique is that array should be sorted..... Try your technique on this data and let me know........ - 7,1,5,2,-4,3,0 . Try my technique and your and compare the answer.

[@sakthim7160]

@@techdose4u No equilibrium found, result of my own code!

[@techdose4u]

2 is the equilibrium point..... So your approach was incorrect.

[@sakthim7160]

@@techdose4u I get to know where my approach will fail. Thanks for let me know sir. Whenever I want to ask something to you I leave it in the comment section just reply me wherever you are getting time like the way you replied me this time.

[@vivekdarmwal]

Sir can we can do it in without using extra sum array .. Sumleft=0 For i to n-1 If (2*sumleft==sum(arr)-arr[i]) return i Else sumleft+=arr[i]

[@techdose4u]

If you don't use sum array then without preprocessing your time will not be O(N).

[@vivekdarmwal]

I don't get this..how this code is not of O(n)?

[@vivekdarmwal]

@@techdose4u can you please explain

[@alancabrera7116]

iiuc, Vivek’s assertion is correct. Two variables, sum_left and sum_ right, can be computed for the first iteration in O(n). Then, we walk down the array, updating sum_left and sum_right as we go. Storage O(n) and time O(n).

[@Day-je4um]

Sir, i think this can be more efficient. import java.util.Scanner; /**Given an array A of N positive numbers. * The task is to find the position where equilibrium first occurs in the array. * Equilibrium position in an array is a position * such that the sum of elements before it is equal to the sum of elements after it.*/ public class EquilibriumPoint { public static void main(String[] args) { Scanner sc = new Scanner(System.in); System.out.println("enter the size of the array :n"); int n = sc.nextInt(); int a[] = new int[n]; System.out.println("enter the values in array"); int i; for (i = 0; i < a.length; i++) { a[i] = sc.nextInt(); } if (n == 1) { System.out.println("equilibrium index is " + i); } if (n == 2) { System.out.println("equilibrium index not possible"); } if (n > 2) { int equibPoint = Equilibrium(a); System.out.println("equilibrium point found at " + equibPoint); } } public static int Equilibrium(int a[]) { int sumBeforeEquib = 0; int sumAfterEquib =0; for (int i =2;i

[@joycethomas6234]

source code for this too please sir :)

[@techdose4u]

You are on a rampage bro :P Will do it too. Hahaha :P

[@joycethomas6234]

@@techdose4u sorry bro , i am too desperate, also you are the only youtuber who actually has an explanation of these niche problems :)

[@techdose4u]

@@joycethomas6234 i did it. Ask for help anytime :)

[@preetikori5406]

can you please share the source code as well it will be helpful

[@miss_Peace]

@@techdose4u hey there TechDose, I'm looking for the source code too, where is it?

[@Handle60299]

int findEquilibrium(int arr[], int n) { //Your code here int sum[n]; int total=0; int j=0; sum[j] = arr[0]; for(int i=0;i

[@muthukamalan.m6316]

it's look like rain water trapping problem

[@net_nomad]

hello

[@abhishekkumarsingh9452]

1st like, 1st view and 1st comment

[@techdose4u]

:)