374. Guess Number Higher or Lower

EasyBinary SearchInteractive

LeetCode ↗

Problem Editor Idea Example Code Complex Pitfalls

Problem Description

This is a classic number guessing game where you need to find a secret number between 1 and n.

The game works as follows:

A number between 1 and n (inclusive) has been picked beforehand
You need to find this number by making guesses
For each guess you make, you'll receive feedback through a pre-defined API function guess(num)

The guess(num) function returns:

-1 if your guess is too high (your guess > the picked number)
1 if your guess is too low (your guess < the picked number)
0 if your guess is correct (your guess = the picked number)

Your task is to implement a function that finds and returns the picked number using the guess API.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

Intuition

When we need to find a specific number in a sorted range from 1 to n, and we can only check if our guess is too high, too low, or correct, binary search naturally comes to mind. This is because we can eliminate half of the remaining possibilities with each guess.

To apply binary search, turn each guess into a yes/no question: "is x at least the picked number?" That is the same as guess(x) <= 0. For every x below the picked number the answer is no, and for the picked number and everything above it the answer is yes:

When x is too low, guess(x) returns 1, so the answer is no
When x is correct, guess(x) returns 0, so the answer is yes
When x is too high, guess(x) returns -1, so the answer is yes

The answers form a block of no's followed by a block of yes's, and the picked number is the first yes. Finding the first True in such a sequence is the standard binary search template: check the middle, keep the left half when the answer is yes (recording mid as a candidate), and keep the right half when it is no.

New to patterns?Most interview problems reduce to a handful of patterns. This video covers the main eight.

Solution Approach

The solution runs a binary search for the first number x in [1, n] with guess(x) <= 0.

Feasibility Function: feasible(mid) returns guess(mid) <= 0, which is true when mid is greater than or equal to the picked number:

If mid is less than the picked number, guess(mid) returns 1, so feasible(mid) is False
If mid equals the picked number, guess(mid) returns 0, so feasible(mid) is True
If mid is greater than the picked number, guess(mid) returns -1, so feasible(mid) is True

Over x = 1, 2, ..., n this gives a run of False values followed by a run of True values, and the first True is exactly the picked number.

Binary Search Loop: Start with left = 1, right = n, and first_true_index = -1. While left <= right:

Compute mid = (left + right) // 2
If feasible(mid) is true, record first_true_index = mid and search the left half with right = mid - 1, in case a smaller feasible value exists
Otherwise, the picked number is larger than mid, so search the right half with left = mid + 1

Return Value: When the loop ends, first_true_index holds the smallest x with guess(x) <= 0, which is the picked number.

The loop does not stop early when guess(mid) returns 0. It keeps narrowing until left > right, which keeps the template the same as other "first true" searches.

Time Complexity: O(log n) - the search range halves on every iteration.

Space Complexity: O(1) - only left, right, mid, and first_true_index are stored.

Example Walkthrough

Let's walk through a concrete example where n = 10 and the picked number is 6.

Initial Setup:

left = 1, right = 10, first_true_index = -1
Target: find the picked number (which is 6, but we don't know this yet)

Step 1: Range [1, 10], mid = 5

Call guess(5): returns 1 (5 is too low)
feasible(5) is False, so set left = 6

Step 2: Range [6, 10], mid = 8

Call guess(8): returns -1 (8 is too high)
feasible(8) is True, so record first_true_index = 8 and set right = 7

Step 3: Range [6, 7], mid = 6

Call guess(6): returns 0 (correct)
feasible(6) is True, so record first_true_index = 6 and set right = 5

Step 4: Now left = 6 > right = 5, so the loop ends

Result: The function returns first_true_index = 6, which is the correct answer.

Visualizing the Transformation:

Number x:        1   2   3   4   5   6   7   8   9   10
guess(x):        1   1   1   1   1   0  -1  -1  -1  -1
feasible(x):     F   F   F   F   F   T   T   T   T   T
                                     ↑
                                     first True = picked number

The binary search finds the first True in this sequence, which is at x = 6.

Solution Implementation

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: int) -> int:
7
8
9class Solution:
10    def guessNumber(self, n: int) -> int:
11        """
12        Find the picked number between 1 and n using binary search.
13
14        Feasible condition: guess(mid) <= 0 means mid >= picked number.
15        We find the first value where guess(mid) <= 0 (i.e., mid is >= picked).
16
17        Args:
18            n: The upper bound of the range [1, n]
19
20        Returns:
21            The picked number
22        """
23        # Define feasible: guess(mid) <= 0 means mid >= picked
24        # We want the first mid where this is true
25        def feasible(mid: int) -> bool:
26            return guess(mid) <= 0
27
28        left, right = 1, n
29        first_true_index = -1
30
31        while left <= right:
32            mid = (left + right) // 2
33            if feasible(mid):
34                first_true_index = mid
35                right = mid - 1
36            else:
37                left = mid + 1
38
39        return first_true_index
40

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    /**
12     * Finds the picked number using the binary search template.
13     * Feasible condition: guess(mid) <= 0 means mid >= picked number.
14     * We find the first value where this is true.
15     */
16    public int guessNumber(int n) {
17        int left = 1;
18        int right = n;
19        int firstTrueIndex = -1;
20
21        while (left <= right) {
22            int mid = left + (right - left) / 2;
23            if (guess(mid) <= 0) {
24                firstTrueIndex = mid;
25                right = mid - 1;
26            } else {
27                left = mid + 1;
28            }
29        }
30
31        return firstTrueIndex;
32    }
33}
34

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    /**
13     * Finds the picked number using the binary search template.
14     * Feasible condition: guess(mid) <= 0 means mid >= picked number.
15     * We find the first value where this is true.
16     */
17    int guessNumber(int n) {
18        int left = 1;
19        int right = n;
20        int firstTrueIndex = -1;
21
22        while (left <= right) {
23            int mid = left + (right - left) / 2;
24            if (guess(mid) <= 0) {
25                firstTrueIndex = mid;
26                right = mid - 1;
27            } else {
28                left = mid + 1;
29            }
30        }
31
32        return firstTrueIndex;
33    }
34};
35

