Stone Game IV - Solution & Explanation
Problem Statement
Alice and Bob take turns playing a game, with Alice starting first.
Initially, there are n stones in a pile. On each player's turn, that player makes a move consisting of removing any non-zero square number of stones in the pile.
Also, if a player cannot make a move, he/she loses the game.
Given a positive integer n, return true if and only if Alice wins the game otherwise return false, assuming both players play optimally.
Example 1:
Input: n = 1 Output: true Explanation: Alice can remove 1 stone winning the game because Bob doesn't have any moves.
Example 2:
Input: n = 2 Output: false Explanation: Alice can only remove 1 stone, after that Bob removes the last one winning the game (2 -> 1 -> 0).
Example 3:
Input: n = 4 Output: true Explanation: n is already a perfect square, Alice can win with one move, removing 4 stones (4 -> 0).
Constraints:
1 <= n <= 105
Approach Overview
Problem Overview: You are given n stones. Two players take turns removing a non‑zero square number of stones (1, 4, 9, 16, ...). The player who cannot make a move loses. Determine whether Alice, who plays first, can force a win if both players play optimally.
Approach 1: Recursive with Memoization (Time: O(n√n), Space: O(n))
This problem fits the classic win/lose state model used in game theory. From a state with n stones, try removing every square number i*i where i*i ≤ n. If any move leads the opponent to a losing state, the current state is winning. A plain recursive search recomputes the same states repeatedly, so store results in a memo table keyed by n. Each state explores at most √n moves and each state is computed once. This reduces the exponential search tree to O(n√n) time while using O(n) memory for memoization.
Approach 2: Dynamic Programming (Bottom-Up) (Time: O(n√n), Space: O(n))
The same win/lose logic can be implemented iteratively using dynamic programming. Define dp[i] as whether the current player wins with i stones remaining. Initialize dp[0] = false since no moves are possible. For each i from 1 to n, iterate over all perfect squares j*j ≤ i. If dp[i - j*j] is false, removing j*j stones forces the opponent into a losing position, so mark dp[i] = true. Each state checks up to √i transitions, leading to overall complexity O(n√n) with O(n) space.
The key insight: a position is winning if at least one move leads to a losing position for the opponent. This pattern appears frequently in impartial combinatorial games and many math and DP problems.
Recommended for interviews: The bottom‑up dynamic programming solution is what most interviewers expect. It demonstrates that you can model the game as a state transition problem and reason about winning vs losing states. Starting with the recursive formulation helps show your thinking, but converting it into iterative DP proves you understand optimization and avoids recursion overhead.
Approach 1: Dynamic Programming Approach
This approach uses Dynamic Programming to determine if Alice can win given n stones. We can maintain a boolean array dp where dp[i] represents whether Alice can win with i stones. A state is winning if there's any move that leaves the opponent in a losing state.
The array dp is initialized with false values. We iterate through each number up to n, checking all possible square numbers we can subtract. If there exists a square number such that the remaining stones leave Bob in a losing position, Alice is in a winning position.
Complexity
Time Complexity: O(n*sqrt(n)), Space Complexity: O(n)
Approach 2: Recursive with Memoization
This approach involves a recursive solution with memoization to cache previously computed results. If n is already solved, we return the cached result. Otherwise, we recursively check if any move leaves the opponent in a losing position.
We use a helper function to recursively determine if a current state is winning while memoizing results for efficiency. The memo array is initialized with -1. For each recursive call, the function checks if removing any square results in a losing state for the opponent.
Complexity
Time Complexity: O(n*sqrt(n)), Space Complexity: O(n)
Approach 3: Default Approach
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Dynamic Programming Approach | Time Complexity: O(n*sqrt(n)), Space Complexity: O(n) |
| Recursive with Memoization | Time Complexity: O(n*sqrt(n)), Space Complexity: O(n) |
| Default Approach | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Naive Recursion | Exponential | O(n) | Conceptual starting point to understand win/lose states in the game tree |
| Recursive with Memoization | O(n√n) | O(n) | Top‑down reasoning when you want a clear recursive definition of the game state |
| Dynamic Programming (Bottom-Up) | O(n√n) | O(n) | Preferred interview solution; efficient iterative computation of all states |
Video Solution
Leetcode 1510. Stone Game IV • Fraz • 7,700 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Stone Game IV easy or hard?
Stone Game IV Python/Java solution
How to solve Stone Game IV in O(n)?
What is the best approach for Stone Game IV?
Is Stone Game IV asked at Google/Amazon/Meta?
What data structure is used in Stone Game IV?
What is the time complexity of Stone Game IV?
Ready to solve this problem?
Practice Stone Game IV with our built-in code editor and test cases.
Practice on FleetCode