LeetCode 278: First Bad Version

Problem Restatement

We have versions numbered from 1 to n.

At some version, the product becomes bad. Because each version is built from the previous one, every version after the first bad version is also bad.

So the versions look like this:

good, good, good, bad, bad, bad

We are given an API:

isBadVersion(version)

It returns True if the version is bad and False if the version is good.

We need to find the first bad version while making as few API calls as possible. The source constraint is 1 <= bad <= n <= 2^31 - 1.

Input and Output

Function shape:

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

class Solution:
    def firstBadVersion(self, n: int) -> int:
        ...

Examples

For:

n = 5
bad = 4

The API behaves like this:

isBadVersion(1) == False
isBadVersion(2) == False
isBadVersion(3) == False
isBadVersion(4) == True
isBadVersion(5) == True

The first bad version is:

4

For:

n = 1
bad = 1

There is only one version, and it is bad.

So the answer is:

1

First Thought: Linear Scan

The most direct solution checks versions from left to right.

for version in range(1, n + 1):
    if isBadVersion(version):
        return version

This works because the first time we see a bad version, that version must be the answer.

Code:

class Solution:
    def firstBadVersion(self, n: int) -> int:
        for version in range(1, n + 1):
            if isBadVersion(version):
                return version

Problem With Linear Scan

The linear scan may call the API n times.

Since n can be as large as 2^31 - 1, a linear scan can be too slow.

We need to use the sorted structure of the answers.

The versions form a monotonic boolean sequence:

False, False, False, True, True, True

We need the first True.

That is a binary search problem.

Key Insight

If we check a middle version mid, there are two cases.

If:

isBadVersion(mid) == True

then mid is bad. The first bad version may be mid, or it may be earlier. So we keep the left half, including mid.

If:

isBadVersion(mid) == False

then mid is good. The first bad version must be after mid. So we discard mid and everything before it.

This lets us remove about half of the remaining versions on every API call.

Algorithm

Use binary search over the version range [1, n].

Initialize:

left = 1
right = n

While left < right:

1. Compute the middle version.
2. If mid is bad, move right to mid.
3. If mid is good, move left to mid + 1.

When the loop ends, left == right.

That position is the first bad version.

Correctness

At all times, the first bad version is inside the current range [left, right].

At the start, the range is [1, n], so it contains the first bad version.

On each step, we inspect mid.

If mid is bad, every version after mid can be ignored because mid itself is already bad. The first bad version must be either mid or some earlier version. So setting right = mid keeps the answer inside the range.

If mid is good, then mid and every version before it cannot be the first bad version. So setting left = mid + 1 keeps the answer inside the range.

Each step preserves the invariant that the answer is inside [left, right].

The loop stops when left == right. Since the range contains the answer and has only one version left, that version must be the first bad version.

Complexity

Implementation

# 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

Code Explanation

We search inside the inclusive range:

left = 1
right = n

The loop continues while more than one possible answer remains:

while left < right:

We compute the middle this way:

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

In Python, (left + right) // 2 is safe too. The longer form is common because in languages with fixed-size integers, it avoids overflow.

If mid is bad:

if isBadVersion(mid):
    right = mid

we keep mid, because mid may be the first bad version.

If mid is good:

else:
    left = mid + 1

we discard mid, because the answer must be later.

Finally:

return left

At this point, left and right are equal, and they point to the first bad version.

Testing

LeetCode provides the isBadVersion API. For local testing, we can simulate it with a closure.

def make_solution(first_bad):
    def isBadVersion(version: int) -> bool:
        return version >= first_bad

    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

    return Solution()

def test_first_bad_version():
    assert make_solution(4).firstBadVersion(5) == 4
    assert make_solution(1).firstBadVersion(1) == 1
    assert make_solution(1).firstBadVersion(10) == 1
    assert make_solution(10).firstBadVersion(10) == 10
    assert make_solution(7).firstBadVersion(20) == 7

    print("all tests passed")

test_first_bad_version()

Test meaning: