Problem editorial

Guess Number Higher or Lower

EasyBinary Search PatternsBinary SearchInteractive

Editorial

Core insight

Guess Number Higher or Lower · Binary Search Patterns

Core Insight for Guess Number Higher or Lower

The key intuition behind the LeetCode 374 solution lies in the sorted nature of the input range. Since the numbers are sequential, they possess a monotonic property: if a number $x$ is greater than the target pick, then all numbers greater than $x$ are also greater than pick.

When we guess a number mid, the API provides one of three states:

Guess is too high (-1): The target must be in the lower half (numbers smaller than mid). We can safely discard mid and everything larger.
Guess is too low (1): The target must be in the upper half (numbers larger than mid). We can safely discard mid and everything smaller.
Guess is correct (0): We found the target.

This allows us to maintain an invariant: the target pick is always contained within our current search window [left, right]. By selecting the middle element, we ensure the search space decreases by a factor of 2 with each iteration.

Visual Description: Imagine the search space as a horizontal line segment from 1 to n. We place pointers at the start (L) and end (R). We calculate the midpoint M.

If the target is to the left of M, the new search space becomes the segment [L, M-1].
If the target is to the right of M, the new search space becomes the segment [M+1, R].
This process repeats, visually shrinking the line segment rapidly until it converges on a single point.

Deep dive

Full breakdown

Full reasoning, pitfalls, and implementation flow

LeetCode 374: Guess Number Higher or Lower Solution & Explanation

Problem Overview

TL;DR: The optimal solution utilizes Binary Search to locate the target number in $O(\log n)$ time by systematically halving the search range based on the API's feedback.

In the Guess Number Higher or Lower problem, we are given a range of integers from 1 to n. One specific number in this range, called pick, has been selected. Our goal is to identify this number by making guesses. We are provided with a pre-defined API guess(int num) which returns feedback indicating if our guess was too high, too low, or correct. This is a classic interactive problem often seen in technical interviews, and the LeetCode 374 solution serves as a foundational example of logarithmic search algorithms.

Brute Force Approach for Guess Number Higher or Lower

The most straightforward way to solve this problem is to check every possible number starting from 1 up to n until we find the correct one.

Naive Algorithm:

Start a loop with a variable i ranging from 1 to n.
For each i, call the API guess(i).
If the API returns 0, we have found the number pick. Return i.

Pseudo-code:

text

for i from 1 to n:
    if guess(i) == 0:
        return i

Time Complexity Analysis: The time complexity is $O(n)$ . In the worst-case scenario, if the picked number is n, we will have to call the guess API n times.

Why it Fails: The constraint for n goes up to $2^{31} - 1$ (approximately 2 billion). A linear scan performing 2 billion operations will inevitably result in a Time Limit Exceeded (TLE) error. We need an approach that drastically reduces the number of API calls.

Algorithm Strategy: Binary Search Patterns

We implement the standard binary search algorithm to solve this efficiently.

Initialization: Define two pointers, left initialized to 1 and right initialized to n. These define the current search boundaries.
Loop Condition: Continue the search as long as left <= right.
Midpoint Calculation: Calculate the middle index mid. To prevent integer overflow, use the formula mid = left + (right - left) / 2.
API Interaction: Call guess(mid) and store the result.
Branching Logic:
- If the result is -1 (guess > pick), the target is smaller. Move the right boundary to mid - 1.
- If the result is 1 (guess < pick), the target is larger. Move the left boundary to mid + 1.
- If the result is 0, return mid.

Execution Flow

Let's trace the algorithm with n = 10 and pick = 6.

Initialize: left = 1, right = 10.
Iteration 1:
- Calculate mid = 1 + (10 - 1) / 2 = 5.
- Call guess(5). Since 5 < 6, API returns 1 (guess is lower than pick).
- Update left = mid + 1 = 6. New range: [6, 10].
Iteration 2:
- Calculate mid = 6 + (10 - 6) / 2 = 8.
- Call guess(8). Since 8 > 6, API returns -1 (guess is higher than pick).
- Update right = mid - 1 = 7. New range: [6, 7].
Iteration 3:
- Calculate mid = 6 + (7 - 6) / 2 = 6.
- Call guess(6). Since 6 == 6, API returns 0.
- Return 6.

Proof of Correctness

The algorithm is correct because it maintains the invariant that the target pick must exist within the range [left, right].

Initially, pick is in [1, n].
In each step, we eliminate a half that strictly cannot contain pick based on the API's return value.
Since the range size decreases monotonically and is finite, the loop must terminate.
Because pick is guaranteed to exist (per problem constraints), the condition guess(mid) == 0 will eventually be met.

Pattern Reuse Notes

The Binary Search pattern used here is fundamental and applies to many other problems.

LeetCode 35: Search Insert Position - Uses the same logic to find where an element belongs in a sorted array.
LeetCode 69: Sqrt(x) - Applies binary search on the answer space (integers) to find a square root.
LeetCode 74: Search a 2D Matrix - Treats a matrix as a flattened sorted list to perform binary search.
LeetCode 278: First Bad Version - Almost identical to Guess Number, finding the first true in a boolean sequence.

Feynman coach · Before you peek at the code

Can you explain the core insight in your own words?

If you can explain it before reading code, you’re far more likely to recall it under interview pressure.

Loading your attempt…

Reference Implementation

C++ Solution for LeetCode 374

cpp

1/** 
2 * Forward declaration of guess API.
3 * @param  num   your guess
4 * @return 	     -1 if num is higher than the picked number
5 *			      1 if num is lower than the picked number
6 *               otherwise return 0
7 * int guess(int num);
8 */
9
10class Solution {
11public:
12    int guessNumber(int n) {
13        int left = 1;
14        int right = n;
15        
16        while (left <= right) {
17            // Prevent integer overflow
18            int mid = left + (right - left) / 2;
19            
20            int res = guess(mid);
21            
22            if (res == 0) {
23                return mid;
24            } else if (res == -1) {
25                // Guess is higher than pick, so pick is smaller
26                right = mid - 1;
27            } else {
28                // Guess is lower than pick, so pick is larger
29                left = mid + 1;
30            }
31        }
32        
33        return -1; // Should not reach here
34    }
35};

Java Solution for LeetCode 374

java

1/** 
2 * Forward declaration of guess API.
3 * @param  num   your guess
4 * @return 	     -1 if num is higher than the picked number
5 *			      1 if num is lower than the picked number
6 *               otherwise return 0
7 * int guess(int num);
8 */
9
10public class Solution extends GuessGame {
11    public int guessNumber(int n) {
12        int left = 1;
13        int right = n;
14        
15        while (left <= right) {
16            // Prevent integer overflow during addition
17            int mid = left + (right - left) / 2;
18            
19            int res = guess(mid);
20            
21            if (res == 0) {
22                return mid;
23            } else if (res == -1) {
24                // My guess is too high, target is lower
25                right = mid - 1;
26            } else {
27                // My guess is too low, target is higher
28                left = mid + 1;
29            }
30        }
31        
32        return -1; // Should not be reached
33    }
34}

Python Solution for LeetCode 374

python

1# The guess API is already defined for you.
2# @param num, your guess
3# @return -1 if num is higher than the picked number
4#          1 if num is lower than the picked number
5#          otherwise return 0
6# def guess(num):
7
8class Solution:
9    def guessNumber(self, n: int) -> int:
10        left = 1
11        right = n
12        
13        while left <= right:
14            # Standard binary search mid calculation
15            mid = left + (right - left) // 2
16            
17            res = guess(mid)
18            
19            if res == 0:
20                return mid
21            elif res == -1:
22                # Guess is too high, look in the lower half
23                right = mid - 1
24            else:
25                # Guess is too low, look in the upper half
26                left = mid + 1
27                
28        return -1

AI Coach Insight

For Guess Number Higher or Lower, focus on explaining why the structure works, not just naming Binary Search Patterns.

Complexity Analysis

Time Complexity: $O(\log n)$ The search space is reduced by half in every iteration. The number of steps required to reduce a range of size $n$ to 1 is $\log_2 n$ . For the maximum $n \approx 2 \times 10^9$ , this takes roughly 31 iterations.

Space Complexity: $O(1)$ We only use a constant amount of extra space for the variables left, right, and mid. No recursive stack space is used in the iterative implementation.

Related Patterns

Pattern: Binary Search Patterns
Subpattern: Binary Search - On Sorted Array/List

This problem fits the Binary Search pattern perfectly because the search space consists of a sorted sequence of integers ( $1, 2, \dots, n$ ). The feedback provided by the API (higher/lower) allows us to determine the relative position of the target, enabling us to discard half of the remaining candidates in every step.

Common Mistakes & FAQ

