Guess Number Higher or Lower II - Solution & Explanation
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.
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.
The code defines a function getMoneyAmount that uses a 2D array dp to store the minimum cost for each subproblem. It iteratively calculates the minimum cost for increasing intervals, considering each number in the interval as a potential guess and calculating the worst-case cost. The main program calls this function with n = 10 and outputs the result.
Complexity
Time Complexity: O(n^3) due to the three nested loops through possible ranges and guesses.
Space Complexity: O(n^2) for storing results of subproblems.
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.
This recursive solution uses a helper function minCost that utilizes memoization to cache results of subproblems in a table dp. The getMoneyAmount function initializes the cache and invokes the helper for the full range from 1 to n, ensuring that calculations are only done once per subproblem.
Complexity
Time Complexity: O(n^2), reduced with memoization.
Space Complexity: O(n^2), for memoizing results.
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,
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Dynamic Programming with Recursion | Time Complexity: O(n^3) due to the three nested loops through possible ranges and guesses. |
| Optimized Recursive Memoization | Time Complexity: O(n^2), reduced with memoization. |
| Dynamic Programming | — |
Detailed 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 |
Video Solution
LeetCode 375. Guess Number Higher or Lower II • Happy Coding • 6,454 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Guess Number Higher or Lower II easy or hard?
How to solve Guess Number Higher or Lower II in O(n)?
Guess Number Higher or Lower II Python or Java solution
Is Guess Number Higher or Lower II asked at Google or Amazon?
What is the best approach for Guess Number Higher or Lower II?
What data structure is used in Guess Number Higher or Lower II?
What is the time complexity of Guess Number Higher or Lower II?
Ready to solve this problem?
Practice Guess Number Higher or Lower II with our built-in code editor and test cases.
Practice on FleetCodeTable of Contents
Practice this problem
Open in Editor