LeetCode 374 - Guess Number Higher or Lower

The problem describes a classic interactive guessing game. A hidden number called pick is chosen somewhere in the range from 1 to n, inclusive. We are not allowed to access pick directly.

leetcodeeasybinary-searchinteractive

LeetCode Problem 374

Difficulty: 🟢 Easy
Topics: Binary Search, Interactive

Solution

Problem Understanding

The problem describes a classic interactive guessing game. A hidden number called pick is chosen somewhere in the range from 1 to n, inclusive. We are not allowed to access pick directly. Instead, we can only interact with the provided API function:

guess(num)

This API tells us whether our current guess is too high, too low, or exactly correct.

The return values have the following meanings:

  • -1 means the guessed number is larger than the hidden number
  • 1 means the guessed number is smaller than the hidden number
  • 0 means the guess is correct

Our task is to determine the hidden number and return it.

The input consists of a single integer n, which defines the search range [1, n]. The expected output is the exact hidden number selected by the game.

The constraints are especially important here:

1 <= n <= 2^31 - 1

This means the search space can be extremely large, potentially over two billion numbers. Because of this, a linear scan from 1 to n would be inefficient in the worst case. The problem is intentionally designed to encourage the use of binary search.

An important property of the problem is that the API response creates a monotonic relationship:

  • If a guess is too high, every larger number is also too high.
  • If a guess is too low, every smaller number is also too low.

This ordered structure is exactly what binary search requires.

There are several edge cases worth recognizing upfront. The hidden number could be the smallest possible value, 1, or the largest possible value, n. The range could also contain only a single number, such as n = 1. Another subtle issue is integer overflow when computing the midpoint in languages like Go or Java. Using:

mid = left + (right - left) / 2

is safer than:

mid = (left + right) / 2

because the latter can overflow when left and right are very large.

Approaches

Brute Force Approach

The most straightforward solution is to try every number sequentially from 1 to n.

For each number:

  • Call guess(current)
  • If the API returns 0, we found the hidden number
  • Otherwise continue to the next value

This approach is correct because it eventually checks every possible candidate. Since the hidden number is guaranteed to exist within the range, the algorithm must eventually find it.

However, this solution is too slow for large values of n. In the worst case, if the hidden number is n, we would need to make n API calls. With n potentially equal to 2^31 - 1, this becomes impractical.

The key inefficiency is that the brute force method ignores the information provided by the API. When the API says a guess is too high or too low, we can eliminate large portions of the search space immediately.

Optimal Approach

The important observation is that the search space is sorted implicitly.

If guess(mid) returns:

  • -1, then the hidden number is smaller than mid
  • 1, then the hidden number is larger than mid
  • 0, then we found the answer

This means we can repeatedly cut the remaining search range in half. That is exactly the binary search strategy.

Binary search dramatically reduces the number of guesses. Instead of checking numbers one by one, we eliminate half of the remaining possibilities after every API call.

For example:

  • Start with range [1, n]
  • Check the middle value
  • Based on the API result, discard either the left half or right half
  • Repeat until the number is found

This reduces the time complexity from linear to logarithmic.

Approach Time Complexity Space Complexity Notes
Brute Force O(n) O(1) Sequentially tests every number
Optimal O(log n) O(1) Uses binary search to halve the search space repeatedly

Algorithm Walkthrough

  1. Initialize two pointers, left and right, representing the current search range.

Initially:

left = 1
right = n

We know the hidden number must exist somewhere inside this interval. 2. Continue searching while left <= right.

This condition ensures there are still valid candidates remaining in the search range. 3. Compute the middle value.

Use:

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

instead of (left + right) // 2 to avoid possible integer overflow in some languages. 4. Call the guess(mid) API.

The API tells us how mid compares to the hidden number. 5. If the API returns 0, return mid.

This means we guessed correctly. 6. If the API returns -1, move the right boundary.

Since mid is too large, the hidden number must be in:

[left, mid - 1]

Update:

right = mid - 1
  1. If the API returns 1, move the left boundary.

Since mid is too small, the hidden number must be in:

[mid + 1, right]

Update:

left = mid + 1
  1. Repeat until the hidden number is found.

Why it works

The algorithm works because after every API call, we eliminate half of the remaining candidates while preserving the invariant that the hidden number always remains inside the current search interval.

At every step:

  • If the guess is too high, all larger numbers are impossible.
  • If the guess is too low, all smaller numbers are impossible.

Because the search interval shrinks correctly each iteration, and because the hidden number is guaranteed to exist, the algorithm must eventually converge to the correct answer.

Python Solution

# The guess API is already defined for you.
# @param num, your guess
# @return -1 if num is higher than the picked number
#          1 if num is lower than the picked number
#          otherwise return 0
# def guess(num: int) -> int:

class Solution:
    def guessNumber(self, n: int) -> int:
        left = 1
        right = n

        while left <= right:
            mid = left + (right - left) // 2
            result = guess(mid)

            if result == 0:
                return mid
            elif result == -1:
                right = mid - 1
            else:
                left = mid + 1

        return -1

The implementation starts by defining the search boundaries, left and right. These represent the smallest and largest possible values the hidden number could still be.

Inside the loop, the midpoint is calculated carefully using:

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

This formulation avoids overflow issues in languages with fixed-size integers.

The guess(mid) API is then called and stored in result.

If result == 0, we immediately return mid because the correct number has been found.

If result == -1, the guess is too large, so we shrink the search range by moving right to mid - 1.

If result == 1, the guess is too small, so we move left to mid + 1.

The loop continues narrowing the interval until the hidden number is located.

The final return -1 is technically unreachable because the problem guarantees that the hidden number exists within the range.

Go Solution

/** 
 * Forward declaration of guess API.
 * @param  num   your guess
 * @return       -1 if num is higher than the picked number
 *                1 if num is lower than the picked number
 *                otherwise return 0
 * func guess(num int) int;
 */

func guessNumber(n int) int {
    left := 1
    right := n

    for left <= right {
        mid := left + (right-left)/2
        result := guess(mid)

        if result == 0 {
            return mid
        } else if result == -1 {
            right = mid - 1
        } else {
            left = mid + 1
        }
    }

    return -1
}

The Go implementation follows the same binary search logic as the Python version. One important detail is the midpoint calculation:

mid := left + (right-left)/2

This avoids integer overflow when left and right are very large.

Unlike Python, Go uses fixed-size integer types, so overflow prevention matters more explicitly.

Otherwise, the logic and control flow are identical between the two implementations.

Worked Examples

Example 1

Input: n = 10, pick = 6

Initial range:

left = 1
right = 10
Iteration left right mid guess(mid) Action
1 1 10 5 1 Hidden number is larger, move left to 6
2 6 10 8 -1 Hidden number is smaller, move right to 7
3 6 7 6 0 Found the hidden number

Result:

6

Example 2

Input: n = 1, pick = 1

Initial range:

left = 1
right = 1
Iteration left right mid guess(mid) Action
1 1 1 1 0 Found the hidden number

Result:

1

Example 3

Input: n = 2, pick = 1

Initial range:

left = 1
right = 2
Iteration left right mid guess(mid) Action
1 1 2 1 0 Found the hidden number

Result:

1

Complexity Analysis

Measure Complexity Explanation
Time O(log n) The search space is halved after every guess
Space O(1) Only a few variables are used

The time complexity is logarithmic because each API call eliminates half of the remaining candidates. Starting with n possible values, binary search reduces the search interval exponentially until only one number remains.

The space complexity is constant because the algorithm only stores a few integer variables regardless of the input size.

Test Cases

# Mock implementation for local testing
pick = 0

def guess(num: int) -> int:
    if num > pick:
        return -1
    elif num < pick:
        return 1
    return 0

class Solution:
    def guessNumber(self, n: int) -> int:
        left = 1
        right = n

        while left <= right:
            mid = left + (right - left) // 2
            result = guess(mid)

            if result == 0:
                return mid
            elif result == -1:
                right = mid - 1
            else:
                left = mid + 1

        return -1

solution = Solution()

pick = 6
assert solution.guessNumber(10) == 6  # Standard example

pick = 1
assert solution.guessNumber(1) == 1  # Single-element range

pick = 1
assert solution.guessNumber(2) == 1  # Smallest value in small range

pick = 2
assert solution.guessNumber(2) == 2  # Largest value in small range

pick = 1702766719
assert solution.guessNumber(2126753390) == 1702766719  # Large input range

pick = 1
assert solution.guessNumber(1000000) == 1  # Hidden number at lower boundary

pick = 1000000
assert solution.guessNumber(1000000) == 1000000  # Hidden number at upper boundary

pick = 500000
assert solution.guessNumber(1000000) == 500000  # Middle value

pick = 999999
assert solution.guessNumber(1000000) == 999999  # Near upper boundary

pick = 2
assert solution.guessNumber(3) == 2  # Small odd-sized range
Test Why
n=10, pick=6 Validates standard binary search behavior
n=1, pick=1 Tests smallest possible input
n=2, pick=1 Tests lower boundary in small range
n=2, pick=2 Tests upper boundary in small range
Large n case Verifies efficiency on very large inputs
pick=1 with large range Tests repeated movement toward lower boundary
pick=n Tests repeated movement toward upper boundary
pick in middle Confirms midpoint handling
pick near upper boundary Ensures no off-by-one errors
Small odd-sized range Tests midpoint calculation correctness

Edge Cases

One important edge case occurs when n = 1. In this scenario, the search range contains exactly one number. A careless implementation might incorrectly skip the loop or mishandle boundary conditions. The current implementation handles this naturally because the loop condition left <= right still holds, and the midpoint becomes 1, which is immediately returned.

Another important edge case is when the hidden number is at the extreme boundaries of the range, either 1 or n. These cases are common sources of off-by-one errors. For example, if the implementation incorrectly updates boundaries using mid instead of mid - 1 or mid + 1, the loop could become infinite. The implementation avoids this by always excluding the already-tested midpoint from future searches.

A third critical edge case involves very large values of n, especially near 2^31 - 1. In languages with fixed-size integers, calculating the midpoint using:

(left + right) / 2

can overflow. The implementation avoids this by computing:

left + (right - left) / 2

which guarantees safe arithmetic even for extremely large search ranges.