LeetCode 374: Guess Number Higher or Lower Solution in Python – A Step-by-Step Guide

What Is LeetCode 374: Guess Number Higher or Lower?

LeetCode 374: Guess Number Higher or Lower provides an integer n and a hidden number (pick) between 1 and n. You use a pre-defined API function guess(num) that returns -1 if num is too high, 1 if too low, and 0 if correct. Your task is to find the hidden number in as few guesses as possible. It’s a classic search problem with a binary twist!

Problem Statement

• Input:
• n: Integer representing the upper bound of the range (1 to n).
• Output: Integer - The hidden number (pick).
• API:
• guess(num): Returns -1 (num > pick), 1 (num < pick), 0 (num == pick).
• Rules:
• Find pick using only the guess API.
• Minimize the number of guesses.

Constraints

• 1 <= n <= 2³¹ - 1
• 1 <= pick <= n

Examples

• Input: n = 10, pick = 6
• Output: 6
• Guess 5 → 1 (too low), Guess 7 → -1 (too high), Guess 6 → 0 (correct).
• Input: n = 1, pick = 1
• Output: 1
• Guess 1 → 0 (correct).
• Input: n = 2, pick = 1
• Output: 1
• Guess 2 → -1 (too high), Guess 1 → 0 (correct).

These show the guessing game—let’s solve it!

Understanding the Problem: Guessing the Number

To tackle LeetCode 374 in Python, we need to: 1. Find the hidden number (pick) between 1 and n. 2. Use only the guess(num) API for feedback (-1, 1, 0). 3. Minimize API calls for efficiency.

A naive approach might guess sequentially, but that’s slow. Instead, we’ll use:

• Best Solution: Binary search—O(log n) time, O(1) space—fast and optimal.
• Alternative Solution: Linear search—O(n) time, O(1) space—simple but inefficient.

Let’s guess with the best solution!

Best Solution: Binary Search

Why This Is the Best Solution

The binary search approach runs in O(log n) time by halving the search space with each guess, using the feedback from guess(num) to adjust the range. It’s the most efficient—guaranteed to find the number in logarithmic steps, making it the gold standard for this problem!

How It Works

Think of it like a number-guessing game:

• Range: Start with left=1, right=n.
• Guess: Compute mid = (left + right) // 2.
• Adjust:
• If guess(mid) = 0, mid is the answer.
• If guess(mid) = 1, pick is higher, left = mid + 1.
• If guess(mid) = -1, pick is lower, right = mid - 1.
• Repeat: Until left > right or guess = 0.
• Result: Return the found number.

It’s like narrowing down the possibilities with each hint!

Step-by-Step Example

For n = 10, pick = 6:

• Range: left=1, right=10.
• Step 1: mid = (1+10)//2 = 5, guess(5) = 1 (too low), left = 6.
• Step 2: mid = (6+10)//2 = 8, guess(8) = -1 (too high), right = 7.
• Step 3: mid = (6+7)//2 = 6, guess(6) = 0 (correct), return 6.

For n = 2, pick = 1:

• Range: left=1, right=2.
• Step 1: mid = (1+2)//2 = 1, guess(1) = 0 (correct), return 1.

For n = 5, pick = 5:

• Range: left=1, right=5.
• Step 1: mid = 3, guess(3) = 1 (too low), left = 4.
• Step 2: mid = 4, guess(4) = 1 (too low), left = 5.
• Step 3: mid = 5, guess(5) = 0 (correct), return 5.

Code with Explanation

Here’s the Python code using binary search:

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

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

            if result == 0:  # Found the number
                return mid
            elif result == 1:  # Too low
                left = mid + 1
            else:  # Too high (result = -1)
                right = mid - 1

        return left  # Shouldn't reach here given constraints

Explanation

• Line 4: Set initial range: left=1, right=n.
• Lines 5-13: Binary search loop:
• Compute mid safely (left + (right - left) // 2 avoids overflow).
• Call guess(mid):
• If 0, mid is pick, return it.
• If 1, pick > mid, move left up.
• If -1, pick < mid, move right down.
• Line 15: Return left (unreachable due to problem guarantee).
• Time: O(log n)—halves range each step.
• Space: O(1)—no extra space.

This is like a guessing master—find the number fast!

Alternative Solution: Linear Search

Why an Alternative Approach?

The linear search solution runs in O(n) time by guessing each number from 1 to n sequentially until the correct one is found. It’s slower and less efficient—great for small n or understanding the brute-force baseline!

How It Works

• Guess: Start at 1, call guess(num).
• Check:
• If 0, return num.
• If 1, increment and continue.
• If -1, num too high (shouldn’t happen with ascending guesses).
• Result: Return found number.

It’s like counting up until you hit the target!

Step-by-Step Example

For n = 10, pick = 6:

• Guess 1: guess(1) = 1 (too low).
• Guess 2: guess(2) = 1.
• Guess 3: guess(3) = 1.
• Guess 4: guess(4) = 1.
• Guess 5: guess(5) = 1.
• Guess 6: guess(6) = 0 (correct), return 6.

For n = 2, pick = 1:

• Guess 1: guess(1) = 0 (correct), return 1.

Code with Explanation

Copy codeclass Solution:
    def guessNumber(self, n: int) -> int:
        # Linearly guess from 1 to n
        for num in range(1, n + 1):
            result = guess(num)
            if result == 0:  # Found the number
                return num
            # If result = 1, continue; -1 shouldn't happen
        return n  # If n is the pick

Explanation

• Line 4: Loop from 1 to n.
• Lines 5-7: Call guess(num):
• If 0, return num (found pick).
• If 1, continue (too low).
• -1 shouldn’t occur (ascending guesses).
• Line 8: Return n (handles n=pick case).
• Time: O(n)—worst case n guesses.
• Space: O(1)—no extra space.

It’s like a slow guesser—checks every number!

Comparing the Two Solutions

• Binary Search (Best):
• Time: O(log n)—logarithmic guesses.
• Space: O(1)—minimal.
• Pros: Fast, optimal.
• Cons: Requires search logic.
• Linear Search (Alternative):
• Time: O(n)—linear guesses.
• Space: O(1)—minimal.
• Pros: Simple to code.
• Cons: Inefficient for large n.

Binary search wins for speed!

Additional Examples and Edge Cases

• n=1, pick=1: Binary and linear both return 1 (1 guess).
• n=10⁹, pick=10⁹: Binary O(log n), linear O(n).
• n=5, pick=1: Binary faster than linear.

Both work, binary is optimal.

Complexity Breakdown

• Binary Search:
• Time: O(log n).
• Space: O(1).
• Linear Search:
• Time: O(n).
• Space: O(1).

Binary search excels for efficiency.

Key Takeaways

• Binary Search: Guess smart—fast and optimal!
• Linear Search: Guess all—clear but slow!
• Search: Efficiency matters.
• Python Tip: Loops rock—see [Python Basics](/python/basics).

Final Thoughts: Guess That Number

LeetCode 374: Guess Number Higher or Lower in Python is a search challenge. Binary search is the efficiency champ, while linear search builds intuition. Want more? Try LeetCode 278: First Bad Version or LeetCode 704: Binary Search. Ready to guess? Visit Solve LeetCode 374 on LeetCode and find that number today!