LeetCode 278 - First Bad Version

LeetCode Problem 278

Difficulty: 🟢 Easy
Topics: Binary Search, Interactive

Solution

Problem Understanding

The problem gives us a sequence of product versions numbered from 1 to n. At some point, one version becomes bad, and every version after it is also bad. This creates a monotonic pattern:

• Good versions appear first
• Bad versions appear afterward

For example:

Version: 1 2 3 4 5
Status : G G G B B

The task is to find the very first bad version.

We are not allowed to inspect the versions directly. Instead, we are given an API:

isBadVersion(version)

This function returns:

• True if the version is bad
• False if the version is good

The challenge is to minimize the number of API calls.

The input is:

• n, the total number of versions

The expected output is:

• The smallest version number for which isBadVersion(version) returns True

The constraints are important:

• 1 <= bad <= n <= 2^31 - 1

This means n can be extremely large, over two billion. A linear scan may require billions of API calls, which is far too slow. The constraints strongly suggest that we need a logarithmic time solution.

There are several important edge cases:

• The first version could already be bad
• The last version could be the first bad version
• There may be only one version total
• Very large values of n could cause integer overflow in some languages if midpoint calculations are done incorrectly

The problem guarantees that at least one bad version exists.

Approaches

Brute Force Approach

The simplest solution is to start from version 1 and check each version one by one using isBadVersion.

As soon as we encounter the first bad version, we return it.

This works because the versions are ordered. Once a bad version appears, all later versions are also bad, so the first bad version is exactly the first version for which the API returns True.

However, this approach is too slow for large inputs.

If n is very large and the first bad version is near the end, we may need to make almost n API calls. Since n can be over two billion, this is not acceptable.

Optimal Approach, Binary Search

The key observation is that the versions form a monotonic structure:

False False False False True True True

This is exactly the type of pattern where binary search works well.

Instead of checking every version, we repeatedly inspect the middle version.

• If the middle version is bad, then the first bad version must be at the middle or somewhere to the left
• If the middle version is good, then the first bad version must be somewhere to the right

By cutting the search space in half each time, we reduce the number of API calls dramatically.

This gives us logarithmic time complexity.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n)	O(1)	Checks versions sequentially until finding the first bad version
Optimal	O(log n)	O(1)	Uses binary search on the monotonic good-to-bad transition

Algorithm Walkthrough

1. Initialize two pointers, left and right.

• left = 1
• right = n

These pointers represent the current search range where the first bad version could exist. 2. Continue searching while left < right.

This condition ensures that we stop once the search space shrinks to a single candidate. 3. Compute the middle version safely.

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

This avoids integer overflow in languages like Go, Java, or C++. 4. Call isBadVersion(mid).

There are two possibilities:

• If mid is bad:

The first bad version could be mid itself or some earlier version.

So we keep the left half:

right = mid

• If mid is good:

The first bad version must appear after mid.

So we discard the left half:

left = mid + 1

5. Repeat until left == right.

At this point, only one version remains in the search range, and it must be the first bad version. 6. Return left.

Since left and right are equal, either one can be returned.

Why it works

The algorithm maintains an important invariant:

• The first bad version is always inside the current search range [left, right]

Each API call removes half of the remaining search space while preserving this invariant. Eventually, the range shrinks to exactly one version, which must be the first bad version.

Python Solution

# The isBadVersion API is already defined for you.
# def isBadVersion(version: int) -> bool:

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

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

            if isBadVersion(mid):
                right = mid
            else:
                left = mid + 1

        return left

The implementation begins by defining the search boundaries from 1 to n.

The while left < right loop continues narrowing the range until only one candidate remains.

The midpoint is calculated using:

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

This form is preferred because it avoids overflow in languages with fixed-size integers.

Inside the loop, the API determines whether the midpoint is bad.

If the midpoint is bad, we know the first bad version lies at mid or earlier, so we move right to mid.

If the midpoint is good, we know the first bad version must come later, so we move left to mid + 1.

Eventually, both pointers converge on the first bad version, which is returned.

Go Solution

