LeetCode 375 - Guess Number Higher or Lower II

This problem is a variant of the classic number guessing game with a twist: incorrect guesses cost money equal to the value guessed, and the goal is to minimize the maximum cost required to guarantee a win.

leetcodemediummathdynamic-programminggame-theory

LeetCode Problem 375

Difficulty: 🟡 Medium
Topics: Math, Dynamic Programming, Game Theory

Solution

Problem Understanding

This problem is a variant of the classic number guessing game with a twist: incorrect guesses cost money equal to the value guessed, and the goal is to minimize the maximum cost required to guarantee a win. In other words, we want a strategy that ensures we will always find the correct number while spending the least money in the worst-case scenario.

The input n represents the upper bound of the number range [1, n]. The output is the minimum amount of money required to guarantee a win regardless of which number is picked. If n = 1, no money is needed since there is only one choice. For n = 2, we need $1, as guessing 1 first could result in paying 1 if the number is 2.

Constraints are 1 <= n <= 200, which is small enough to allow a dynamic programming solution. Edge cases include n = 1 (trivial, cost = 0), n = 2 (simple calculation), and the upper limit n = 200, which tests the efficiency of the approach.

The main challenge is that a naive strategy, such as always guessing the middle number, does not account for the cost of each guess, which varies depending on the number guessed. The solution must consider both the value of the guess and the potential worst-case costs in the remaining ranges.

Approaches

Brute Force Approach

The brute force approach tries every possible first guess in the range [start, end], then recursively calculates the worst-case cost of the two resulting subranges (numbers lower than the guess and numbers higher than the guess). For each guess x, the cost is:

cost(x) = x + max(cost(start, x-1), cost(x+1, end))

The minimum of these costs across all guesses is the result for that range. This guarantees correctness because it considers all possible strategies, but the recursive calls result in exponential time complexity O(2^n) due to overlapping subproblems, which is too slow for n = 200.

Optimal Approach

The key observation is that the problem exhibits optimal substructure and overlapping subproblems, making it ideal for dynamic programming. By memoizing results of subranges [start, end], we avoid redundant calculations. The DP solution uses a 2D table dp[start][end] representing the minimum cost to guarantee a win in that subrange. Each entry is filled iteratively or recursively with memoization.

The transition is the same as brute force:

dp[start][end] = min(
    x + max(dp[start][x-1], dp[x+1][end]) for x in range(start, end+1)
)

Memoization reduces the complexity dramatically to O(n^3) because for each of the O(n^2) subranges, we try O(n) possible guesses.

Approach Time Complexity Space Complexity Notes
Brute Force O(2^n) O(n) Recursively try every possible guess without memoization
Optimal (DP) O(n^3) O(n^2) Memoize subrange results to avoid recomputation

Algorithm Walkthrough

  1. Initialize a DP table: Create a 2D array dp of size (n+1) x (n+1) where dp[start][end] stores the minimum guaranteed cost for numbers in the range [start, end]. Initially, all entries are 0.
  2. Iterate over range lengths: Start with small subranges and gradually increase the length of the range, because the cost of a range depends on smaller subranges.
  3. Consider all possible guesses: For each range [start, end], try every guess x in the range. The cost of guessing x is x plus the maximum cost of the two resulting subranges: [start, x-1] and [x+1, end].
  4. Update the DP table: Take the minimum of all possible guesses for that range and store it in dp[start][end].
  5. Return the final result: dp[1][n] gives the minimum amount of money to guarantee a win for the full range.

Why it works: The algorithm works because it uses dynamic programming to exhaustively consider all ranges and all possible first guesses while storing the optimal costs. By taking the maximum of the two subranges, it ensures the solution accounts for the worst-case scenario, and taking the minimum over all guesses ensures we find the strategy that minimizes this maximum cost.

Python Solution

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):
                end = start + length - 1
                dp[start][end] = float('inf')
                for x in range(start, end + 1):
                    left = dp[start][x - 1] if x - 1 >= start else 0
                    right = dp[x + 1][end] if x + 1 <= end else 0
                    cost = x + max(left, right)
                    dp[start][end] = min(dp[start][end], cost)
                    
        return dp[1][n]

The implementation initializes a DP table, iterates over subrange lengths, and fills each cell based on the minimum worst-case cost from all possible first guesses. It handles edge cases such as start == end (cost 0) naturally, as dp[start][start] = 0 by initialization.

Go Solution

func getMoneyAmount(n int) int {
    dp := make([][]int, n+1)
    for i := range dp {
        dp[i] = make([]int, n+1)
    }
    
    for length := 2; length <= n; length++ {
        for start := 1; start <= n-length+1; start++ {
            end := start + length - 1
            dp[start][end] = 1 << 30 // large number
            for x := start; x <= end; x++ {
                left := 0
                if x-1 >= start {
                    left = dp[start][x-1]
                }
                right := 0
                if x+1 <= end {
                    right = dp[x+1][end]
                }
                cost := x + max(left, right)
                if cost < dp[start][end] {
                    dp[start][end] = cost
                }
            }
        }
    }
    
    return dp[1][n]
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

The Go solution mirrors the Python approach, using slices instead of lists and initializing a large number to simulate infinity. Edge cases are handled similarly, and the max function is used to compare subrange costs.

Worked Examples

Example 1: n = 10

Step Range Guess x Left Right Cost dp[start][end]
1 [1,2] 1 0 0 1 1
2 [1,3] 2 1 0 2 2
3 [1,10] 7 dp[1,6]=10 dp[8,10]=6 7+max(10,6)=17 dp[1,10]=16 (after checking all guesses)

The DP table systematically computes every subrange, ensuring the final result for [1,10] is 16, as described in the problem.

Example 2: n = 1

Only one number, cost = 0.

Example 3: n = 2

dp[1][2] = 1 because guessing 1 first gives a worst-case cost of 1 if the number is 2.

Complexity Analysis

Measure Complexity Explanation
Time O(n^3) For each of the O(n^2) subranges, we try O(n) possible guesses
Space O(n^2) DP table of size (n+1) x (n+1) stores results for all subranges

The cubic time complexity is feasible for n <= 200 because it results in around 8 million operations, which is manageable for modern processors. Space usage is quadratic due to storing all subrange results.

Test Cases

# test cases
assert Solution().getMoneyAmount(10) == 16  # Example 1
assert Solution().getMoneyAmount(1) == 0    # Example 2
assert Solution().getMoneyAmount(2) == 1    # Example 3
assert Solution().getMoneyAmount(3) == 2    # Small n, 3 numbers
assert Solution().getMoneyAmount(4) == 4    # Small n, testing DP for even numbers
assert Solution().getMoneyAmount(20) == 49  # Larger range
assert Solution().getMoneyAmount(200) >= 0  # Upper bound stress test

| Test