Guess Number Higher Lower LeetCode 374

LeetCode 374 — Guess Number Higher or Lower is a classic binary search problem with an API twist. You are playing a guessing game: a number from 1 to n is picked, and you must find it by calling the pre-defined API guess(num). The API tells you whether your guess is too high, too low, or exactly correct.

The challenge is purely about applying binary search correctly against a callback rather than an array. You do not compare against a stored value — instead, you query the guess API at each step and adjust your search window based on the response. The game ends the moment guess(num) returns 0.

This problem is an excellent introduction to the interactive binary search pattern, where the comparison function is a black box. The same pattern appears in problems like First Bad Version (LeetCode 278), Search Insert Position, and any scenario where you cannot directly access the data but can query it.

The binary search setup is straightforward: initialize lo = 1 and hi = n. At each step, compute mid = lo + (hi - lo) / 2 to avoid integer overflow. Call guess(mid) to determine whether the hidden number is at mid, below mid, or above mid.

If guess(mid) returns 0, mid is the answer — return it immediately. If guess(mid) returns -1, your guess was too high, so the hidden number is below mid: set hi = mid - 1 and continue. If guess(mid) returns 1, your guess was too low, so the hidden number is above mid: set lo = mid + 1 and continue.

The loop invariant is that the hidden number always lies in [lo, hi]. Each iteration cuts the window in half, guaranteeing termination in O(log n) steps. The problem guarantees the picked number is always in [1, n], so the answer is always found before lo exceeds hi.

The most common source of bugs on this problem is misreading the guess API return values. The values -1 and 1 are defined from the PICKER's perspective, not the guesser's — and they are counterintuitive if you do not read the docs carefully.

When guess(num) returns -1, it means your guess num is TOO HIGH — the hidden number is LOWER than your guess. So you should move hi = mid - 1 to search the lower half. When guess(num) returns 1, it means your guess num is TOO LOW — the hidden number is HIGHER than your guess. So you should move lo = mid + 1 to search the upper half.

A good mental model: read the return value as what the picker says about the hidden number relative to your guess. -1 means "the pick is lower than your guess." 1 means "the pick is higher than your guess." 0 means "you got it." Confusing -1 and 1 causes an infinite loop or wrong answer — it is the #1 bug on this problem.

Always compute mid as lo + (hi - lo) / 2 rather than (lo + hi) / 2. When lo and hi are both large (e.g., both near Integer.MAX_VALUE in Java), their sum overflows a 32-bit integer, producing a negative result and sending mid to the wrong half of the range.

The safe formula lo + (hi - lo) / 2 avoids this by computing the offset from lo rather than the direct average. Since (hi - lo) is always non-negative and less than Integer.MAX_VALUE when hi <= Integer.MAX_VALUE and lo >= 1, the subtraction never overflows. Adding the halved offset to lo produces the correct midpoint.

For n up to 2^31 - 1, which is the typical constraint, the unsafe formula (lo + hi) / 2 will overflow when lo and hi are both in the upper half of the integer range. This is a real bug in production code and a standard interview follow-up question — always use the overflow-safe version.

n = 10, pick = 6. Initialize lo = 1, hi = 10. Step 1: mid = 1 + (10-1)/2 = 5. Call guess(5) — 5 is too low (pick 6 > 5), returns 1. Set lo = 6.

Step 2: lo = 6, hi = 10. mid = 6 + (10-6)/2 = 8. Call guess(8) — 8 is too high (pick 6 < 8), returns -1. Set hi = 7.

Step 3: lo = 6, hi = 7. mid = 6 + (7-6)/2 = 6. Call guess(6) — correct, returns 0. Return 6. Total: 3 API calls for n=10, matching the O(log n) = O(log 10) ≈ 3.32 expected performance.

Python: def guessNumber(n): lo, hi = 1, n; while lo <= hi: mid = lo + (hi - lo) // 2; result = guess(mid); if result == 0: return mid; elif result == -1: hi = mid - 1; else: lo = mid + 1. Six lines of core logic. Time: O(log n). Space: O(1).

Java: public int guessNumber(int n) { int lo = 1, hi = n; while (lo <= hi) { int mid = lo + (hi - lo) / 2; int res = guess(mid); if (res == 0) return mid; else if (res == -1) hi = mid - 1; else lo = mid + 1; } return -1; } The -1 fallback after the loop is unreachable given the problem guarantee, but Java requires a return statement.

Both implementations are O(log n) time and O(1) space — no recursion stack, no auxiliary arrays. The while lo <= hi loop terminates because each iteration strictly reduces the window size: either lo increases or hi decreases. The problem guarantee that the pick is always in [1, n] means guess(mid) == 0 is always reached.

LeetCode 374 belongs to the interactive binary search family — problems where you cannot access data directly but can query it. First Bad Version (LeetCode 278) is the closest cousin: isBadVersion(mid) replaces guess(mid), and the logic is identical. Search in Rotated Sorted Array (LeetCode 33) uses the same mid calculation but adds a step to determine which half is sorted before deciding which way to move.

Find Peak Element (LeetCode 162) is another binary search problem where the comparison is between adjacent elements rather than a target value — yet the same binary search framework applies. Koko Eating Bananas (LeetCode 875) uses binary search over the answer space (bananas per hour) rather than a data array, another variation on the same core pattern.

The unifying thread across all binary search variants: a monotonic decision function (something is clearly "too low" or "too high" or "correct"), a search space that can be halved each step, and the overflow-safe mid calculation. Master these elements and every binary search problem becomes a straightforward application of the same template.