Scale Engineer

Guess Number Higher or Lower II

Med
#0362Time: O(n^3). The three nested loops for `len`, `i`, and `k` dominate the runtime. `len` runs up to `n`, `i` runs up to `n`, and `k` runs up to `n` times in the worst case.Space: O(n^2), for the 2D DP table.
Patterns
MathDynamic ProgrammingGame Theory

Prompt

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

  1. I pick a number between 1 and n.
  2. You guess a number.
  3. If you guess the right number, you win the game.
  4. 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.
  5. 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

Approaches

3 approaches with complexity analysis and trade-offs.

This approach solves the problem iteratively using bottom-up dynamic programming, also known as tabulation. It avoids recursion and its associated overhead, often leading to better performance. We use a 2D table, dp[i][j], to store the minimum cost to guarantee a win for the number range [i, j]. The key idea is to fill this table by starting with the smallest subproblems (ranges of length 2) and progressively building up to the solution for the full range [1, n]. By iterating through range lengths, we ensure that when we calculate dp[i][j], the solutions for all smaller, required subproblems (like dp[i][k-1] and dp[k+1][j]) have already been computed and stored in the table.

Algorithm

  1. Create a 2D DP table dp of size (n+2) x (n+2) and initialize all its values to 0. The extra padding helps handle boundary cases like k-1 and k+1 without extra checks.
  2. Iterate over the length of the range, len, from 2 to n.
  3. Inside this loop, iterate over all possible starting points i for a range of length len. The loop for i will go from 1 up to n - len + 1.
  4. Calculate the end point of the current range: j = i + len - 1.
  5. For the current range [i, j], initialize its cost dp[i][j] to Integer.MAX_VALUE.
  6. Iterate through all possible first guesses k from i to j.
  7. For each guess k, calculate the cost using the already computed values from smaller sub-ranges: cost = k + max(dp[i][k-1], dp[k+1][j]).
  8. Update the minimum cost for the range [i, j]: dp[i][j] = min(dp[i][j], cost).
  9. After all loops complete, the value dp[1][n] will contain the minimum cost to guarantee a win for the entire range [1, n]. Return this value.

Walkthrough

Instead of starting from the top problem (1, n) and breaking it down, the bottom-up approach starts with the smallest problems and builds up. We use a 2D array dp[n+2][n+2] where dp[i][j] stores the solution for the subproblem on the range [i, j]. The base cases are ranges of length 0 or 1, for which the cost is 0. Our DP table is initialized to 0, which covers these cases. We then iterate on the length of the range, len, from 2 to n. For each len, we iterate through all possible start indices i. The end index j is simply i + len - 1. For each range [i, j], we calculate dp[i][j] by trying every possible split point k (our first guess) from i to j. The cost for guessing k is k + max(dp[i][k-1], dp[k+1][j]). Since we are iterating by increasing length, the values dp[i][k-1] (for range length k-i) and dp[k+1][j] (for range length j-k) are guaranteed to have been computed in previous iterations. We take the minimum cost over all possible k. The final answer is the value stored in dp[1][n].

public class Solution {    public int getMoneyAmount(int n) {        if (n == 1) {            return 0;        }        // dp[i][j] = min cost for range [i, j]        int[][] dp = new int[n + 2][n + 2];         for (int len = 2; len <= n; len++) {            for (int i = 1; i <= n - len + 1; i++) {                int j = i + len - 1;                dp[i][j] = Integer.MAX_VALUE;                for (int k = i; k <= j; k++) {                    int cost = k + Math.max(dp[i][k - 1], dp[k + 1][j]);                    dp[i][j] = Math.min(dp[i][j], cost);                }            }        }         return dp[1][n];    }}

Complexity

Time

O(n^3). The three nested loops for `len`, `i`, and `k` dominate the runtime. `len` runs up to `n`, `i` runs up to `n`, and `k` runs up to `n` times in the worst case.

Space

O(n^2), for the 2D DP table.

Trade-offs

Pros

  • Generally the most efficient solution for the given constraints due to the absence of recursion overhead.

  • Iterative nature can make it easier to analyze and debug.

  • Guarantees the optimal solution.

Cons

  • Can be slightly less intuitive to formulate than the recursive top-down approach.

  • Still has a cubic time complexity, which might be too slow for much larger constraints.

Solutions

class Solution {public  int getMoneyAmount(int n) {    int[][] dp = new int[n + 10][n + 10];    for (int l = 2; l <= n; ++l) {      for (int i = 1; i + l - 1 <= n; ++i) {        int j = i + l - 1;        dp[i][j] = Integer.MAX_VALUE;        for (int k = i; k <= j; ++k) {          int t = Math.max(dp[i][k - 1], dp[k + 1][j]) + k;          dp[i][j] = Math.min(dp[i][j], t);        }      }    }    return dp[1][n];  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem