Watch 10 video solutions for Guess Number Higher or Lower, a easy level problem involving Binary Search, Interactive. This walkthrough by NeetCode has 45,850 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
We are playing the Guess Game. The game is as follows:
I pick a number from 1 to n. You have to guess which number I picked.
Every time you guess wrong, I will tell you whether the number I picked is higher or lower than your guess.
You call a pre-defined API int guess(int num), which returns three possible results:
-1: Your guess is higher than the number I picked (i.e. num > pick).1: Your guess is lower than the number I picked (i.e. num < pick).0: your guess is equal to the number I picked (i.e. num == pick).Return the number that I picked.
Example 1:
Input: n = 10, pick = 6 Output: 6
Example 2:
Input: n = 1, pick = 1 Output: 1
Example 3:
Input: n = 2, pick = 1 Output: 1
Constraints:
1 <= n <= 231 - 11 <= pick <= nProblem Overview: You need to guess a hidden number between 1 and n. An API guess(num) tells whether your guess is correct, too high, or too low. The goal is to minimize guesses while identifying the exact number.
Approach 1: Iterative Method with Linear Search (O(n) time, O(1) space)
The simplest strategy is to start from 1 and repeatedly call guess(i) while incrementing the value. If the API returns 0, you found the hidden number. If it returns -1, your guess is too high and you stop. This approach works because the range is sequential, but it may require checking every number up to n. The time complexity is O(n) since each value may be tested once, while space usage stays O(1). It demonstrates the basic interaction pattern but becomes inefficient for large ranges.
Approach 2: Binary Search Method (O(log n) time, O(1) space)
The efficient solution applies binary search on the range [1, n]. Start with two pointers: left = 1 and right = n. Compute the middle value and call guess(mid). If the result is 0, the number is found. If the API returns -1, the guess is too high so move the right boundary to mid - 1. If it returns 1, the guess is too low so move the left boundary to mid + 1. Each step halves the search range, which reduces the number of API calls dramatically. The algorithm runs in O(log n) time with constant O(1) extra space.
This problem is also categorized as an interactive problem because your program must repeatedly query an external API instead of accessing the hidden value directly. The key insight is recognizing that the API response gives ordering information, which allows binary search to eliminate half the possibilities each step.
Recommended for interviews: Binary search is the expected solution. Interviewers want to see you recognize that the API feedback provides a sorted decision boundary, enabling a classic binary search pattern. Mentioning the linear scan first shows understanding of the brute-force baseline, but implementing the O(log n) binary search demonstrates strong problem-solving and algorithm knowledge.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative Linear Search | O(n) | O(1) | Useful as a baseline or when the search range is very small |
| Binary Search | O(log n) | O(1) | Best choice when the range is ordered and the API reveals higher/lower hints |