Stone Game II - Leetcode 1140 - Python

Solving leetcode 1140 - Stone Game II, today's daily leetcode problem on may 25.
🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🥷 Discord: / discord
🐦 Twitter: / neetcode1
🐮 Support the channel: / neetcode
⭐ BLIND-75 PLAYLIST: • Two Sum - Leetcode 1 -...
💡 DYNAMIC PROGRAMMING PLAYLIST: • House Robber - Leetco...
Problem Link: leetcode.com/problems/stone-g...
0:00 - Read the problem
0:30 - Drawing explanation
9:15 - Code Solution
17:35 - Time Complexity
leetcode 1140
#neetcode #leetcode #python

[@ary_21]

At 11:42 i realised Alice and Bob are playing with me and not with each other

[@MP-ny3ep]

Phenomenal explanation. Thank you!

[@RomanFalcon13]

Thank you king, keep it up!

[@reckyru]

DP is pain and makes me cry

[@uptwist2260]

Thanks for the daily

[@Calypso1406]

idk how to come up with these kinds of solutions and im genuinely lost

[@saagerbabung5652]

In Google interview, do they accept memorization solution or it has to be only tabulation form for a DP problem?

[@kotik1221]

Do you have this code snippet somewhere? I want to read the code in my own editor.

[@user-le6ts6ci7h]

The time complexity you mentioned is not correct, m might at the worst go up to log(n)

[@ayo4590]

Hi Neetocde, I was thinking of buying your course but as a broke college student the price is a bit too expensive as a yearly payment. Can you add a monthly payment option? i'll prefer having to pay even more than the current price (like over a year) if the monthly is low enough because i know it's really worth it.

[@NeetCodeIO]

Feel free to email me at neetcodebusiness@gmail

[@liangyu3771]

life saver. I could not understand the question (sad)

[@user-rm6vf9zm1t]

take inspirations from your stone gameIII solution, I tried to calculate the max diff of Alice -Bob, then return the sum of piles - diff divided by 2, it works!

[@gangstacoder4234]

hey i tried that too...can you elaborate or paste the code (if possible)

[@user-rm6vf9zm1t]

@@gangstacoder4234
var stoneGameII = function (piles) {
let cache = new Map()
let sum = piles.reduce((acu, cur) => acu + cur, 0)
function dfs(i, M) {
if (i >= piles.length) {
return 0
}
if (cache.has(`${i}|${M}`)) {
return cache.get(`${i}|${M}`)
}
let res = -Infinity
let total = 0
for (let j = i; j < 2 * M + i; j++) {
if (j >= piles.length) {
break
}
total += piles[j]
res = Math.max(res, total - dfs(j + 1, Math.max(M, j - i + 1)))
}
cache.set(`${i}|${M}`, res)
return res
}
let diff = dfs(0, 1)
return (sum + diff) / 2
};

[@tofahub]

This one is more helpful@@user-rm6vf9zm1t

[@business_central]

Could anyone please clarify to me why use "not Alice" in both Alice & Bob's turn ? (in the res calculations) ? I really just didn't get that specific point.
Otherwise all clear as usual! Thank you Neetcode!

[@ADITYA-fk1zy]

consider initilally alice = True (it means its alice turn now),when we say " not alice " it will become bob's turn right because not alice will be false now,simillarly if its bobs turn now it means alice variable must be false ,so next turn would be alice so
"not alice " will become true in that case.
In simple terms if its alice's turn "alice == true",else if its bob's turn "alice == false"
hope you understand.

[@business_central]

@@ADITYA-fk1zy Thank you for trying to clarify!
The main point of confusion for me, is that when we are calculating the result for Alice, we do a dfs for Bob's turn therefore dfs(not Alice, etc.) - This part quite clear-
The problem is when we are doing bob's result and doing the dfs for the following turn (which is Alice) why aren't we doing dfs( Alice) that's where I am still a bit confused

[@codertrucker3296]

@@business_central Because when you are doing bob's result, the current Alice is False, so for the following turn (which is Alice) the Alice has to be True, then you need a (!Alice) to turn Alice to True.

[@business_central]

@@codertrucker3296 that was my understanding, but when we do that it would be wrong.
We have to have dfs(not alice) for both, when next turn is Bob's and when the next one is Alice's.

[@NeetCodeIO]

The not just takes the negation. So not True -> False. not False -> True.
This is a pretty trivial feature of any programming language. I would test it out in an ide yourself if you don't believe that it works.

[@6kostia]

Nice solution, but it's better to ignore Bob's existence, Alice plays against herself as Bob and Alice are actually the same player.

[@ivanzaplatar9033]

This is what I was thinking. What would the recurrence relation be?

[@6kostia]

@@ivanzaplatar9033 res = max(res, (sum(piles[i:])- dfs(i + x, max(x, m))))
It actually runs faster, around 200 ms

[@NeetCodeIO]

Does the sum(piles[I:]) run in O(n) time? I believe that may affect the overall time complexity

[@ADITYA-fk1zy]

​@@NeetCodeIO we pre-compute the suffixsum in a array and use that array so it's O(1) to get sum.

[@MohddAlii]

Why are you minimising at bob's turn, Will bob not play optimally?

[@lakshmanvengadesan9096]

Bob is minimizing the score of Alice, not his score

[@parashararamesh4252]

This is similar to the minimax algorithm so you can refer to that as well.
If you think about it the function only returns Alice's maximum value and in that recursion of that function it will be bobs turn as well ( also remember bob is not the starting player). So from Alice's perspective Bob would have to minimise his score for Alice to get the best score.
If Bob also maximises his score then it could probably result in Bob having more stones even though he only starts second

[@alek4001]

@@parashararamesh4252 No, they both play optimally. It's just the same thing - minimizing opponents score or maximizing owns. Bob minimizes Alice score == maximizes his own.

[@eku333]

@@lakshmanvengadesan9096 Holy shit this comment should be pinned

[@johnnychang3456]

Bob will get Alice's score from the recursive call, of which he'll select the minimum one.

[@MrKB_SSJ2]

Yeeeeeeee

[@meghasharma_0419]

Hey guys
I tried to implement this solution in js as follows
var stoneGameII = function(piles) {
//this problem can be solved using recursion with caching
let dp = {}
//the dfs has 3 parameters -
//alice - to keep track of who is playing alice or bob
//i to keep track of index we are at in piles
//M defined in problem statement as we can only choose piles between index i to 2M i.e eithier the first pile or the first two pile or first 3 pile so on....
//this function returns the no of stones alice gets
const dfs = (alice,i,M) =>{
//Base cases
if(i === piles.length)
return 0
if((alice,i,M) in dp)
return dp[(alice,i,M)]
//if it is alice turn we maximize the result , if it is bob's turn we minimize the result(stones alice gets) as both players play optimally
let res = alice ? 0 : Number.MAX_SAFE_INTEGER
let total = 0
for(let x = 1; xpiles.length)
break
//we subtract 1 as x begins at 1 and we wanna consider the ith pile too
total += piles[i+x-1]
console.log(total)
//Now we wanna make the dfs call
if(alice){
res = Math.max(res, total+dfs(false,i+x,Math.max(M,x)))
}
else{
//since the function returns alice stone so we do not add bob stones (total ) in case bob is playing
res = Math.min(res,dfs(true,i+x, Math.max(M,x)))
}
}
dp[(alice, i, M)] = res
return res
}
return dfs(true,0,1)
};
But i m getting wrong answer
Can anyone help

[@prashantshubham]

Issue is with your hash map i.e `dp` implementation

[@meghasharma_0419]

@@prashantshubham Thanks