East or West, Striver bhaiya sabse Best UA-cam pe esa koi bhi nahi hoga jo job ke saath saath itna content banata ho aur apni company bhi chalata ho...🙏🙏🙏
This was a great problem, i hope one day i can come up with such approach all by myself. For those who might of two pointers i at 0 and j at n-1 and compare instances , this method will fail on TC such as [11,49,100,20,86,29,72], because at first it looks 72 should be chosen but all the elements after 11 are large and they will compensate and produce maximum score
Thank you... I was dying to understand the problem statement. Now this example makes it easier why a sliding window approach should be used and not the two pointer approach.
Hii Striver! I have implemented another logic which is to consider a fixed window of size 'k' from the right side of the array, calculating the sum initially and then comparing with other windows by moving the window to the front of the array step by step. Here's my code -> class Solution { public: int maxScore(vector& cardPoints, int k) { int size = cardPoints.size(); int start = size-k; int end = size-1; int sum = 0; // Calculating sum initially int low = start; int high = end; while(low=0) { if(sum > maxSum) maxSum = sum; sum = sum - cardPoints[start]; start = (start+1)% size; end = (end+1)% size; sum = sum + cardPoints[end]; k--; } return maxSum; } };
another approach? we can take a consecutive window of size (n-k) and find the minimum sum window , that yields us the maximum sum of the remaining 4 elements from the first or last
public static int maxScore(int[] cardPoints, int k) { int lsum =0, rsum =0, max =0,sum =0; int n = cardPoints.length; for(int i=0;imax){ max = sum; } } return max; } same approach but easier to understand
I have been following your a2z DSA course. I want to do strings but there is no videos and problems in your sheet. Please make videos on them and upload the problems
bro what are you talking about.....the a2z dsa sheet has 2 dedicated section for strings....step-5 and step-18, which covers all basics,medium and hard string questions !!!
One more approach: As the qsn asking us to pickup the maximum points , and the points can be pickup either front or back side, (which leaves the least sum of points in the array) so we can find the minimum sum ,with window size n-k and subtract the result from total sum of the array ,we can use sliding window to solve this Time Complexity is O(N) Space Complexity is O(1)
You can take n-k as windowlength , totalsum=sum(arr) windowlength=n-k currwindowsum=sum(arr[:windowlength) maxwin=curwin , for l in range(windowlen,n): curwin +=arr[l]-arr[l-windowlen] netsum=total-curwin maxwin=max(maxwin,netsum)
Do we need seperate variables for right and left sum, can we not just maintain a single variable and 2 pointers and remove left pointer value and increase right bponter value
class Solution { public: int maxScore(vector& nums, int k) { int leftSum=0,rightSum=0,maxSum=0; for(int i=0;i=0;i--){ leftSum-=nums[i]; rightSum+=nums[rightIndex]; rightIndex--; maxSum=max(maxSum,leftSum+rightSum); } return maxSum; } }; here's the working code..... 😌
With modulo , its much easier class Solution { public: int maxScore(vector& cardPoints, int k) { int n = cardPoints.size(); int left = n-k; int right = n-k; int ans = 0; int sum = 0; while (left < n) { if ((right - left + 1)
thanks you bhaiya, Understood😊 import java.util.*; public class main{ public static void main(String args[]){ int a[] = {6, 2, 3, 4, 7, 2, 1, 7, 1}; int k = 4; System.out.println("MAX SUM IS: "+ findMaxPoints(a, k)); } public static int findMaxPoints(int a[], int k){ int lsum = 0; int rsum = 0; int maxsum = 0;
my approach is similar to urs what i did is take k last elements followed by k first then i took sum of last k and then kept removing the front and adding the latest element in the sum and took max of these steps: int n=arr.size(); int ans=0; int sum=0; int ret=0; for(int i=n-k;i
this method will fail on TC such as [11,49,100,20,86,29,72], because at first it looks 72 should be chosen but all the elements after 11 are large and they will compensate and produce maximum score copied from another comment
here that you have included all the elements as 4 size but the index 4 element 7 is not at all included if its included the output will be 17 am i correct
class Solution { public int maxScore(int[] nums, int k) { //int left=0,right=0,maxi=0,sum=0; int n=nums.length,leftsum=0,rightsum=0,maxi=0; for(int i=0;i=0;i--){ leftsum-=nums[i];//contract //if(j>n-k-1) rightsum+=nums[j];//expand j--; maxi=Math.max(maxi,leftsum+rightsum); } return maxi; } } whats wong with it
I think you are ignoring value of leftsum from (idx = 0 to idx=k-1) in maxi... So it doesn't take value of leftsum for first kth elements. So after the first loop try maxi = leftsum before going for second loop in which you are decreasing value of leftsum....try it...may help..
l = n-k r=n-1 s= sum of arr from index l to index r while r! = k-1: s -= arr[l] l=(l+1) %n r=(r+1) %n s+= arr[r] MaxSum = max(MaxSum, s) Is this approach correct?
Understood, implementing with pseudocode is not able to pass leetcode test cases! did i miss something! def (nums, k): lsum = 0 maxsum = 0 n = len(nums) for i in range(k-1): lsum = lsum + nums[i] maxsum = lsum r_idx = n-1 maxsum = 0 rsum = 0 for i in range(k-1, -1, -1): lsum = lsum - nums[i] rsum = rsum + nums[r_idx-i] r_idx = r_idx - 1 maxsum = max(maxsum, lsum+rsum) return maxsum
int maxScore(vector& cardPoints, int k) { int n = cardPoints.size(); int left = k-1; int right = n-1; int maxSum = INT_MIN; int sum = 0; for(int i = 0; i < k; i++){ sum += cardPoints[i]; } maxSum = max(maxSum, sum); while(left >= 0){ sum = sum - cardPoints[left]; sum = sum + cardPoints[right]; maxSum = max(maxSum, sum); left--; right--; } return maxSum; }
Another approach with is exactly same as one of the very standard Sliding window question. class Solution { public: int maxScore(vector& cardPoints, int k) { // we need to find substring of size (n-k) and minimum sum // final answer = is total sum of length n - minimum sum of substring of length (n-k) // = maximum sum of length k taken from extreme left/right int n = cardPoints.size(); int l = 0; int r = 0; int ans = INT_MAX; int sum = 0; int val = 0; for(auto it:cardPoints) val+=it; while(r(n-k)){ sum-=cardPoints[l]; l++; } if(r-l+1==(n-k)) ans = min(ans, sum); r++; } return val-ans;
I thought of this approach at the very beginning and then thought of how to optimise this for an hour then came here to see the optimised approach but 😂😂😂😂😂😂 after coming here i realised I just wasted an hour
Hello everyone, another approach we can think of is We can take sum of all the elements and as according to example we want sum of 4 maximum elements with given conditions and the size of array is 9 so actually we can calculate the sum of 5 consecutive elements which is minimum among all and then we can subtract it from the total sum of all the elements of the array
Started from the end and circularly rotated sliding window ``` int maxScore(vector& cardPoints, int k) { int i, j, maxSum, sum, n = cardPoints.size(); bool flag = false; i = j = n - k; maxSum = sum = 0; while(true) { sum += cardPoints[j]; if(j-i+1 == k || flag) { flag = true; maxSum = max(maxSum, sum); if(i == 0) break; sum -= cardPoints[i]; i = (i + 1) % n; } j = (j + 1) % n; } return maxSum; } ```
class Solution { public: int maxScore(vector& nums, int k) { int lsum=0; int rsum = 0; int maxSum = 0; int n = nums.size(); for(int i=0;i=0;i--){ lsum=lsum-nums[i]; rsum=rsum+nums[rindex]; rindex=rindex-1; maxSum= max(maxSum,lsum+rsum); } return maxSum; } };this code not passing testcases in leetcode
optimal solution in another way ------------------------------------------------------ public int maxScore(int[] arr, int k) { int n = arr.length; int i = 1, j = 1; int sum = 0,maxsum = -1; int end = 2 * k; /// to consider only first k and last k elements while (j k) { sum -= arr[(n + k - i) % n]; i++; } if ((j - i) + 1 == k) maxsum = Math.max(sum, maxsum); j++; } return maxsum; } ----------------------------------------
class Solution { public: int maxScore(vector& a, int k) { int n=a.size(); int s1=0; int s2=0; int i=0; int j=n-k; while(j k. tk loop chala k times o(k) { s2=s2+a[j]; j++; } int maxi = s2;
Implementing it yourself makes it much more clearer.
East or West, Striver bhaiya sabse Best
UA-cam pe esa koi bhi nahi hoga jo job ke saath saath itna content banata ho aur apni company bhi chalata ho...🙏🙏🙏
codewithmik bhi hai bro
@@Coder_Buzz07 yup
This was a great problem, i hope one day i can come up with such approach all by myself. For those who might of two pointers i at 0 and j at n-1 and compare instances , this method will fail on TC such as [11,49,100,20,86,29,72], because at first it looks 72 should be chosen but all the elements after 11 are large and they will compensate and produce maximum score
Thank you... I was dying to understand the problem statement. Now this example makes it easier why a sliding window approach should be used and not the two pointer approach.
Hii Striver!
I have implemented another logic which is to consider a fixed window of size 'k' from the right side of the array, calculating the sum initially and then comparing with other windows by moving the window to the front of the array step by step.
Here's my code ->
class Solution {
public:
int maxScore(vector& cardPoints, int k) {
int size = cardPoints.size();
int start = size-k;
int end = size-1;
int sum = 0;
// Calculating sum initially
int low = start;
int high = end;
while(low=0)
{
if(sum > maxSum) maxSum = sum;
sum = sum - cardPoints[start];
start = (start+1)% size;
end = (end+1)% size;
sum = sum + cardPoints[end];
k--;
}
return maxSum;
}
};
my approach using while loop in java -
int[] ar= {6,2,3,4,7,2,1,7,1};
int k=4;
int sum=0;
for(int i=0;iar.length-k-1) {
sum+=ar[l]; sum-=ar[r];
maxx=Math.max(maxx,sum);
l--;r--;
}
System.out.println(maxx);
thanks for so easy and intuitive solution. Lot of solutions for this problem are problem which have made it look really complex
another approach? we can take a consecutive window of size (n-k) and find the minimum sum window , that yields us the maximum sum of the remaining 4 elements from the first or last
Yes...that also makes sense...but what will be time complexity for getting min sum of n-k array size ?
@@akshaysharmaBSG O(N) time and O(1) space
@@AryanGupta-2024 yeah i did this but ig his solution is better as it is O(2k)
@@sjain6320 the above said solution would be better in the cases where k > n/2
u are the best bhaiya🤩 eagerly waiting for your string playlist
Thank you @striver , for making DSA Easy for us . Hatts of to you .
Classic problem.. thanks Striver!
public static int maxScore(int[] cardPoints, int k) {
int lsum =0, rsum =0, max =0,sum =0;
int n = cardPoints.length;
for(int i=0;imax){
max = sum;
}
}
return max;
}
same approach but easier to understand
In this case with above solution in video we can't take 7 i.e 7,2,1,7 which will result in more sum . or is it important to take the last card ?
@@VarshaSingh-hi2sb have the same doubt we are ignoring the middle elements , but why ? cant there be a scenario where they contribute to the sum?
Understood...........Thank You So Much for this wonderful video..........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
I have been following your a2z DSA course. I want to do strings but there is no videos and problems in your sheet. Please make videos on them and upload the problems
bro what are you talking about.....the a2z dsa sheet has 2 dedicated section for strings....step-5 and step-18, which covers all basics,medium and hard string questions !!!
@@mrinceptionist7038 He has questions but there is no solve videos for them
hey striver ... i'm the one of those follower who always give time for like and comment whenever i watch your videos.....thanku again
One more approach:
As the qsn asking us to pickup the maximum points , and the points can be pickup either front or back side, (which leaves the least sum of points in the array) so we can find the minimum sum ,with window size n-k and subtract the result from total sum of the array ,we can use sliding window to solve this
Time Complexity is O(N)
Space Complexity is O(1)
Understood bhai. Thank you.
You can take n-k as windowlength ,
totalsum=sum(arr)
windowlength=n-k
currwindowsum=sum(arr[:windowlength)
maxwin=curwin ,
for l in range(windowlen,n):
curwin +=arr[l]-arr[l-windowlen]
netsum=total-curwin
maxwin=max(maxwin,netsum)
OTHER CREATORS! be like "BHAI SAANS THO LENE DE......".
Thanks striver for this amazing video.
Hi striver, I knew a better solution that solves in single pass.
share it please
Thank you so much for the video bro.
"UNDERSTOOD BHAIYA!!"
Do we need seperate variables for right and left sum, can we not just maintain a single variable and 2 pointers and remove left pointer value and increase right bponter value
class Solution {
public:
int maxScore(vector& nums, int k) {
int leftSum=0,rightSum=0,maxSum=0;
for(int i=0;i=0;i--){
leftSum-=nums[i];
rightSum+=nums[rightIndex];
rightIndex--;
maxSum=max(maxSum,leftSum+rightSum);
}
return maxSum;
}
};
here's the working code.....
😌
understood!Thank you Striver
feels a little happy to solve this on my own
thanks vvvvv much sir,i really wanted a playlist like this
One more approach is finding min_sum of all windows of size array_length - k , array_total_sum - min_sum will be the ans.
Super easily understood
class Solution {
public int maxScore(int[] cardPoints, int k) {
int lsum=0,rsum=0,maxSum=0;
for(int i=0;i=0;i--){
lsum-=cardPoints[i];
rsum+=cardPoints[rindex];
rindex--;
maxSum=Math.max(maxSum,(lsum+rsum));
}
return maxSum;
}
}
i was here and anyone can have this java code !!!! and also initial loop will go to end k because of correct calculation of lsum
With modulo , its much easier
class Solution {
public:
int maxScore(vector& cardPoints, int k) {
int n = cardPoints.size();
int left = n-k;
int right = n-k;
int ans = 0;
int sum = 0;
while (left < n) {
if ((right - left + 1)
Understood ❤
Understood 😊😊
Wow......nice approach......
NICE SUPER EXCELLENT MOTIVATED
Thank you very much
Thanks Brother❤
thanks you bhaiya, Understood😊
import java.util.*;
public class main{
public static void main(String args[]){
int a[] = {6, 2, 3, 4, 7, 2, 1, 7, 1};
int k = 4;
System.out.println("MAX SUM IS: "+ findMaxPoints(a, k));
}
public static int findMaxPoints(int a[], int k){
int lsum = 0;
int rsum = 0;
int maxsum = 0;
for(int i=0;i
great video 😇
Mja AAGeYa!!
my approach is similar to urs what i did is take k last elements followed by k first then i took sum of last k and then kept removing the front and adding the latest element in the sum and took max of these steps: int n=arr.size();
int ans=0;
int sum=0;
int ret=0;
for(int i=n-k;i
Understood. Thanks
Thankyou
Thanks❤
can anyone guide me why the two pointer approach is not working here that I am place i in the 0 and the J = n-1;
this method will fail on TC such as [11,49,100,20,86,29,72], because at first it looks 72 should be chosen but all the elements after 11 are large and they will compensate and produce maximum score
copied from another comment
it was helpful
Where is it mentoned to keep consecutive number
understood bhaiya
here that you have included all the elements as 4 size but the index 4 element 7 is not at all included if its included the output will be 17 am i correct
class Solution {
public int maxScore(int[] nums, int k) {
//int left=0,right=0,maxi=0,sum=0;
int n=nums.length,leftsum=0,rightsum=0,maxi=0;
for(int i=0;i=0;i--){
leftsum-=nums[i];//contract
//if(j>n-k-1)
rightsum+=nums[j];//expand
j--;
maxi=Math.max(maxi,leftsum+rightsum);
}
return maxi;
}
} whats wong with it
I think you are ignoring value of leftsum from (idx = 0 to idx=k-1) in maxi... So it doesn't take value of leftsum for first kth elements.
So after the first loop try maxi = leftsum before going for second loop in which you are decreasing value of leftsum....try it...may help..
what about the elements in the middle ? how do we reach them ?
You are only allowed to take
l = n-k
r=n-1
s= sum of arr from index l to index r
while r! = k-1:
s -= arr[l]
l=(l+1) %n
r=(r+1) %n
s+= arr[r]
MaxSum = max(MaxSum, s)
Is this approach correct?
More of a two pointer approach rather than sliding window....as sliding window format is generally Diffrent.
Understood, implementing with pseudocode is not able to pass leetcode test cases! did i miss something!
def (nums, k):
lsum = 0
maxsum = 0
n = len(nums)
for i in range(k-1):
lsum = lsum + nums[i]
maxsum = lsum
r_idx = n-1
maxsum = 0
rsum = 0
for i in range(k-1, -1, -1):
lsum = lsum - nums[i]
rsum = rsum + nums[r_idx-i]
r_idx = r_idx - 1
maxsum = max(maxsum, lsum+rsum)
return maxsum
int maxScore(vector& cardPoints, int k) {
int n = cardPoints.size();
int left = k-1;
int right = n-1;
int maxSum = INT_MIN;
int sum = 0;
for(int i = 0; i < k; i++){
sum += cardPoints[i];
}
maxSum = max(maxSum, sum);
while(left >= 0){
sum = sum - cardPoints[left];
sum = sum + cardPoints[right];
maxSum = max(maxSum, sum);
left--;
right--;
}
return maxSum;
}
You set maxsum to 0 and r_idx-i is wrong
@striver where can i get the source code solution for content
Why 2*k and not 2+k?
Isn't 2 separate loop takes adding and nested takes multiplication?
Bhai tu first year se wapas repeat kr
Another approach with is exactly same as one of the very standard Sliding window question.
class Solution {
public:
int maxScore(vector& cardPoints, int k) {
// we need to find substring of size (n-k) and minimum sum
// final answer = is total sum of length n - minimum sum of substring of length (n-k)
// = maximum sum of length k taken from extreme left/right
int n = cardPoints.size();
int l = 0;
int r = 0;
int ans = INT_MAX;
int sum = 0;
int val = 0;
for(auto it:cardPoints)
val+=it;
while(r(n-k)){
sum-=cardPoints[l];
l++;
}
if(r-l+1==(n-k))
ans = min(ans, sum);
r++;
}
return val-ans;
}
};
I thought of this approach at the very beginning and then thought of how to optimise this for an hour then came here to see the optimised approach but 😂😂😂😂😂😂 after coming here i realised I just wasted an hour
Understood
understood
Hello everyone, another approach we can think of is
We can take sum of all the elements and as according to example we want sum of 4 maximum elements with given conditions and the size of array is 9 so actually we can calculate the sum of 5 consecutive elements which is minimum among all and then we can subtract it from the total sum of all the elements of the array
i think everyone is providing solution when N=2k+1, what if k is lesser than that??
JAVA BOLNE WALO K LIYE : --
class Solution {
public int maxScore(int[] arr, int k) {
int sum=0;
for(int i=0;i
class Solution {
public int maxScore(int[] cardPoints, int k) {
long start = System.nanoTime();
int maxy = 0;
int lsum = 0;
int rsum = 0;
for(int i=0;i=0;j--){
rsum = rsum + cardPoints[rightIndex];
rightIndex--;
lsum = lsum - cardPoints[j];
maxy = Math.max(maxy,lsum+rsum);
}
long end = System.nanoTime();
System.out.println(end-start);
return maxy;
}
}
We want Strings playlist Striver
Started from the end and circularly rotated sliding window
```
int maxScore(vector& cardPoints, int k) {
int i, j, maxSum, sum, n = cardPoints.size();
bool flag = false;
i = j = n - k;
maxSum = sum = 0;
while(true)
{
sum += cardPoints[j];
if(j-i+1 == k || flag)
{
flag = true;
maxSum = max(maxSum, sum);
if(i == 0)
break;
sum -= cardPoints[i];
i = (i + 1) % n;
}
j = (j + 1) % n;
}
return maxSum;
}
```
class Solution {
public:
int maxScore(vector& nums, int k) {
int lsum=0;
int rsum = 0;
int maxSum = 0;
int n = nums.size();
for(int i=0;i=0;i--){
lsum=lsum-nums[i];
rsum=rsum+nums[rindex];
rindex=rindex-1;
maxSum= max(maxSum,lsum+rsum);
}
return maxSum;
}
};this code not passing testcases in leetcode
the condition in the first loop will be i < k or i
optimal solution in another way
------------------------------------------------------
public int maxScore(int[] arr, int k) {
int n = arr.length;
int i = 1, j = 1;
int sum = 0,maxsum = -1;
int end = 2 * k; /// to consider only first k and last k elements
while (j k) {
sum -= arr[(n + k - i) % n];
i++;
}
if ((j - i) + 1 == k)
maxsum = Math.max(sum, maxsum);
j++;
}
return maxsum;
}
----------------------------------------
Subah uthe, aapke darshan hogye. Ab saare contest badia jayenge, sare hard question solve hone lag jayenge 😂😂
bro konse year mein ho??
🙌🏻
🙌
same approach but implemented in a simpler way
class Solution {
private static int sumupto(int k , int[]arr){
int res=0;
for(int i =0;i
hil bhi ni rhe ye questions mujhse
😀😀
US
bhaiya aap thora sick ya kaafi stressed lg rhe ho. Wo phle jaisa energy kahi na kahi missing laga.
Are bhaiya itni fast fast
class Solution {
public:
int maxScore(vector& a, int k) {
int n=a.size();
int s1=0; int s2=0; int i=0; int j=n-k;
while(j k. tk loop chala k times o(k)
{
s2=s2+a[j];
j++;
}
int maxi = s2;
j=n-k;
while(i
Understood
understood
Understood
understood
Understood
understood
Understood
understood