Stone Game IV solution and explanation
9 more videos on this problem
Leetcode 1510. Stone Game IVFraz · 11:06 · 7K views
Stone Game IV Leetcode 1510. Dynamic Programming Code C++ + ExplanationCode with Alisha · 11:17 · 2K views
Stone Game IV | Leetcode 1510 | Game Theory | DPAyushi Sharma · 11:27 · 2K views
Stone Game IV | Live Coding with Explanation | Leetcode - 1510Algorithms Made Easy · 14:18 · 1K views
1510. Stone Game IV (Leetcode Problem)viralSongs · 6:35 · 947 views
Stone Game IV | Leetcode 1510 |Live coding session 🔥🔥🔥🔥 | Dynamic ProgrammingCoding Decoded · 12:12 · 866 views
Stone Game IV | Leet code 1510 | Theory explained + Python codeSai Anish Malla · 19:10 · 703 views
Stone Game 4 Leetcode | Leetcode 1510 | Recursive + Top Down + Bottom Up Approach explainedCode Bashers · 14:20 · 373 views
Daily Leetcode #661 part 2: Jan 21, 2022 - 1510. Stone Game IVProgramming Live with Larry · 12:50 · 335 views
Leetcode - Stone Game IV (Python)Timothy H Chang · 6:20 · 302 views
The problem
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.
import math
def winnerSquareGame(n):
dp = [False] * (n + 1)
for i in range(1, n + 1):
for k in range(1, int(math.sqrt(i)) + 1):
if not dp[i - k * k]:
dp[i] = True
break
return dp[n]import java.util.*;
public class Solution {
public boolean winnerSquareGame(int n) {
boolean[] dp = new boolean[n + 1];
for (int i = 1; i <= n; i++) {
for (int k = 1; k * k <= i; k++) {
if (!dp[i - k * k]) {
dp[i] = true;
break;
}
}
}
return dp[n];
}
}#include <vector>
#include <cmath>
using namespace std;
bool winnerSquareGame(int n) {
vector<bool> dp(n + 1, false);
for (int i = 1; i <= n; ++i) {
for (int k = 1; k * k <= i; ++k) {
if (!dp[i - k * k]) {
dp[i] = true;
break;
}
}
}
return dp[n];
}var winnerSquareGame = function(n) {
const dp = new Array(n + 1).fill(false);
for (let i = 1; i <= n; i++) {
for (let k = 1; k * k <= i; k++) {
if (!dp[i - k * k]) {
dp[i] = true;
break;
}
}
}
return dp[n];
};#include <stdbool.h>
#include <math.h>
bool winnerSquareGame(int n) {
bool dp[n+1];
for (int i = 0; i <= n; ++i) {
dp[i] = false;
}
for (int i = 1; i <= n; ++i) {
for (int k = 1; k*k <= i; ++k) {
if (!dp[i-k*k]) {
dp[i] = true;
break;
}
}
}
return dp[n];
}using System;
public class Solution {
public bool WinnerSquareGame(int n) {
bool[] dp = new bool[n + 1];
for (int i = 1; i <= n; i++) {
for (int k = 1; k * k <= i; k++) {
if (!dp[i - k * k]) {
dp[i] = true;
break;
}
}
}
return dp[n];
}
}We initialize a boolean list dp and iterate through each state, marking it as winning if there exists a move that forces the opponent into a losing position.
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.
def winnerSquareGame(n):
memo = [-1] * (n + 1)
def isWinning(x):
if x == 0:
return False
if memo[x] != -1:
return memo[x]
for k in range(1, int(x ** 0.5) + 1):
if not isWinning(x - k*k):
memo[x] = True
return True
memo[x] = False
return False
return isWinning(n)import java.util.*;
public class Solution {
public boolean winnerSquareGame(int n) {
Boolean[] memo = new Boolean[n + 1];
return isWinning(n, memo);
}
private boolean isWinning(int n, Boolean[] memo) {
if (n == 0) return false;
if (memo[n] != null) return memo[n];
for (int k = 1; k * k <= n; ++k) {
if (!isWinning(n - k * k, memo)) {
return memo[n] = true;
}
}
return memo[n] = false;
}
}#include <vector>
#include <cmath>
bool isWinning(int n, std::vector<int>& memo) {
if (n == 0) return false;
if (memo[n] != -1) return memo[n];
for (int k = 1; k * k <= n; ++k) {
if (!isWinning(n - k * k, memo)) {
return memo[n] = true;
}
}
return memo[n] = false;
}
bool winnerSquareGame(int n) {
std::vector<int> memo(n+1, -1);
return isWinning(n, memo);
}var winnerSquareGame = function(n) {
let memo = new Array(n + 1).fill(-1);
const isWinning = function(x) {
if (x === 0) return false;
if (memo[x] !== -1) return memo[x];
for (let k = 1; k * k <= x; k++) {
if (!isWinning(x - k * k)) {
memo[x] = true;
return true;
}
}
memo[x] = false;
return false;
}
return isWinning(n);
};#include <stdbool.h>
#include <math.h>
#include <string.h>
bool isWinning(int n, bool *memo) {
if (n == 0) return false;
if (memo[n] != -1) return memo[n];
for (int k = 1; k * k <= n; ++k) {
if (!isWinning(n - k * k, memo)) {
return memo[n] = true;
}
}
return memo[n] = false;
}
bool winnerSquareGame(int n) {
bool memo[n+1];
memset(memo, -1, sizeof(memo));
return isWinning(n, memo);
}using System;
public class Solution {
public bool WinnerSquareGame(int n) {
int?[] memo = new int?[n + 1];
return IsWinning(n, memo);
}
private bool IsWinning(int n, int?[] memo) {
if (n == 0) return false;
if (memo[n] != null) return memo[n] == 1;
for (int k = 1; k * k <= n; ++k) {
if (!IsWinning(n - k * k, memo)) {
memo[n] = 1;
return true;
}
}
memo[n] = 0;
return false;
}
}This Python function defines a helper to recursively check if there's a move that forces the opponent into a losing state. Previously computed results are stored in memo, enhancing efficiency through reduced redundant calculations.
Time Complexity: O(n*sqrt(n)), Space Complexity: O(n)
Approach 3: Default Approach
function winnerSquareGame(n: number): boolean {
const f: number[] = new Array(n + 1).fill(0);
const dfs = (i: number): boolean => {
if (i <= 0) {
return false;
}
if (f[i] !== 0) {
return f[i] === 1;
}
for (let j = 1; j * j <= i; ++j) {
if (!dfs(i - j * j)) {
f[i] = 1;
return true;
}
}
f[i] = -1;
return false;
};
return dfs(n);
}func winnerSquareGame(n int) bool {
f := make([]int, n+1)
var dfs func(int) bool
dfs = func(i int) bool {
if i <= 0 {
return false
}
if f[i] != 0 {
return f[i] == 1
}
for j := 1; j <= i/j; j++ {
if !dfs(i - j*j) {
f[i] = 1
return true
}
}
f[i] = -1
return false
}
return dfs(n)
}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 | – |
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 |
Frequently asked questions
Is Stone Game IV easy or hard?
Stone Game IV is classified as Hard on LeetCode even though the implementation is short. The difficulty comes from recognizing the game theory pattern and modeling the problem as DP with winning and losing states.
Stone Game IV Python/Java solution
Both Python and Java implementations typically use a DP array of size n+1. For each index i, iterate through j*j ≤ i and mark dp[i] true if dp[i - j*j] is false. The same logic works across languages including C++, JavaScript, and C#.
How to solve Stone Game IV in O(n)?
A strict O(n) solution is not commonly used for this problem because each state must consider multiple square moves. The standard optimal approach checks all perfect squares ≤ n for every state, resulting in O(n√n) time using dynamic programming.
What is the best approach for Stone Game IV?
Dynamic Programming is the most reliable approach. Define dp[i] as whether the current player wins with i stones. For each i, try removing every square number j*j ≤ i and check if dp[i - j*j] is false. If such a move exists, dp[i] becomes true. This runs in O(n√n) time with O(n) space.
Is Stone Game IV asked at Google/Amazon/Meta?
Stone Game style problems frequently appear in interviews at companies like Google, Amazon, and Meta because they test reasoning about game states, recursion, and dynamic programming. Variants of this problem are commonly used to evaluate understanding of optimal play strategies.
What data structure is used in Stone Game IV?
The core data structure is a boolean DP array or memoization map that stores whether a state with i stones is winning or losing. The algorithm iterates through perfect squares and performs constant-time lookups in this table.
What is the time complexity of Stone Game IV?
The optimal solution runs in O(n√n) time. For each state from 1 to n, the algorithm iterates through all square numbers up to √n. The space complexity is O(n) for storing the DP or memoization table.