278. First Bad Version - Leetcode Solution

Leetcode Problem Link Code Solution Link:

Step-by-Step Thought Process

Brute Force

Understand the problem: Find the first version that is bad, given an API to check if a version is bad.
Iterate through each version from 1 to n.
For each version, call the isBadVersion API.
If the version is bad, return it as the first bad version.

Code Solution (Brute Force)

# Brute Force Solution
class Solution:
    def firstBadVersion(self, n: int) -> int:
        for version in range(1, n+1):
            if isBadVersion(version):
                return version
    # Time: O(n)
    # Space: O(1)

// The API isBadVersion is defined for you.
// bool isBadVersion(int version);

class Solution {
public:
    int firstBadVersion(int n) {
        for (int version = 1; version <= n; version++) {
            if (isBadVersion(version)) {
                return version;
            }
        }
        return n; // Fallback, though problem guarantees a bad version exists
        // Time: O(n)
        // Space: O(1)
    }
};

/* The isBadVersion API is defined in the parent class VersionControl.
      boolean isBadVersion(int version); */

public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        for (int version = 1; version <= n; version++) {
            if (isBadVersion(version)) {
                return version;
            }
        }
        return n; // Fallback, though problem guarantees a bad version exists
        // Time: O(n)
        // Space: O(1)
    }
}

/**
 * @param {number} n
 * @return {number}
 */
var firstBadVersion = function(isBadVersion) {
    return function(n) {
        for (let version = 1; version <= n; version++) {
            if (isBadVersion(version)) {
                return version;
            }
        }
        return n; // Fallback, though problem guarantees a bad version exists
        // Time: O(n)
        // Space: O(1)
    };
};

Why the Brute-Force Solution is Inefficient

The brute-force solution checks every version sequentially, leading to:

Time Complexity: O(n), where n is the total number of versions, as it may need to check all versions.
Space Complexity: O(1), as only a constant amount of extra space is used.
Performance Issue: For large n, the linear time complexity is inefficient, as the problem allows for a faster search method due to the sorted nature of version quality.

Optimal Solution

The optimal solution uses binary search to find the first bad version in O(log n) time complexity:

Initialize two pointers, left to 1 and right to n.
While left is less than right, compute the middle version as the average of left and right (integer division).
Call isBadVersion on the middle version.
If the middle version is bad, adjust right to middle to include it in the search for the first bad version.
If the middle version is not bad, adjust left to middle + 1 to search later versions.
Return left as the first bad version.

Code Solution (Optimal)

# The isBadVersion API is already defined for you.
# def isBadVersion(version: int) -> bool:
class Solution:
    def firstBadVersion(self, n: int) -> int:
        L = 1
        R = n

        while L < R:
            M = (L+R) // 2
            if isBadVersion(M):
                R = M
            else:
                L = M + 1
        
        return L 
        # Time: O(Log n)
        # Space: O(1)

// The API isBadVersion is defined for you.
// bool isBadVersion(int version);

class Solution {
public:
    int firstBadVersion(int n) {
        int i,j,k,c=0;
        int h=n,l=0,m;

        while(l<=h)
        {
            m=l+(h-l)/2;
            int res=isBadVersion(m);
            if(res==1 and (m==0 or isBadVersion(m-1)!=1)){
                return m;
            }
            else if(res==0){
                l=m+1;
            }else
            h=m-1;
        }
        return m;
        
    }
};

/* The isBadVersion API is defined in the parent class VersionControl.
boolean isBadVersion(int version); */

public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        if(n==1) return n;

        int start =1;
        int end = n;
        int badVersion = 1;
        while(start <= end){
            int mid = start +(end-start)/2;
            if(isBadVersion(mid)){
                badVersion = mid;
                end = mid-1;
            }
            else start=mid+1;
        }
        return badVersion;
        
    }
}

var solution = function (isBadVersion) {

    return function (n) {
        let low = 1;
        let high = n;
        let mid;
        while (low <= high) {
            mid = ~~(low + (high - low) / 2);
            if (isBadVersion(mid)) {
                if (isBadVersion(mid - 1)) high = mid - 1;
                else return mid;
            } else low = mid + 1;
        }
    }
};

Detailed Explanation

Understanding the Problem: First Bad Version

The “First Bad Version” problem asks us to find the earliest version of a product that fails quality control. You are given a function isBadVersion(version) which returns true if a version is bad and false otherwise. Versions are developed sequentially, and once a bad version appears, all subsequent versions are also bad.

Your task is to determine the first bad version out of n versions with the minimum number of calls to isBadVersion.

Why This Problem Matters

This problem is an application of binary search — a core algorithmic concept that enables efficient searching over sorted data. It also simulates real-world problems such as debugging a regression bug in a sequence of software builds or identifying the version that introduced a breaking change.

Optimal Approach: Binary Search for First Occurrence

Since the list of versions has a sorted property (all versions before the first bad one are good, and all after are bad), we can use binary search to efficiently locate the first bad version.

Steps:

Set two pointers: left = 1 and right = n.
While left < right:
- Compute mid = Math.floor((left + right) / 2).
- Call isBadVersion(mid):
  - If true, the first bad version could be mid or earlier → set right = mid.
  - If false, the first bad version is later → set left = mid + 1.
After the loop, left will point to the first bad version. Return left.

Example Walkthrough

Suppose n = 5 and isBadVersion returns true starting from version 4:

left = 1, right = 5 → mid = 3 → isBadVersion(3) = false → left = 4
left = 4, right = 5 → mid = 4 → isBadVersion(4) = true → right = 4
left = right = 4 → return 4

The first bad version is 4, and we found it using only two API calls instead of five.

Time and Space Complexity

Time Complexity: O(log n), as binary search cuts the search space in half each time.
Space Complexity: O(1), using constant additional space.

Edge Cases to Consider

First version is bad → should still return 1
Last version is bad → should scan correctly through entire list
Only one version → return 1 if it is bad

Conclusion

The “First Bad Version” problem is a classic binary search use case that highlights how to efficiently search for the first occurrence of a condition in a sorted dataset. It's highly relevant for software testing and debugging and teaches how to reduce API calls or checks in performance-critical applications.

Get Personalized Support at AlgoMap Bootcamp 💡

AlgoMap.io

Want Help Cracking FAANG?