375. Guess Number Higher or Lower II Solution

The problem

We are playing the Guessing Game. The game will work as follows:

I pick a number between 1 and n.
You guess a number.
If you guess the right number, you win the game.
If you guess the wrong number, then I will tell you whether the number I picked is higher or lower, and you will continue guessing.
Every time you guess a wrong number x, you will pay x dollars. If you run out of money, you lose the game.

Given a particular n, return the minimum amount of money you need to guarantee a win regardless of what number I pick.

Example 1:

Input: n = 10
Output: 16
Explanation: The winning strategy is as follows:
- The range is [1,10]. Guess 7.
    - If this is my number, your total is $0. Otherwise, you pay $7.
    - If my number is higher, the range is [8,10]. Guess 9.
        - If this is my number, your total is $7. Otherwise, you pay $9.
        - If my number is higher, it must be 10. Guess 10. Your total is $7 + $9 = $16.
        - If my number is lower, it must be 8. Guess 8. Your total is $7 + $9 = $16.
    - If my number is lower, the range is [1,6]. Guess 3.
        - If this is my number, your total is $7. Otherwise, you pay $3.
        - If my number is higher, the range is [4,6]. Guess 5.
            - If this is my number, your total is $7 + $3 = $10. Otherwise, you pay $5.
            - If my number is higher, it must be 6. Guess 6. Your total is $7 + $3 + $5 = $15.
            - If my number is lower, it must be 4. Guess 4. Your total is $7 + $3 + $5 = $15.
        - If my number is lower, the range is [1,2]. Guess 1.
            - If this is my number, your total is $7 + $3 = $10. Otherwise, you pay $1.
            - If my number is higher, it must be 2. Guess 2. Your total is $7 + $3 + $1 = $11.
The worst case in all these scenarios is that you pay $16. Hence, you only need $16 to guarantee a win.

Example 2:

Input: n = 1
Output: 0
Explanation: There is only one possible number, so you can guess 1 and not have to pay anything.

Example 3:

Input: n = 2
Output: 1
Explanation: There are two possible numbers, 1 and 2.
- Guess 1.
    - If this is my number, your total is $0. Otherwise, you pay $1.
    - If my number is higher, it must be 2. Guess 2. Your total is $1.
The worst case is that you pay $1.

Constraints:

1 <= n <= 200

Approach overview

Problem Overview: You pick a number between 1 and n. Every wrong guess costs the value of the guessed number. The goal is to determine the minimum amount of money required to guarantee a win regardless of which number is chosen.

Approach 1: Recursive Game Simulation (Exponential Time, O(2^n) time, O(n) space)

This problem can be modeled as a minimax game. For each possible guess k between l and r, you pay k and the game continues either in the left range [l, k-1] or the right range [k+1, r]. Since the opponent can force the worst outcome, you take the maximum cost of the two branches. The optimal choice minimizes this worst-case cost across all guesses. A pure recursive solution recomputes the same ranges repeatedly, leading to exponential time complexity.

Approach 2: Dynamic Programming with Memoized Recursion (O(n^3) time, O(n^2) space)

The key observation is that subproblems repeat for the same interval [l, r]. Store results in a 2D DP table where dp[l][r] represents the minimum guaranteed cost for that range. For each interval, iterate every possible pivot k, compute k + max(dp[l][k-1], dp[k+1][r]), and choose the minimum across all pivots. Memoization avoids recomputation and turns the exponential recursion into polynomial time. This approach is a classic interval DP pattern frequently seen in dynamic programming and adversarial decision problems related to game theory. The numeric nature of the cost also ties the reasoning to math based minimax optimization.

Recommended for interviews: Interviewers expect the memoized dynamic programming solution. Start by describing the recursive minimax idea to show understanding of the game strategy. Then introduce memoization or a DP table to remove overlapping subproblems. This demonstrates both problem modeling and optimization skills.

Approach 1: Dynamic Programming with Recursion

This approach involves using dynamic programming with recursion to solve the problem. The main idea is to break the problem into subproblems: determining the cost of guessing any number within a given range. For each number in the current range, calculate the worst-case cost of guessing that number, accounting for both possibilities where the picked number is less or greater than the guessed number. Store solutions to subproblems to avoid recalculating them.

Python

class Solution:
    def getMoneyAmount(self, n: int) -> int:
        dp = [[0] * (n+1) for _ in range(n+1)]
        for length in range(2, n+1):
            for start in range(1, n-length+2):
                min_cost = float('inf')
                for pivot in range(start, start+length-1):
                    cost = pivot + max(dp[start][pivot-1] if pivot > start else 0,
                                       dp[pivot+1][start+length-1] if pivot < start+length-1 else 0)
                    min_cost = min(min_cost, cost)
                dp[start][start+length-1] = min_cost
        return dp[1][n]

