First Bad Version

LeetCode 278: First Bad Version Solution & Explanation

Problem Overview

TL;DR: The optimal solution utilizes binary search to locate the transition point from "good" to "bad" versions in $O(\log n)$ time, minimizing API calls.

In the LeetCode 278 problem "First Bad Version," we are given a sequence of product versions numbered from 1 to $n$. We are told that once a version is bad, all subsequent versions are also bad. Our goal is to identify the very first bad version using a provided API function, isBadVersion(version). This is a classic search problem where we must minimize the number of calls to the external API, making it a popular interview question for testing algorithmic efficiency.

Brute Force Approach for First Bad Version

The most intuitive way to solve this problem is to check every version sequentially, starting from version 1. We continue checking versions one by one until we encounter the first version that the API reports as "bad."

Pseudo-code:

for version from 1 to n:
    if isBadVersion(version) is true:
        return version

Complexity Analysis:

• Time Complexity: $O(n)$. In the worst-case scenario (e.g., the bad version is $n$ or does not exist), we perform a linear scan of the entire range.
• Space Complexity: $O(1)$.

Why it fails: While logically correct, the linear approach fails due to time constraints. The problem statement specifies that $n$ can be as large as $2^{31} - 1$. If the first bad version appears late in the sequence, the brute force method will exceed the time limit (TLE) because checking billions of versions sequentially is computationally expensive.

Algorithm Strategy: Binary Search Patterns

We implement the standard Binary Search algorithm tailored for finding the leftmost element that satisfies a condition (often called lower_bound).

1. Initialization: Set two pointers, left to 1 and right to $n$.
2. Loop: Continue searching while left < right.
3. Midpoint Calculation: Calculate mid to avoid integer overflow: mid = left + (right - left) / 2.
4. Condition Check: Call isBadVersion(mid).
   • Case A (Bad Version): If true, this version is a candidate for the first bad version, but there might be an earlier one. We narrow the search to the left half, including the current mid: right = mid.
   • Case B (Good Version): If false, the first bad version must be after this one. We narrow the search to the right half, excluding the current mid: left = mid + 1.
5. Termination: When the loop ends (left == right), the left pointer will be at the first bad version.

Execution Flow

Let's trace the algorithm with Input: n = 5, bad = 4.

1. Initial State:

   • Range: [1, 5]
   • left = 1, right = 5

2. Iteration 1:

   • Calculate mid: 1 + (5 - 1) / 2 = 3.
   • Check API: isBadVersion(3) returns false (3 is good).
   • Logic: Since 3 is good, the first bad version must be $> 3$.
   • Update: left = mid + 1 = 4.
   • New Range: [4, 5]

3. Iteration 2:

   • Calculate mid: 4 + (5 - 4) / 2 = 4.
   • Check API: isBadVersion(4) returns true (4 is bad).
   • Logic: Since 4 is bad, it could be the first one. We keep it in the search space.
   • Update: right = mid = 4.
   • New Range: [4, 4]

4. Termination:

   • Condition left < right is now 4 < 4, which is false.
   • Loop terminates.
   • Return left (which is 4).

Proof of Correctness

The correctness relies on the invariant that the first bad version is always contained within the closed interval [left, right].

• Initialization: The range [1, n] definitely contains the first bad version (per problem constraints).
• Maintenance:
  • If mid is bad, the answer is $\le mid$. Setting right = mid preserves the answer in the range.
  • If mid is good, the answer is $> mid$. Setting left = mid + 1 preserves the answer in the range.
• Termination: The loop runs while left < right. Since the range size decreases strictly at each step (either right decreases or left increases), the pointers must eventually converge. When left == right, the search space has size 1, and due to the invariant, this single element must be the first bad version.

Pattern Reuse Notes

The Binary Search pattern used here is fundamental for finding boundaries in sorted data. Similar logic applies to:

• LeetCode 35: Search Insert Position (Find the index where an element belongs)
• LeetCode 69: Sqrt(x) (Find the integer square root, a monotonic property)
• LeetCode 74: Search a 2D Matrix (Treating a matrix as a sorted list)
• LeetCode 374: Guess Number Higher or Lower (Almost identical structure to First Bad Version)

Understanding how to narrow the search space based on a boolean condition is the key to solving all these problems efficiently.

Reference Implementation

C++ Solution for LeetCode 278

1// The API isBadVersion is defined for you.
2// bool isBadVersion(int version);
3
4class Solution {
5public:
6    int firstBadVersion(int n) {
7        int left = 1;
8        int right = n;
9        
10        while (left < right) {
11            // Prevent integer overflow
12            int mid = left + (right - left) / 2;
13            
14            if (isBadVersion(mid)) {
15                // Mid is bad; the first bad version is mid or to the left.
16                right = mid;
17            } else {
18                // Mid is good; the first bad version is strictly to the right.
19                left = mid + 1;
20            }
21        }
22        
23        // When left == right, we have found the first bad version.
24        return left;
25    }
26};

Java Solution for LeetCode 278

1/* The isBadVersion API is defined in the parent class VersionControl.
2      boolean isBadVersion(int version); */
3
4public class Solution extends VersionControl {
5    public int firstBadVersion(int n) {
6        int left = 1;
7        int right = n;
8        
9        while (left < right) {
10            // Calculate mid to avoid integer overflow
11            int mid = left + (right - left) / 2;
12            
13            if (isBadVersion(mid)) {
14                // Found a bad version, search left half (inclusive)
15                right = mid;
16            } else {
17                // Found a good version, search right half (exclusive)
18                left = mid + 1;
19            }
20        }
21        
22        return left;
23    }
24}

Python Solution for LeetCode 278

1# The isBadVersion API is already defined for you.
2# def isBadVersion(version: int) -> bool:
3
4class Solution:
5    def firstBadVersion(self, n: int) -> int:
6        left = 1
7        right = n
8        
9        while left < right:
10            # Python handles large integers automatically, 
11            # but this formula is standard for binary search logic.
12            mid = left + (right - left) // 2
13            
14            if isBadVersion(mid):
15                # Mid is bad, answer is mid or to the left
16                right = mid
17            else:
18                # Mid is good, answer is to the right
19                left = mid + 1
20                
21        return left