375. Guess Number Higher or Lower II
Problem Description
Imagine you're playing a guessing game where the objective is to figure out a hidden number and you want to spend as little money as possible in the process. In this game, you will guess numbers between 1 and n
, and each incorrect guess will cost you the value of the guess in dollars. If you get it right, you win! If you get it wrong, you'll be told if the hidden number is higher or lower than your guess. You want to know the least amount of money required to guarantee a win no matter what number is chosen by your opponent.
Intuition
The approach to solve this problem is to use dynamic programming, a method where we break the problem down into simpler subproblems and build up a solution to the larger problem based on the solutions to the smaller problems.
This problem requires a strategy to minimize the total cost while guaranteeing a win. To achieve this, we need to consider all possible outcomes and make the best worst-case decision at each guess. We think of the game in terms of ranges (from 1 to n
) and then narrow down the range based on whether we need to guess higher or lower. This approach will help us figure out the minimum cost required to win the game.
We use a 2D array dp
to record the cost to guarantee a win for every range [i, j]
. The cost of the guess k
is the maximum between dp[i][k-1]
(if the number is lower than k
) and dp[k+1][j]
(if the number is higher than k
) plus the cost k
of making the guess. Since we want to minimize our cost, we take the minimum over all possible k
's for the range [i, j]
. The answer is then dp[1][n]
since it's the minimum amount of money required to guarantee a win for the full range.
Learn more about Math and Dynamic Programming patterns.
Solution Approach
The implementation leverages the concept of dynamic programming to develop a strategy that ensures the minimum cost of a guaranteed win. Here's how the solution is built:
-
Dynamic Programming Table Initialization: Create a 2-dimensional array
dp
wheredp[i][j]
represents the minimum cost to guarantee a win for the range[i, j]
. The size of the array is(n + 10)
by(n + 10)
to cover all the possible ranges between1
andn
, with a bit of extra space to avoid index out-of-bounds errors. -
Filling the DP Table: Iterate over all the possible lengths
l
of the ranges from2
ton+1
. For each length, compute the minimum cost for all ranges of that length starting from1
. -
Computing Costs: For each range
[i, j]
with the starting pointi
and the endpointj
, initialize the minimum costdp[i][j]
to infinity as a starting point. Then, try every possible guessk
within the range[i, j]
. For each guess, calculate the costt
, which is the maximum of either guessing too low (dp[i][k - 1]
) or too high (dp[k + 1][j]
), plus the costk
of making the current guess. -
Minimizing Costs: The value of
dp[i][j]
is updated to the minimum cost out of all the guessesk
. -
Result Extraction: After populating the
dp
table with the costs for all ranges, the minimum cost to guarantee a win for the full range from1
ton
is found indp[1][n]
.
The algorithm uses a bottom-up strategy, solving smaller range problems first and using their solutions to address larger ranges. This ensures that at every step, the optimal (minimum) cost for the current range is based on the best decisions made for the previous smaller ranges.
This approach ensures that we achieve a global optimum by making locally optimal choices, thanks to the overlapping subproblems and optimal substructure properties of dynamic programming.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's illustrate the solution approach using a small example. Suppose n = 4
, so the hidden number is between 1 and 4, and we want to find the minimum amount of money required to guarantee a win.
Step 1: Dynamic Programming Table Initialization
We initialize a 2D array dp
that has 5x5 dimensions since n
is 4 and we add 1 to have an inclusive range.
Initially, dp
looks like this (with 0s where no cost is involved):
1dp = [ 2 [0, 0, 0, 0, 0], 3 [0, 0, 0, 0, 0], 4 [0, 0, 0, 0, 0], 5 [0, 0, 0, 0, 0], 6 [0, 0, 0, 0, 0], 7]
Step 2: Filling the DP Table
We consider ranges of lengths from 2 to 5.
Step 3: Computing Costs
When the length is 2, we consider ranges: [1, 2]
, [2, 3]
, [3, 4]
. For example, for the range [1, 2]
, we can guess 1 or 2. If we guess 1 and the number is 2, we lose $1 and then pay $2 to guess correctly, which sums to $3. If we guess 2 and the number is 1, we lose $2 but then just pay $1 to guess it correctly, summing to $3. So, the minimum cost here is $3.
The table looks partially like this:
1dp = [ 2 [0, 0, 0, 0, 0], 3 [0, 0, 3, 0, 0], 4 [0, 0, 0, 3, 0], 5 [0, 0, 0, 0, 3], 6 [0, 0, 0, 0, 0], 7]
Step 4: Minimizing Costs
We move to ranges of length 3 and 4 and update dp
accordingly. Take range [1, 3]
. Our guesses are 1, 2, or 3:
- Guess 1: If it's wrong, we lose 1, and the minimum cost to guess between [2, 3] is \3 (from step 3). So, total cost = $1 + $3 = $4.
- Guess 2: If it's wrong, we can face a higher or lower number, resulting in a cost of max([1], [3]) = $2 (always correct on the second guess, 1 or 3). So, total cost = $2 + $2 = $4.
- Guess 3: Similar to guessing 1, total cost = $4.
Therefore, the cost to guarantee a win between [1, 3]
is $4.
We proceed similarly for all lengths. Finally, for length 4, the range [1, 4]
has multiple scenarios and we select the minimum cost of all.
Step 5: Result Extraction
After computing all possible ranges, our dp
array for the range [1, n]
(which is [1, 4]
in our example) gives us the answer. For this example, dp[1][4]
will end up being the minimum cost to guarantee a win for the game.
By building the solution from the smallest range to the largest and choosing the minimum cost at each step, we ensure the minimum amount of money required to guarantee a win for the entire range. This example uses smaller numbers for simplicity, but the actual implementation would handle larger values of n
following the same process.
Solution Implementation
1class Solution:
2 def getMoneyAmount(self, n: int) -> int:
3 # Initialize the dynamic programming (DP) table with 0's and add extra space to avoid index out of range
4 dp_table = [[0] * (n + 10) for _ in range(n + 10)]
5
6 # Loop over the lengths of the ranges of numbers we are considering
7 for length in range(2, n + 1):
8 # Start index of the current range
9 for start in range(1, n - length + 2):
10 # End index of the current range
11 end = start + length - 1
12
13 # Initialize the DP table entry with infinity to later find the minimum cost
14 dp_table[start][end] = float('inf')
15
16 # Check each possible number (k) to guess within the current range
17 for k in range(start, end + 1):
18 # The cost of guessing k includes the cost of the worst scenario from both sides
19 # of the range split by k, plus the cost of guessing k
20 cost_when_guessing_k = max(dp_table[start][k - 1], dp_table[k + 1][end]) + k
21
22 # Update the DP table for the current range with the minimum cost amongst all k's
23 dp_table[start][end] = min(dp_table[start][end], cost_when_guessing_k)
24
25 # The answer is the minimum cost to guess the number in range 1...n
26 return dp_table[1][n]
27
1class Solution {
2 public int getMoneyAmount(int n) {
3 // Initialize the dynamic programming table.
4 // dp[i][j] represents the minimum amount of money required to
5 // guarantee a win for guessing the number between i and j.
6 int[][] dp = new int[n + 1][n + 1];
7
8 // Fill the table using the bottom-up dynamic programming approach.
9 // 'l' represents the range size from i to j.
10 for (int l = 2; l <= n; ++l) {
11 // 'i' is the lower bound of the range.
12 for (int i = 1; i + l - 1 <= n; ++i) {
13 // 'j' is the upper bound of the range.
14 int j = i + l - 1;
15 // Initialize the value to maximum it could possibly be.
16 dp[i][j] = Integer.MAX_VALUE;
17
18 // Test all possible guesses 'k' from i to j and
19 // take the cost of the most unfortunate (worst-case) outcome.
20 for (int k = i; k <= j; ++k) {
21 // The cost is calculated as the higher cost of two scenarios:
22 // * the cost of guessing a number too low and then solving the range [k+1, j].
23 // * the cost of guessing a number too high and then solving the range [i, k-1].
24 // Then add the cost 'k' of making the guess itself.
25 int cost = Math.max(dp[i][k - 1], dp[k + 1][j]) + k;
26 // Find the minimum cost among all possible guesses 'k'.
27 dp[i][j] = Math.min(dp[i][j], cost);
28 }
29 }
30 }
31 // The answer is the minimum cost to guarantee a win when the range is from 1 to n.
32 return dp[1][n];
33 }
34}
35
1#include <vector>
2#include <climits> // For INT_MAX
3
4class Solution {
5public:
6 int getMoneyAmount(int n) {
7 // Initialize a 2D vector dp where dp[i][j] represents the minimal amount
8 // of money required to guarantee a win when guessing numbers between i and j.
9 std::vector<std::vector<int>> dp(n + 1, std::vector<int>(n + 1));
10
11 // Length of the range we are considering. Starts at 2 since a single number range requires no guesses.
12 for (int length = 2; length <= n; ++length) {
13 for (int start = 1; start <= n - length + 1; ++start) {
14 int end = start + length - 1;
15
16 // Initialize the dp value for the range [start, end] to the highest possible value.
17 dp[start][end] = INT_MAX;
18
19 // Try every possible guess (pick 'k') from the range [start, end].
20 for (int k = start; k <= end; ++k) {
21 // Compute the cost when choosing 'k'. It is the higher cost of the two ranges
22 // split by 'k' (since we're minimizing the worst-case scenario) plus the cost of 'k'.
23 int costWhenPickingK = k + std::max(
24 k > start ? dp[start][k - 1] : 0, // Cost of the left subrange if k is not the start
25 k < end ? dp[k + 1][end] : 0 // Cost of the right subrange if k is not the end
26 );
27
28 // Update the minimal cost for the range [start, end].
29 dp[start][end] = std::min(dp[start][end], costWhenPickingK);
30 }
31 }
32 }
33
34 // Return the minimal amount of money required to guarantee a win for the range [1, n].
35 return dp[1][n];
36 }
37};
38
1// Importing module for max safe integer constant.
2import { MAX_SAFE_INTEGER } from "constants";
3
4// Initializes a 2D array 'dp' where dp[i][j] represents the minimal amount
5// of money required to guarantee a win when guessing numbers between i and j.
6const dp: number[][] = [];
7
8// Method that calculates the minimal amount of money required to guarantee a win.
9function getMoneyAmount(n: number): number {
10 // Initialize 'dp' with the appropriate dimensions and fill it with zeros.
11 for (let i = 0; i <= n; i++) {
12 dp[i] = new Array(n + 1).fill(0);
13 }
14
15 // Analyzing different range lengths, starting from length 2 since a single number requires no guess.
16 for (let length = 2; length <= n; length++) {
17 // Iterating over each possible starting point of the range.
18 for (let start = 1; start <= n - length + 1; start++) {
19 const end = start + length - 1;
20
21 // Initialize the 'dp' value for this range to the highest safe integer to ensure minimization.
22 dp[start][end] = MAX_SAFE_INTEGER;
23
24 // Iterate over every possible number 'k' within the current range to simulate a guess.
25 for (let k = start; k <= end; k++) {
26 // Calculate the cost of picking number 'k', which is k plus the highest cost between the two subranges.
27 const costWhenPickingK = k + Math.max(
28 k > start ? dp[start][k - 1] : 0, // Cost for the left subrange, if 'k' is not at the start.
29 k < end ? dp[k + 1][end] : 0 // Cost for the right subrange, if 'k' is not at the end.
30 );
31
32 // Store the minimum cost between the current and the calculated cost for this range.
33 dp[start][end] = Math.min(dp[start][end], costWhenPickingK);
34 }
35 }
36 }
37
38 // Return the minimal amount of money to guarantee a win for the full range of numbers.
39 return dp[1][n];
40}
41
42// Example usage: calculate the minimal amount needed to guarantee a win from 1 to 10.
43console.log(getMoneyAmount(10));
44
Time and Space Complexity
Time Complexity
The time complexity of the provided code is O(n^3)
. This is because there are three nested loops: the outermost loop ranges over l
, which goes from 2
to n
; the second loop ranges over i
, which goes from 1
to n - l + 1
. For each combination of i
and l
, the innermost loop ranges over k
, which goes from i
to j
(where j = i + l - 1
). For each value of k
, the code computes t
which involves querying and updating values in the dp
array, which takes constant time. The number of iterations is roughly n
for the i
loop, n
for the l
loop, and n
again for the k
loop, multiplying together for a cubic time complexity.
Space Complexity
The space complexity of the code is O(n^2)
. We allocate a dp
array that has n + 10
rows and n + 10
columns to ensure that we do not index out of bounds when performing dynamic programming. Though not all of these entries are used, the overall space required is proportional to n^2
since the bulk of the space is occupied by the n * n
subarray required to calculate the minimum cost for guessing the number.
Learn more about how to find time and space complexity quickly using problem constraints.
How would you design a stack which has a function min
that returns the minimum element in the stack, in addition to push
and pop
? All push
, pop
, min
should have running time O(1)
.
Recommended Readings
Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you
What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.