1/**
2 * Forward declaration of guess API.
3 * @param {number} 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 * var guess = function(num) {}
8 */
9
10/**
11 * Finds the picked number using the binary search template.
12 * Feasible condition: guess(mid) <= 0 means mid >= picked number.
13 * We find the first value where this is true.
14 *
15 * Time Complexity: O(log n)
16 * Space Complexity: O(1)
17 */
18function guessNumber(n: number): number {
19    let left = 1;
20    let right = n;
21    let firstTrueIndex = -1;
22
23    while (left <= right) {
24        const mid = Math.floor((left + right) / 2);
25        if (guess(mid) <= 0) {
26            firstTrueIndex = mid;
27            right = mid - 1;
28        } else {
29            left = mid + 1;
30        }
31    }
32
33    return firstTrueIndex;
34}
35

Time and Space Complexity

The time complexity is O(log n), where n is the upper limit given in the problem. The search range starts as [1, n] and halves on every iteration, so the loop calls guess about log₂(n) times.

The space complexity is O(1). The algorithm stores only left, right, mid, and first_true_index.

Common Pitfalls

Pitfall 1: Mixing Binary Search Template Variants

The Problem: Two templates are common. One uses while left < right with right = mid and returns left; the other uses while left <= right, records the answer, and sets right = mid - 1. Both are correct here because the picked number always exists. Mixing them breaks the search.

Wrong Implementation:

while left < right:
    mid = (left + right) // 2
    if guess(mid) <= 0:
        right = mid - 1  # WRONG with left < right: can step past the answer
    else:
        left = mid + 1
return left

For n = 2 and picked number 1: mid = 1, guess(1) = 0, so right = 0, and the loop ends with left = 1, which happens to be right. For n = 4 and picked number 2: mid = 2 gives right = 1, the loop ends with left = 1, and the function returns 1 instead of 2.

Solution: Use one template consistently. The solution records each candidate before moving right past it:

first_true_index = -1
while left <= right:
    mid = (left + right) // 2
    if guess(mid) <= 0:
        first_true_index = mid
        right = mid - 1
    else:
        left = mid + 1
return first_true_index

Pitfall 2: Misunderstanding the Guess API Return Values

The guess() function returns:

-1 if your guess is higher than the picked number
1 if your guess is lower than the picked number
0 if your guess is correct

Wrong Interpretation:

# WRONG: Inverting the meaning of -1 and 1
if guess(mid) == 1:  # Thinking 1 means "too high"
    right = mid - 1

Solution: The feasible condition is guess(mid) <= 0, which means mid is greater than or equal to the picked number.

Pitfall 3: Integer Overflow in Mid Calculation

In languages with fixed integer sizes, (left + right) / 2 can overflow.

Wrong Implementation:

int mid = (left + right) / 2;  // Can overflow when left + right > Integer.MAX_VALUE

Solution: Use left + (right - left) / 2 to avoid overflow:

int mid = left + (right - left) / 2;

Pitfall 4: Off-by-One Errors with Search Range

Using incorrect initial boundaries can miss the answer.

Wrong Implementation:

left, right = 0, n  # WRONG: 0 is not a valid guess
# or
left, right = 1, n - 1  # WRONG: might miss n

Solution: Always use left = 1 and right = n since the picked number is between 1 and n inclusive.

Ready to land your dream job?

Unlock your dream job with a 5-minute quiz for a personalized study roadmap!

Get My Roadmap

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Get a Personalized Study Roadmap:

374. Guess Number Higher or Lower

Problem Description

Intuition

Solution Approach

Example Walkthrough

Solution Implementation

Time and Space Complexity

Common Pitfalls

Pitfall 1: Mixing Binary Search Template Variants

Pitfall 2: Misunderstanding the Guess API Return Values

Pitfall 3: Integer Overflow in Mid Calculation

Pitfall 4: Off-by-One Errors with Search Range

Ready to land your dream job?

Unlock your dream job with a 5-minute quiz for a personalized study roadmap!

Recommended Readings