if __name__ == "__main__":
    sol = Solution()
    print("Minimum money needed: ", sol.getMoneyAmount(10))

Java

class Solution {
    public int getMoneyAmount(int n) {
        int[][] dp = new int[n + 1][n + 1];
        for (int len = 2; len <= n; len++) {
            for (int start = 1; start <= n - len + 1; start++) {
                int end = start + len - 1;
                int minCost = Integer.MAX_VALUE;
                for (int piv = start; piv <= end; piv++) {
                    int cost = piv + Math.max(piv - 1 >= start ? dp[start][piv - 1] : 0,
                                                piv + 1 <= end ? dp[piv + 1][end] : 0);
                    minCost = Math.min(minCost, cost);
                }
                dp[start][end] = minCost;
            }
        }
        return dp[1][n];
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println("Minimum money needed: " + sol.getMoneyAmount(10));
    }
}

C++

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

int getMoneyAmount(int n) {
    vector<vector<int>> dp(n+1, vector<int>(n+1, 0));
    for (int len = 2; len <= n; ++len) {
        for (int start = 1; start <= n-len+1; ++start) {
            int end = start+len-1;
            int min_cost = INT_MAX;
            for (int piv = start; piv <= end; ++piv) {
                int cost = piv + max(piv-1 >= start ? dp[start][piv-1] : 0,
                                      piv+1 <= end ? dp[piv+1][end] : 0);
                min_cost = min(min_cost, cost);
            }
            dp[start][end] = min_cost;
        }
    }
    return dp[1][n];
}

int main() {
    int n = 10;
    cout << "Minimum amount: " << getMoneyAmount(n) << endl;
    return 0;
}

JavaScript

function getMoneyAmount(n) {
    const dp = Array.from({length: n+1}, () => Array(n+1).fill(0));

    for (let len = 2; len <= n; len++) {
        for (let start = 1; start <= n - len + 1; start++) {
            const end = start + len - 1;
            let minCost = Infinity;
            for (let piv = start; piv <= end; piv++) {
                const cost = piv + Math.max(
                    piv - 1 >= start ? dp[start][piv - 1] : 0,
                    piv + 1 <= end ? dp[piv + 1][end] : 0
                );
                minCost = Math.min(minCost, cost);
            }
            dp[start][end] = minCost;
        }
    }

    return dp[1][n];
}

console.log(`Minimum money needed: ${getMoneyAmount(10)}`);

#include <stdio.h>
#include <string.h>

int getMoneyAmount(int n) {
    int dp[201][201] = {0};

    for (int len = 2; len <= n; ++len) {
        for (int start = 1; start <= n - len + 1; ++start) {
            int minCost = INT_MAX;
            for (int piv = start; piv < start + len - 1; ++piv) {
                int cost = piv + (piv+1 <= start+len-1 ? dp[piv+1][start+len-1] : 0);
                cost = piv > start ? cost + dp[start][piv-1] : cost;
                minCost = minCost < cost ? minCost : cost;
            }
            dp[start][start + len - 1] = minCost;
        }
    }
    return dp[1][n];
}

int main() {
    int n = 10;
    printf("Minimum amount of money to guarantee a win is: %d", getMoneyAmount(n));
    return 0;
}

public class Solution {
    public int GetMoneyAmount(int n) {
        int[,] dp = new int[n + 1, n + 1];
        for (int len = 2; len <= n; len++) {
            for (int start = 1; start <= n - len + 1; start++) {
                int end = start + len - 1;
                int minCost = int.MaxValue;
                for (int piv = start; piv <= end; piv++) {
                    int cost = piv + Math.Max(piv > start ? dp[start, piv - 1] : 0,
                                             piv < end ? dp[piv + 1, end] : 0);
                    minCost = Math.Min(minCost, cost);
                }
                dp[start, end] = minCost;
            }
        }
        return dp[1, n];
    }

    public static void Main(string[] args) {
        Solution sol = new Solution();
        Console.WriteLine("Minimum money needed: " + sol.GetMoneyAmount(10));
    }
}

The Python solution closely follows the dynamic programming paradigm. The function getMoneyAmount initializes a 2D array to hold the minimum expenses for each subproblem. It iterates over all possible intervals and pivot choices, updating the dp table with minimized worst-case scenario costs. The function ultimately returns the answer at dp[1][n].

Complexity

Time Complexity: O(n^3)
Space Complexity: O(n^2)

Try this approach in the editor

Approach 2: Optimized Recursive Memoization