Why does my solution get Time Limit Exceeded (TLE)?
- Mistake: Using a linear search (looping 1 to n) or failing to update left and right correctly in the binary search (e.g., setting left = mid instead of mid + 1), causing an infinite loop.
- Reason: Linear search is $O(n)$ , which is too slow for $n=2^{31}$ . Infinite loops prevent termination.
- Consequence: The code runs until the time limit is reached.
Why does my binary search fail on large inputs?
- Mistake: Calculating the midpoint as (left + right) / 2.
- Reason: When left and right are both large (near $2^{31}$ ), their sum exceeds the maximum integer limit, causing an integer overflow.
- Consequence: The mid value becomes negative or incorrect, leading to index out of bounds or logic errors. Always use left + (right - left) / 2.
Why is my logic reversed?
- Mistake: Misinterpreting the API return values -1 and 1.
- Reason: The problem states -1 means "Your guess is higher than the picked number". This implies the target is lower, so we must move right. It is easy to confuse this with "The target is higher".
- Consequence: The search moves in the wrong direction, eventually eliminating the correct answer and failing to find the target.

Practise Guess Number Higher or Lower and the problems around it

Guess Number Higher or Lower is a Binary Search Patterns problem, in the On Sorted Array/List subpattern. Once the approach above makes sense, write it yourself and then work through the neighbouring problems that reuse it.

Core insight

Guess Number Higher or Lower · Binary Search Patterns

Core Insight for Guess Number Higher or Lower

When we guess a number mid, the API provides one of three states:

Guess is too high (-1): The target must be in the lower half (numbers smaller than mid). We can safely discard mid and everything larger.
Guess is too low (1): The target must be in the upper half (numbers larger than mid). We can safely discard mid and everything smaller.
Guess is correct (0): We found the target.

Visual Description: Imagine the search space as a horizontal line segment from 1 to n. We place pointers at the start (L) and end (R). We calculate the midpoint M.

If the target is to the left of M, the new search space becomes the segment [L, M-1].
If the target is to the right of M, the new search space becomes the segment [M+1, R].
This process repeats, visually shrinking the line segment rapidly until it converges on a single point.

Deep dive

Full breakdown

Full reasoning, pitfalls, and implementation flow

LeetCode 374: Guess Number Higher or Lower Solution & Explanation

Problem Overview

TL;DR: The optimal solution utilizes Binary Search to locate the target number in $O(\log n)$ time by systematically halving the search range based on the API's feedback.

Brute Force Approach for Guess Number Higher or Lower

The most straightforward way to solve this problem is to check every possible number starting from 1 up to n until we find the correct one.

Naive Algorithm:

Start a loop with a variable i ranging from 1 to n.
For each i, call the API guess(i).
If the API returns 0, we have found the number pick. Return i.

Pseudo-code:

text

for i from 1 to n:
    if guess(i) == 0:
        return i

Time Complexity Analysis: The time complexity is $O(n)$ . In the worst-case scenario, if the picked number is n, we will have to call the guess API n times.

Algorithm Strategy: Binary Search Patterns

We implement the standard binary search algorithm to solve this efficiently.

Initialization: Define two pointers, left initialized to 1 and right initialized to n. These define the current search boundaries.
Loop Condition: Continue the search as long as left <= right.
Midpoint Calculation: Calculate the middle index mid. To prevent integer overflow, use the formula mid = left + (right - left) / 2.
API Interaction: Call guess(mid) and store the result.
Branching Logic:
- If the result is -1 (guess > pick), the target is smaller. Move the right boundary to mid - 1.
- If the result is 1 (guess < pick), the target is larger. Move the left boundary to mid + 1.
- If the result is 0, return mid.

Execution Flow

Let's trace the algorithm with n = 10 and pick = 6.

Initialize: left = 1, right = 10.
Iteration 1:
- Calculate mid = 1 + (10 - 1) / 2 = 5.
- Call guess(5). Since 5 < 6, API returns 1 (guess is lower than pick).
- Update left = mid + 1 = 6. New range: [6, 10].
Iteration 2:
- Calculate mid = 6 + (10 - 6) / 2 = 8.
- Call guess(8). Since 8 > 6, API returns -1 (guess is higher than pick).
- Update right = mid - 1 = 7. New range: [6, 7].
Iteration 3:
- Calculate mid = 6 + (7 - 6) / 2 = 6.
- Call guess(6). Since 6 == 6, API returns 0.
- Return 6.

Proof of Correctness

The algorithm is correct because it maintains the invariant that the target pick must exist within the range [left, right].

Initially, pick is in [1, n].
In each step, we eliminate a half that strictly cannot contain pick based on the API's return value.
Since the range size decreases monotonically and is finite, the loop must terminate.
Because pick is guaranteed to exist (per problem constraints), the condition guess(mid) == 0 will eventually be met.

Pattern Reuse Notes

The Binary Search pattern used here is fundamental and applies to many other problems.

LeetCode 35: Search Insert Position - Uses the same logic to find where an element belongs in a sorted array.
LeetCode 69: Sqrt(x) - Applies binary search on the answer space (integers) to find a square root.
LeetCode 74: Search a 2D Matrix - Treats a matrix as a flattened sorted list to perform binary search.
LeetCode 278: First Bad Version - Almost identical to Guess Number, finding the first true in a boolean sequence.

Feynman coach · Before you peek at the code

Can you explain the core insight in your own words?

If you can explain it before reading code, you’re far more likely to recall it under interview pressure.

Loading your attempt…

Reference Implementation

C++ Solution for LeetCode 374

cpp

1/** 
2 * Forward declaration of guess API.
3 * @param  num   your guess
4 * @return 	     -1 if num is higher than the picked number
5 *			      1 if num is lower than the picked number
6 *               otherwise return 0
7 * int guess(int num);
8 */
9
10class Solution {
11public:
12    int guessNumber(int n) {
13        int left = 1;
14        int right = n;
15        
16        while (left <= right) {
17            // Prevent integer overflow
18            int mid = left + (right - left) / 2;
19            
20            int res = guess(mid);
21            
22            if (res == 0) {
23                return mid;
24            } else if (res == -1) {
25                // Guess is higher than pick, so pick is smaller
26                right = mid - 1;
27            } else {
28                // Guess is lower than pick, so pick is larger
29                left = mid + 1;
30            }
31        }
32        
33        return -1; // Should not reach here
34    }
35};

Java Solution for LeetCode 374

java

1/** 
2 * Forward declaration of guess API.
3 * @param  num   your guess
4 * @return 	     -1 if num is higher than the picked number
5 *			      1 if num is lower than the picked number
6 *               otherwise return 0
7 * int guess(int num);
8 */
9
10public class Solution extends GuessGame {
11    public int guessNumber(int n) {
12        int left = 1;
13        int right = n;
14        
15        while (left <= right) {
16            // Prevent integer overflow during addition
17            int mid = left + (right - left) / 2;
18            
19            int res = guess(mid);
20            
21            if (res == 0) {
22                return mid;
23            } else if (res == -1) {
24                // My guess is too high, target is lower
25                right = mid - 1;
26            } else {
27                // My guess is too low, target is higher
28                left = mid + 1;
29            }
30        }
31        
32        return -1; // Should not be reached
33    }
34}

Python Solution for LeetCode 374

python

1# The guess API is already defined for you.
2# @param num, your guess
3# @return -1 if num is higher than the picked number
4#          1 if num is lower than the picked number
5#          otherwise return 0
6# def guess(num):
7
8class Solution:
9    def guessNumber(self, n: int) -> int:
10        left = 1
11        right = n
12        
13        while left <= right:
14            # Standard binary search mid calculation
15            mid = left + (right - left) // 2
16            
17            res = guess(mid)
18            
19            if res == 0:
20                return mid
21            elif res == -1:
22                # Guess is too high, look in the lower half
23                right = mid - 1
24            else:
25                # Guess is too low, look in the upper half
26                left = mid + 1
27                
28        return -1

Guess Number Higher or Lower

Core insight

Core Insight for Guess Number Higher or Lower

Full breakdown

LeetCode 374: Guess Number Higher or Lower Solution & Explanation

Problem Overview

Brute Force Approach for Guess Number Higher or Lower

Algorithm Strategy: Binary Search Patterns

Execution Flow

Proof of Correctness

Pattern Reuse Notes

Can you explain the core insight in your own words?

Reference Implementation

C++ Solution for LeetCode 374

Java Solution for LeetCode 374

Python Solution for LeetCode 374

Practise Guess Number Higher or Lower and the problems around it

Related problems

Guess Number Higher or Lower

Core insight

Core Insight for Guess Number Higher or Lower

Full breakdown

LeetCode 374: Guess Number Higher or Lower Solution & Explanation

Problem Overview

Brute Force Approach for Guess Number Higher or Lower

Algorithm Strategy: Binary Search Patterns

Execution Flow

Proof of Correctness

Pattern Reuse Notes

Can you explain the core insight in your own words?

Reference Implementation

C++ Solution for LeetCode 374

Java Solution for LeetCode 374

Python Solution for LeetCode 374

Practise Guess Number Higher or Lower and the problems around it

Related problems