First Bad Version

EASY

Description

You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad.

Suppose you have n versions [1, 2, ..., n] and you want to find out the first bad one, which causes all the following ones to be bad.

You are given an API bool isBadVersion(version) which returns whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.

Example 1:

Input: n = 5, bad = 4
Output: 4
Explanation:
call isBadVersion(3) -> false
call isBadVersion(5) -> true
call isBadVersion(4) -> true
Then 4 is the first bad version.

Example 2:

Input: n = 1, bad = 1
Output: 1

Constraints:

1 <= bad <= n <= 2³¹ - 1

Approaches

Checkout 2 different approaches to solve First Bad Version. Click on different approaches to view the approach and algorithm in detail.

Linear Search

Iterate through each version from 1 to n and check if it's a bad version using the isBadVersion API. Return the first bad version found.

Algorithm

Start iterating from version 1 to n
For each version, call isBadVersion(version)
If isBadVersion returns true, return the current version
If no bad version is found, return n

The linear search approach is the most straightforward solution. We start checking each version from 1 up to n using the isBadVersion API. As soon as we find a bad version, we return it since it will be the first bad version (as all versions after a bad version are also bad).

public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        for (int version = 1; version <= n; version++) {
            if (isBadVersion(version)) {
                return version;
            }
        }
        return n;
    }
}

In this approach, we simply use a for loop to check each version. When we find the first bad version, we return it immediately.

Complexity Analysis

Time Complexity: O(n) - where n is the number of versions, as we might need to check all versions in the worst caseSpace Complexity: O(1) - only using a constant amount of extra space

Pros and Cons

Pros:

Simple and easy to understand
Works for small inputs
Minimal space requirement

Cons:

Inefficient for large inputs
Makes too many API calls
Does not minimize the number of calls to the API as required

Code Solutions

Checking out 4 solutions in different languages for First Bad Version. Click on different languages to view the code.

/* The isBadVersion API is defined in the parent class VersionControl. boolean isBadVersion(int version); */ public class Solution extends VersionControl { public int firstBadVersion ( int n ) { int left = 1 , right = n ; while ( left < right ) { int mid = ( left + right ) >>> 1 ; if ( isBadVersion ( mid )) { right = mid ; } else { left = mid + 1 ; } } return left ; } }

Video Solution

Watch the video walkthrough for First Bad Version

Algorithms:

Binary Search