/** 
 * Forward declaration of isBadVersion API.
 * @param   version   your guess about first bad version
 * @return            true if current version is bad 
 *                    false if current version is good
 * func isBadVersion(version int) bool;
 */

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

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

        if isBadVersion(mid) {
            right = mid
        } else {
            left = mid + 1
        }
    }

    return left
}

The Go implementation follows exactly the same binary search logic as the Python version.

One important detail is the midpoint calculation:

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

This avoids potential integer overflow.

Go uses fixed-size integers, so this safer midpoint formula is important when n is close to 2^31 - 1.

No additional memory structures are required, so the solution remains constant space.

Worked Examples

Example 1

Input: n = 5, bad = 4

Versions:

1 -> good
2 -> good
3 -> good
4 -> bad
5 -> bad

Step	left	right	mid	isBadVersion(mid)	Action
1	1	5	3	False	Move left to 4
2	4	5	4	True	Move right to 4
End	4	4	-	-	Return 4

Final answer:

4

Example 2

Input: n = 1, bad = 1

Step	left	right	Condition
Initial	1	1	left == right

The loop never runs because there is only one version.

Return:

1

Complexity Analysis

Measure	Complexity	Explanation
Time	O(log n)	Each iteration cuts the search range in half
Space	O(1)	Only a few variables are used

The binary search repeatedly halves the remaining search space. Since halving continues until only one element remains, the number of iterations is logarithmic relative to n.

No extra data structures are allocated, so the memory usage stays constant.

Test Cases

# Mock helper for testing
def make_is_bad_version(first_bad):
    def isBadVersion(version):
        return version >= first_bad
    return isBadVersion

# Example 1
isBadVersion = make_is_bad_version(4)
assert Solution().firstBadVersion(5) == 4  # first bad version in middle

# Example 2
isBadVersion = make_is_bad_version(1)
assert Solution().firstBadVersion(1) == 1  # single version

# First version is bad
isBadVersion = make_is_bad_version(1)
assert Solution().firstBadVersion(10) == 1  # earliest possible bad version

# Last version is bad
isBadVersion = make_is_bad_version(10)
assert Solution().firstBadVersion(10) == 10  # latest possible bad version

# Small range
isBadVersion = make_is_bad_version(2)
assert Solution().firstBadVersion(2) == 2  # two-element range

# Large input
isBadVersion = make_is_bad_version(1702766719)
assert Solution().firstBadVersion(2126753390) == 1702766719  # stress test

# Middle transition
isBadVersion = make_is_bad_version(500)
assert Solution().firstBadVersion(1000) == 500  # balanced binary search case

# Adjacent boundary
isBadVersion = make_is_bad_version(999)
assert Solution().firstBadVersion(1000) == 999  # near-end transition

Test Summary

Test	Why
n=5, bad=4	Standard example with transition near the end
n=1, bad=1	Minimum input size
n=10, bad=1	First version already bad
n=10, bad=10	Last version is first bad
n=2, bad=2	Small search space
Large stress test	Verifies logarithmic performance
bad=500 in 1000 versions	Typical balanced binary search behavior
bad=999 in 1000 versions	Transition very close to the end

Edge Cases

Only One Version Exists

When n = 1, the search range starts as:

left = 1
right = 1

Since left < right is false immediately, the loop never executes. The algorithm correctly returns 1.

This case is important because some implementations accidentally assume at least two elements exist.

The First Version Is Bad

If version 1 is already bad, every API call on any midpoint will return True.

The algorithm continuously shrinks the right boundary until both pointers converge at 1.

This edge case is important because incorrect binary search implementations sometimes skip the leftmost candidate.

The Last Version Is the First Bad Version

If only the final version is bad, most midpoint checks return False.

The algorithm keeps advancing the left boundary until it eventually reaches the final version.

This case validates that the implementation correctly handles transitions at the extreme right edge of the search space.

Very Large Values of n

The constraint allows values up to 2^31 - 1.

A midpoint calculation like:

mid = (left + right) // 2

can overflow in some languages with fixed-size integers.

The safer formula:

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

prevents overflow while producing the same result mathematically. The Go solution uses this safer calculation as well.