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
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
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
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).
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
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
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
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
@@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)
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 :)
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)
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.
@@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)
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
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 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
// 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; }
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
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 :)
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 .
@@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
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).
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.
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.
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
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
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.
@@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.
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
Man, you are one of the best teachers that is available on youtube thanks a lot for your explanation videos.
Welcome
i was stuck in this problem for a long time. this video cleared all my doubts. thanks.
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
Can u please elaborate
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
excellent work
Great Explanantion sir .......you are great keep going .....
The diagram explanation makes it even more clear thanks
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
Thanks Zakir bhai :)
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).
That's what I did
The hard work he has done to make 246 videos in this series is really unimaginable !! Great man !!
Thanks for your appreciation
Thank you so much for the great explaination.
I got struked in the logic of the problem.Tq for the approach.
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
Leftsum[i]=sum[i-1]
sir ur algorithm and approach is excellent...
keep making such videos...
Thanks :)
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
Do i need to take extraa array to store sum of array ??
If yes ?
I would increase space
great explained by you.
Thank you brother for explanation.
thanks sir for these videos plz make more videos on arrays
Yea will keep adding videos.
Very nice explanation bro
Thank you so much 🙂
👌 teaching
Great videos sir! Thank you very much
Welcome :)
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
Answer is wrong for 1,2,3,4 elements
great explanation.
why we are iterating till n-1 and not to whole array of size N ?
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
Clear explanation
very nice
we can solve it in O(1) space
Yep....if you keep sum in a variable then it's possible.
@@techdose4u please explain
@@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)
@@siddhantrai7529 Thank You
@@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.
nice
Thanks
Well explained!
Can we do it using two pointer method with time o(n) and space o(1)?
Why are we neglecting the corner elements? Please reply
Please explain the thought process of calculating the left sum
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 :)
Excellent bro
:)
Which software do you use for the for annotations?
Ink2go :)
super sir
Super
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)
That depends on specifics of problem and assumption made in the problem statement :)
I also wanted to ask, if the input list is sorted, do we have any optimization we can add to the algorithm?
and thanks for the quick reply!
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.
@@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)
Thank you
class Solution {
public:
int pivotIndex(vector& nums) {
int n=nums.size();
int ans=-1;
vectorprefix;
int sum=0;
for(int i=0;i
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
Why can't we take
leftSum = sum[i-1];
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
Erichto solves competitive programming questions. You can follow him to see how he does it.
@@techdose4u sir Erichto plz snd hiscyoutube channel
@@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
Can be solved in O(N) time and O(1) space.
We just need to keep the sum in variable.
in case of 2 elements what will be the answer if [1,1] or both elements are same?
I already mentioned that equilibrium point is not possible with array of size 2 ever. Please watch the video again :)
for only two elements both right and left sum is not possible simultaneously . Happy coding.
this code is only runs on an array which is given in the video, I cant run this code if i take different array
suppose there are only two elements 1 and 0 in an array .i.e [1,0]. Does it mean index 0 is equib.Index?
Yes correct. It depends on constraints of questions though. But it should be correct.
// 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;
}
Thanks!
We can use given array itself to store sum , no need of using O(n) space
Sir why every programming languages have different datastructues??
they dont
how to do it in O(1) space?
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
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 :)
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 .
@@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
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]
If you don't use sum array then without preprocessing your time will not be O(N).
I don't get this..how this code is not of O(n)?
@@techdose4u can you please explain
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).
Can you make coding video after explanation
Yep. Making since last 2 years :)
@@techdose4u implementation and run code
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
how can we know when we should increment the left pointer and when right pointer. As the array can have negative values too.
2 pointer approach works for sorted array only
Sir please make a video on how to take a input and output in codecheif and time complexicity space complexicity @TECHDOSE
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.
@@techdose4u ok sir sir suggest me to learn youtubechannel for datastructure algorithms and java
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.
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
other algo in my mind came start two pointers from left and right and move them according to lsum and r sum
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
Leetcode 724 find pivot index
You must have solved most leetcode problems to know this 😂
source code for this too please sir :)
You are on a rampage bro :P Will do it too. Hahaha :P
@@techdose4u sorry bro , i am too desperate, also you are the only youtuber who actually has an explanation of these niche problems :)
@@joycethomas6234 i did it. Ask for help anytime :)
can you please share the source code as well it will be helpful
@@techdose4u hey there TechDose, I'm looking for the source code too, where is it?
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
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.
@@techdose4u No equilibrium found, result of my own code!
2 is the equilibrium point..... So your approach was incorrect.
@@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.
it's look like rain water trapping problem
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
Sir code to kar detev
hello
1st like, 1st view and 1st comment
:)