LeetCode 375: Guess Number Higher or Lower II Solution in Python – A Step-by-Step Guide

What Is LeetCode 375: Guess Number Higher or Lower II?

LeetCode 375: Guess Number Higher or Lower II gives you an integer n, and you need to determine the minimum amount of money required to guarantee finding a hidden number between 1 and n using the guess(num) API (from LeetCode 374), where each wrong guess costs num dollars. The goal is to find the worst-case minimum cost. It’s a step up from LeetCode 374, adding a cost-minimization layer!

Problem Statement

• Input:
• n: Integer representing the upper bound of the range (1 to n).
• Output: Integer - Minimum money needed to guarantee finding the number.
• API:
• guess(num): Returns -1 (num > pick), 1 (num < pick), 0 (num == pick).
• Rules:
• Each wrong guess costs num dollars.
• Minimize the maximum cost over all possible picks.
• Number is between 1 and n.

Constraints

• 1 <= n <= 200

Examples

• Input: n = 10
• Output: 16
• Optimal strategy costs 16 in worst case (e.g., guess 4, then adjust).
• Input: n = 1
• Output: 0
• Only 1 possible, no guesses needed.
• Input: n = 2
• Output: 1
• Guess 1: If wrong (cost 1), pick is 2; worst case is 1.

These show the cost strategy—let’s solve it!

Understanding the Problem: Minimizing Worst-Case Cost

To tackle LeetCode 375 in Python, we need to: 1. Find a strategy to guess a number between 1 and n. 2. Minimize the maximum total cost across all possible picks. 3. Use the guess API implicitly via cost calculation.

A naive approach might try all strategies, but that’s exponential. Instead, we’ll use:

• Best Solution: Dynamic programming with minimax—O(n³) time, O(n²) space—fast and optimal.
• Alternative Solution: Recursive minimax—O(2ⁿ) time, O(n) space—intuitive but slow.

Let’s strategize with the best solution!

Best Solution: Dynamic Programming with Minimax

Why This Is the Best Solution

The dynamic programming with minimax approach runs in O(n³) time by breaking the problem into subproblems, using a 2D DP table to store the minimum cost for each range [i, j]. It’s the most efficient—balancing worst-case costs with memoization to avoid exponential exploration!

How It Works

Think of it like a game strategy:

• DP Table: dp[i][j] = minimum cost to guarantee finding a number in range [i, j].
• Minimax: For each guess x in [i, j]:
• Cost = x + max(dp[i][x-1], dp[x+1][j]) (worst-case subproblem).
• Minimize this over all x.
• Base Cases: dp[i][i] = 0 (one number, no cost), dp[i][i-1] = 0 (empty range).
• Result: dp[1][n] is the answer.

It’s like planning the cheapest worst-case path!

Step-by-Step Example

For n = 4:

• Range: [1, 2, 3, 4].
• DP Table: dp[i][j] for i to j.
• Base Cases: dp[1][1] = 0, dp[2][2] = 0, dp[3][3] = 0, dp[4][4] = 0.
• Length 1: dp[1][2], dp[2][3], dp[3][4]:
• dp[1][2]: Guess 1 (cost 1 + dp[2][2] = 1), Guess 2 (cost 2 + dp[1][1] = 2), min(1, 2) = 1.
• dp[2][3]: Guess 2 (2 + 0 = 2), Guess 3 (3 + 0 = 3), min(2, 3) = 2.
• dp[3][4]: Guess 3 (3 + 0 = 3), Guess 4 (4 + 0 = 4), min(3, 4) = 3.
• Length 2: dp[1][3], dp[2][4]:
• dp[1][3]:
• Guess 1: 1 + max(dp[2][3], dp[1][0]) = 1 + 2 = 3.
• Guess 2: 2 + max(dp[1][1], dp[3][3]) = 2 + 0 = 2.
• Guess 3: 3 + max(dp[1][2], dp[4][4]) = 3 + 1 = 4.
• min(3, 2, 4) = 2.
• dp[2][4]: Guess 2 (2 + 3 = 5), Guess 3 (3 + 2 = 5), Guess 4 (4 + 0 = 4), min(5, 5, 4) = 4.
• Length 3: dp[1][4]:
• Guess 1: 1 + max(dp[2][4], dp[1][0]) = 1 + 4 = 5.
• Guess 2: 2 + max(dp[1][1], dp[3][4]) = 2 + 3 = 5.
• Guess 3: 3 + max(dp[1][2], dp[4][4]) = 3 + 1 = 4.
• Guess 4: 4 + max(dp[1][3], dp[5][4]) = 4 + 2 = 6.
• min(5, 5, 4, 6) = 4.
• Result: dp[1][4] = 4.

Code with Explanation

Here’s the Python code using DP with minimax:

Copy codeclass Solution:
    def getMoneyAmount(self, n: int) -> int:
        # DP table: dp[i][j] = min cost to guess in range [i, j]
        dp = [[0] * (n + 1) for _ in range(n + 1)]

        # Fill DP table for all lengths
        for length in range(1, n):
            for start in range(1, n - length + 1):
                end = start + length
                dp[start][end] = float('inf')

                # Try each number as the guess
                for guess in range(start, end + 1):
                    # Cost = guess + max cost of left or right subproblem
                    left_cost = dp[start][guess - 1] if guess > start else 0
                    right_cost = dp[guess + 1][end] if guess < end else 0
                    total_cost = guess + max(left_cost, right_cost)
                    dp[start][end] = min(dp[start][end], total_cost)

        return dp[1][n]

Explanation

• Line 4: dp: 2D table, dp[i][j] for range [i, j], initialized to 0.
• Lines 6-15: Fill DP table:
• Iterate over lengths 1 to n-1.
• For each start, compute end = start + length.
• For each guess in [start, end]:
• Left cost: dp[start][guess-1] (0 if guess=start).
• Right cost: dp[guess+1][end] (0 if guess=end).
• Total = guess + max(left, right), minimize over all guesses.
• Line 17: Return dp[1][n], cost for full range.
• Time: O(n³)—O(n²) subproblems, O(n) guesses each.
• Space: O(n²)—DP table.

This is like a cost-minimizing strategist—plan the cheapest worst case!

Alternative Solution: Recursive Minimax

Why an Alternative Approach?

The recursive minimax solution runs in O(2ⁿ) time without memoization, exploring all possible guess sequences. It’s slower but shows the raw game theory approach—great for small n or understanding the logic!

How It Works

• Recurse: For range [start, end], try each guess, compute max cost of subproblems.
• Minimize: Take min over all guesses.
• Base: Single or empty range costs 0.

Step-by-Step Example

For n = 3:

• Range: [1, 2, 3].
• Guess 1: 1 + max(cost(2-3), cost(0)) = 1 + 2 = 3.
• Guess 2: 2 + max(cost(1-1), cost(3-3)) = 2 + 0 = 2.
• Guess 3: 3 + max(cost(1-2), cost(4-3)) = 3 + 1 = 4.
• Min: min(3, 2, 4) = 2.
• Result: 2.

Code with Explanation

Copy codeclass Solution:
    def getMoneyAmount(self, n: int) -> int:
        # Recursive helper
        def minimax(start, end):
            if start >= end:
                return 0  # Base case: single or empty range

            min_cost = float('inf')
            for guess in range(start, end + 1):
                left_cost = minimax(start, guess - 1)
                right_cost = minimax(guess + 1, end)
                total_cost = guess + max(left_cost, right_cost)
                min_cost = min(min_cost, total_cost)
            return min_cost

        return minimax(1, n)

Explanation

• Lines 3-14: minimax:
• Base case: start ≥ end, return 0.
• For each guess, compute max cost of left and right subranges.
• Total cost = guess + max(left, right), minimize over guesses.
• Line 16: Call for full range [1, n].
• Time: O(2ⁿ)—exponential without memoization.
• Space: O(n)—recursion stack.

It’s like guessing all paths—intuitive but slow!

Comparing the Two Solutions

• DP with Minimax (Best):
• Time: O(n³)—cubic DP.
• Space: O(n²)—table.
• Pros: Fast, scalable.
• Cons: Complex setup.
• Recursive Minimax (Alternative):
• Time: O(2ⁿ)—exponential.
• Space: O(n)—stack.
• Pros: Clear logic.
• Cons: Impractical for large n.

DP wins for efficiency!

Additional Examples and Edge Cases

• n=1: 0 (no guesses).
• n=5: 8 (optimal strategy).
• Large n: DP scales, recursion doesn’t.

DP handles all efficiently.

Complexity Breakdown

• DP:
• Time: O(n³).
• Space: O(n²).
• Recursive:
• Time: O(2ⁿ).
• Space: O(n).

DP excels for performance.

Key Takeaways

• DP Minimax: Optimize costs—fast and smart!
• Recursive: Explore all—clear but slow!
• Game Theory: Strategy matters.
• Python Tip: DP rocks—see [Python Basics](/python/basics).

Final Thoughts: Minimize That Cost

LeetCode 375: Guess Number Higher or Lower II in Python is a cost-strategy challenge. DP with minimax is the efficiency champ, while recursive minimax builds intuition. Want more? Try LeetCode 374: Guess Number Higher or Lower or LeetCode 486: Predict the Winner. Ready to strategize? Visit Solve LeetCode 375 on LeetCode and guess that number today!