Guess Number Higher or Lower II - Video Solutions
LeetCode 375. Guess Number Higher or Lower II
Guess Number Higher or Lower II - Video Solution
Watch 10 video solutions for Guess Number Higher or Lower II, a medium level problem involving Math, Dynamic Programming, Game Theory. This walkthrough by Happy Coding has 6,454 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
We are playing the Guessing Game. The game will work as follows:
- I pick a number between
1andn. - 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 payxdollars. 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.
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 |