A more advanced recursive approach with memoization achieves similar results, storing results of previously solved subproblems in a cache for fast retrieval. This is especially useful for large inputs, reducing computational overhead by avoiding repeated calculations of the same conditions and ranges.

Python

class Solution:
    def __init__(self):
        self.dp = []

    def minCost(self, start, end):
        if start >= end:
            return 0
        if self.dp[start][end] != 0:
            return self.dp[start][end]
        res = float('inf')
        for piv in range(start, end + 1):
            cost = piv + max(self.minCost(start, piv - 1), self.minCost(piv + 1, end))
            res = min(res, cost)
        self.dp[start][end] = res
        return res

    def getMoneyAmount(self, n: int) -> int:
        self.dp = [[0] * (n + 1) for _ in range(n + 1)]
        return self.minCost(1, n)

if __name__ == "__main__":
    sol = Solution()
    print("Minimum amount to guarantee a win: ", sol.getMoneyAmount(10))

Java

class Solution {
    int[][] dp;

    private int minCost(int start, int end) {
        if (start >= end) return 0;
        if (dp[start][end] != 0) return dp[start][end];
        int res = Integer.MAX_VALUE;
        for (int piv = start; piv <= end; piv++) {
            int cost = piv + Math.max(minCost(start, piv - 1), minCost(piv + 1, end));
            res = Math.min(res, cost);
        }
        dp[start][end] = res;
        return res;
    }

    public int getMoneyAmount(int n) {
        dp = new int[n+1][n+1];
        return minCost(1, n);
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println("Minimum amount to guarantee a win: " + sol.getMoneyAmount(10));
    }
}

C++

#include <iostream>
#include <vector>
using namespace std;

vector<vector<int>> dp;

int minCost(int start, int end) {
    if (start >= end) return 0;
    if (dp[start][end] != -1) return dp[start][end];
    int res = INT_MAX;
    for (int piv = start; piv <= end; ++piv) {
        int cost = piv + max(minCost(start, piv - 1), minCost(piv + 1, end));
        res = min(res, cost);
    }
    return dp[start][end] = res;
}

int getMoneyAmount(int n) {
    dp.assign(n+1, vector<int>(n+1, -1));
    return minCost(1, n);
}

int main() {
    cout << "Minimum amount to guarantee a win: " << getMoneyAmount(10) << endl;
    return 0;
}

JavaScript

const memo = {};

function minCost(start, end) {
    if (start >= end) return 0;
    const key = `${start},${end}`;
    if (memo[key] !== undefined) return memo[key];
    let res = Infinity;

    for (let piv = start; piv <= end; piv++) {
        const cost = piv + Math.max(
            piv - 1 >= start ? minCost(start, piv - 1) : 0,
            piv + 1 <= end ? minCost(piv + 1, end) : 0
        );
        res = Math.min(res, cost);
    }
    memo[key] = res;
    return res;
}

function getMoneyAmount(n) {
    return minCost(1, n);
}

console.log(`Minimum amount to guarantee a win: ${getMoneyAmount(10)}`);

#include <stdio.h>
#include <string.h>
#define MAXN 201

int dp[MAXN][MAXN];

int minCost(int start, int end) {
    if (start >= end) return 0;
    if (dp[start][end] != 0) return dp[start][end];
    int res = 1e9;
    for (int piv = start; piv <= end; ++piv) {
        int cost = piv + (piv > start ? minCost(start, piv - 1) : 0) +
                   (piv < end ? minCost(piv + 1, end) : 0);
        res = res < cost ? res : cost;
    }
    dp[start][end] = res;
    return res;
}

int getMoneyAmount(int n) {
    memset(dp, 0, sizeof(dp));
    return minCost(1, n);
}

int main() {
    int n = 10;
    printf("Minimum amount to guarantee a win: %d", getMoneyAmount(n));
    return 0;
}

public class Solution {
    private int[,] dp;

    private int MinCost(int start, int end) {
        if (start >= end) return 0;
        if (dp[start, end] != 0) return dp[start, end];
        int res = int.MaxValue;
        for (int piv = start; piv <= end; piv++) {
            int cost = piv + Math.Max(MinCost(start, piv - 1), MinCost(piv + 1, end));
            res = Math.Min(res, cost);
        }
        dp[start, end] = res;
        return res;
    }

    public int GetMoneyAmount(int n) {
        dp = new int[n+1, n+1];
        return MinCost(1, n);
    }

    public static void Main(string[] args) {
        Solution sol = new Solution();
        System.Console.WriteLine("Minimum amount to guarantee a win: " + sol.GetMoneyAmount(10));
    }
}

In this Python approach, memoization is achieved using an instance class variable dp initialized to zeros. The recursive function ensures subproblems are evaluated only once per unique input values, avoiding overlapping calculations and thus improving efficiency.

Complexity

Time Complexity: O(n^2), reduced with memoization.
Space Complexity: O(n^2), requiring storage for memoized subproblem results.

Try this approach in the editor

Approach 3: Dynamic Programming

We define f[i][j] as the minimum cost required to guess any number in the interval [i, j]. Initially, f[i][i] = 0 because there is no cost to guess the only number, and for i > j, we also have f[i][j] = 0. The answer is f[1][n].

For f[i][j], we can enumerate any number k in [i, j], divide the interval [i, j] into two parts, [i, k - 1] and [k + 1, j], choose the larger value of the two parts plus the cost of k,

TypeScript

function getMoneyAmount(n: number): number {
    const f: number[][] = Array.from({ length: n + 1 }, () => Array(n + 1).fill(0));
    for (let i = n - 1; i; --i) {
        for (let j = i + 1; j <= n; ++j) {
            f[i][j] = j + f[i][j - 1];
            for (let k = i; k < j; ++k) {
                f[i][j] = Math.min(f[i][j], k + Math.max(f[i][k - 1], f[k + 1][j]));
            }
        }
    }
    return f[1][n];
}

func getMoneyAmount(n int) int {
	f := make([][]int, n+1)
	for i := range f {
		f[i] = make([]int, n+1)
	}
	for i := n - 1; i > 0; i-- {
		for j := i + 1; j <= n; j++ {
			f[i][j] = j + f[i][j-1]
			for k := i; k < j; k++ {
				f[i][j] = min(f[i][j], k+max(f[i][k-1], f[k+1][j]))
			}
		}
	}
	return f[1][n]
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Dynamic Programming with Recursion	Time Complexity: O(n^3) Space Complexity: O(n^2)
Optimized Recursive Memoization	Time Complexity: O(n^2), reduced with memoization. Space Complexity: O(n^2), requiring storage for memoized subproblem results.
Dynamic Programming	–

Complexity analysis

Approach	Time	Space	When to Use
Pure Recursive Game Simulation	O(2^n)	O(n)	Conceptual understanding of the minimax decision process before optimization
Dynamic Programming with Memoized Recursion	O(n^3)	O(n^2)	Standard interview solution that removes overlapping subproblems
Optimized Recursive Memoization	O(n^3)	O(n^2)	Same DP strategy with pruning and cleaner recursion for practical implementations

Frequently asked questions

Is Guess Number Higher or Lower II easy or hard?

Guess Number Higher or Lower II is generally rated Medium on LeetCode but can feel difficult if you are new to interval dynamic programming. The challenge comes from recognizing the minimax strategy and defining the correct DP state for ranges.

How to solve Guess Number Higher or Lower II in O(n)?

An O(n) solution is not known for this problem because every interval must consider multiple possible pivots to guarantee the minimum worst-case cost. The accepted optimal approach is interval dynamic programming with O(n^3) time complexity.

Guess Number Higher or Lower II Python or Java solution

Python and Java implementations typically use recursion with memoization. A 2D array or dictionary caches results for dp[l][r], and each recursive step evaluates all possible pivot guesses while choosing the minimum worst-case cost.

Is Guess Number Higher or Lower II asked at Google or Amazon?

Variants of this problem appear in interviews that test dynamic programming and minimax reasoning. Companies such as Google, Amazon, and Meta commonly ask interval DP or game-theory style problems where you must minimize the worst-case outcome.

What is the best approach for Guess Number Higher or Lower II?

The best approach uses dynamic programming with memoized recursion. Define dp[l][r] as the minimum guaranteed cost to guess a number within the range [l, r]. For each possible guess k, compute k + max(dp[l][k-1], dp[k+1][r]) and choose the minimum across all k. This ensures the lowest worst‑case cost.

What data structure is used in Guess Number Higher or Lower II?

The core data structure is a 2D dynamic programming table dp[l][r]. It stores the minimum guaranteed cost for each interval of numbers. The algorithm also relies on recursion or iterative DP to evaluate ranges.

What is the time complexity of Guess Number Higher or Lower II?

The optimal dynamic programming solution runs in O(n^3) time and O(n^2) space. There are O(n^2) subranges and each range tries up to n pivot guesses. Memoization prevents repeated calculations for the same intervals.

Guess Number Higher or Lower II solution and explanation

The problem

Approach overview

Approach 1: Dynamic Programming with Recursion

Approach 2: Optimized Recursive Memoization

Approach 3: Dynamic Programming

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Guess Number Higher or Lower II solution and explanation

The problem

Approach overview

Approach 1: Dynamic Programming with Recursion

Approach 2: Optimized Recursive Memoization

Approach 3: Dynamic Programming

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems