Scale Engineer

First Bad Version

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

Prompt

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 <= 231 - 1

Approaches

2 approaches with complexity analysis and trade-offs.

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

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

Walkthrough

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

Time

O(n) - where n is the number of versions, as we might need to check all versions in the worst case

Space

O(1) - only using a constant amount of extra space

Trade-offs

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

Solutions

/* 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 walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem