Java solution: class Solution { public int maxScore(int[] cardPoints, int k) { int len = cardPoints.length; int l = 0, r = len - k; int total = 0; for(int i = r ; i < len; i++) total += cardPoints[i]; int res = total; while(r < len) { total += (cardPoints[l] - cardPoints[r]); res = Math.max(res, total); l++; r++; } return res; } }
my easy solution to this question. initially i just consider first k integers from left. and then start deleting on element from left and adding one element to right side sum. and just check which is max sum.. java code below. class Solution { public int maxScore(int[] cardPoints, int k) {
int len=cardPoints.length; int sum=findsum(cardPoints,k); int maxSum=Math.max(0,sum);
Wow came here struggling with this question and you said this is super easy for Google :( I have my interview on the 15th fingers crossed and thank you for a great explanation
For me it was a hard problem to solve since the key is to see the array as cyclical. I missed that. I went ahead and did a DP: def maxScore(cards, k): if k == 1: return max(cards[0], cards[-1]) @functools.lru_cache(maxsize=None) def dfs(l, r): if l + abs(r) - 1 == k: return 0 left = cards[l] + dfs(l + 1, r) right = cards[r] + dfs(l, r - 1) return max(left, right) return dfs(0, -1) which works just fine but is no match to the time (and space) complexity of your solution. I guess for me now the problems that DONT fit neatly in the standard categories (trees, dyn. prog etc.) are harder to solve bec. they sneak up on you.
There are a couple of problems like Stone Game that perform well with this approach, I guess the fact that it is only you that is selecting i.e. there isn't another person a clue that we need to think differently ? I did what you did only to TLE
@NeetCode , there are a couple of problems such as Stone Game that perform well with the left & right pointer approach, simulating the entire process in a way. The fact that it is only you that is selecting i.e. there isn't another person involved in selecting the cards, is that a clue that we need to think differently ? I used left and right pointers with a cache using (l,r) as key, it TLE'd. Would like to know if you thought of that approach as well, trying to understand the intuition behind sliding window :) Great work btw :)
I used left and right pointers as well but when there's [2,2,2] and k=2 I'm getting wrong o/p. idk I'm literally stuck there and everyone's using sliding window that I've no idea of😅
This solution does use extra k space but I feel its more intuitive class Solution: def maxScore(self, cardPoints: List[int], k: int) -> int: left_card_sum = [0]*(k+1) right_card_sum = [0]*(k+1) max_score = 0 _sum_so_far = 0 for i in range(1,k+1): _sum_so_far += cardPoints[i-1] left_card_sum[i] = _sum_so_far _sum_so_far = 0 for i in range(1,k+1): _sum_so_far += cardPoints[len(cardPoints) - i] right_card_sum[i] = _sum_so_far for i in range(len(right_card_sum)): max_score = max(max_score,left_card_sum[i]+right_card_sum[len(right_card_sum)-1-i]) return max_score
There's a lack of good formatting here and introducing extra loops makes this way more ambiguous than it has to be. This solution takes the sum of the elements outside of a sliding window, a well-known concept, whereas this just feels spaghettified.
"Guess the Word". It's a weird question for leetcode, it would probably be better with a real interviewer where you could discuss the solution with someone
Not so efficient. But A noob's first intuition. Prefix sum class Solution: def maxScore(self, arr: List[int], k: int) -> int: n = len(arr) arr = arr*2 start = n-k res = 0 for i in range(1,len(arr)): arr[i] += arr[i-1] for i in range(start,n+1): ans = arr[i+k-1] - arr[i-1] res = max(res,ans) return res
Very clever solution. I recreated something similar (in Java) and despite getting 0ms when I hit “run code” I keep getting time limit exceeded after trying to submit it. What gives??
Who and all directly jumped into recursive solution(there were decisions to take either left or right) like me??
This is such a simple solution but so difficult to think of! Jeez. Thank you!
Java solution:
class Solution {
public int maxScore(int[] cardPoints, int k) {
int len = cardPoints.length;
int l = 0, r = len - k;
int total = 0;
for(int i = r ; i < len; i++)
total += cardPoints[i];
int res = total;
while(r < len)
{
total += (cardPoints[l] - cardPoints[r]);
res = Math.max(res, total);
l++;
r++;
}
return res;
}
}
One of the clearest explanations I've seen! Thank you so much
Wonderful explanation! Thank you!
I always search for Neetcode's video while looking for solution of a coding problem.
awesome work, why is this categorized under Greedy? It should be sliding window on Neetcode page, thanks
my easy solution to this question.
initially i just consider first k integers from left.
and then start deleting on element from left and adding one element to right side sum.
and just check which is max sum..
java code below.
class Solution {
public int maxScore(int[] cardPoints, int k) {
int len=cardPoints.length;
int sum=findsum(cardPoints,k);
int maxSum=Math.max(0,sum);
for(int i=1;i
If the length of the cards is n, you need to slide the window n-k times. So the time complexity is O(n) when n is bigger than k. When k^2
Dont think so, what ever is the size of the cards , we need to shift the slider k times, so its O(k)
Hey neetcode, if I use prefix and suffix sum to optimise the brute force approach it may work in O(n), but with 3 passes
The explanantion was detailed and clear. Amazing!! Thank you!
Wow came here struggling with this question and you said this is super easy for Google :( I have my interview on the 15th fingers crossed and thank you for a great explanation
How'd it go?
how did it go ?
brute force is 2^k no?
Yea that’s what I thought
This is so clean and easy to understand. Thank you!
For me it was a hard problem to solve since the key is to see the array as cyclical. I missed that. I went ahead and did a DP:
def maxScore(cards, k):
if k == 1:
return max(cards[0], cards[-1])
@functools.lru_cache(maxsize=None)
def dfs(l, r):
if l + abs(r) - 1 == k:
return 0
left = cards[l] + dfs(l + 1, r)
right = cards[r] + dfs(l, r - 1)
return max(left, right)
return dfs(0, -1)
which works just fine but is no match to the time (and space) complexity of your solution. I guess for me now the problems that DONT fit neatly in the standard categories (trees, dyn. prog etc.) are harder to solve bec. they sneak up on you.
How is this dp? Looks like normal recursion to me
There are a couple of problems like Stone Game that perform well with this approach, I guess the fact that it is only you that is selecting i.e. there isn't another person a clue that we need to think differently ? I did what you did only to TLE
@NeetCode , there are a couple of problems such as Stone Game that perform well with the left & right pointer approach, simulating the entire process in a way.
The fact that it is only you that is selecting i.e. there isn't another person involved in selecting the cards, is that a clue that we need to think differently
? I used left and right pointers with a cache using (l,r) as key, it TLE'd. Would like to know if you thought of that approach as well, trying to understand the intuition behind sliding window :) Great work btw :)
I used left and right pointers as well but when there's [2,2,2] and k=2 I'm getting wrong o/p. idk I'm literally stuck there and everyone's using sliding window that I've no idea of😅
Great explanation! Thank you Neetcode!
Using Prefix Sum array:
class Solution:
def maxScore(self, cardPoints: List[int], k: int) -> int:
forwardPrefixSum = [None] * len(cardPoints)
backwardPrefixSum = [None] * len(cardPoints)
summ = 0
for i in range(len(cardPoints)):
summ += cardPoints[i]
forwardPrefixSum[i] = summ
reversedCardPoints = cardPoints[::-1]
summ = 0
for i in range(len(cardPoints)):
summ += reversedCardPoints[i]
backwardPrefixSum[i] = summ
maxx = max(forwardPrefixSum[k-1], backwardPrefixSum[k-1])
for i in range(1, k):
temp = k - i
t1 = forwardPrefixSum[i-1]
t2 = backwardPrefixSum[temp-1]
print(t1, end=" ")
print(t2)
summ = t1 + t2
maxx = max(maxx, summ)
return maxx
Your explainations are so good...Thanks...
This solution does use extra k space but I feel its more intuitive
class Solution:
def maxScore(self, cardPoints: List[int], k: int) -> int:
left_card_sum = [0]*(k+1)
right_card_sum = [0]*(k+1)
max_score = 0
_sum_so_far = 0
for i in range(1,k+1):
_sum_so_far += cardPoints[i-1]
left_card_sum[i] = _sum_so_far
_sum_so_far = 0
for i in range(1,k+1):
_sum_so_far += cardPoints[len(cardPoints) - i]
right_card_sum[i] = _sum_so_far
for i in range(len(right_card_sum)):
max_score = max(max_score,left_card_sum[i]+right_card_sum[len(right_card_sum)-1-i])
return max_score
There's a lack of good formatting here and introducing extra loops makes this way more ambiguous than it has to be. This solution takes the sum of the elements outside of a sliding window, a well-known concept, whereas this just feels spaghettified.
which is the other question? Great explaination. Thanks :)
"Guess the Word". It's a weird question for leetcode, it would probably be better with a real interviewer where you could discuss the solution with someone
@@NeetCode I have my interview coming up soon, all thanks to you!
Excellent :) Thanks a lot
Wow! that was a really nice explanation! Thank you! 🎉
well explained! Thanks a lot
thank you!
a very beautiful solution
Not so efficient. But A noob's first intuition. Prefix sum
class Solution:
def maxScore(self, arr: List[int], k: int) -> int:
n = len(arr)
arr = arr*2
start = n-k
res = 0
for i in range(1,len(arr)):
arr[i] += arr[i-1]
for i in range(start,n+1):
ans = arr[i+k-1] - arr[i-1]
res = max(res,ans)
return res
What is the logic behind this ?
Great problem.
I thought this problem was Dynamic programming. I would've failed the interview😥.
Very clever solution. I recreated something similar (in Java) and despite getting 0ms when I hit “run code” I keep getting time limit exceeded after trying to submit it. What gives??
It will be better if the solution is available for a java too.
Which is the other most frequently asked google question?
i thought of recursion
U a God
🤯