First Bad Version
EasyPrompt
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
- 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
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
Use binary search to efficiently find the first bad version by eliminating half of the search space in each step.
Algorithm
- Initialize left = 1 and right = n
- While left < right:
- Calculate mid = left + (right - left) / 2
- If isBadVersion(mid) is true, set right = mid
- If isBadVersion(mid) is false, set left = mid + 1
- Return left
Walkthrough
The binary search approach is optimal for this problem as it minimizes the number of API calls. Since all versions after a bad version are also bad, we can use binary search to find the transition point from good to bad versions.
public class Solution extends VersionControl { public int firstBadVersion(int n) { int left = 1; int right = n; while (left < right) { int mid = left + (right - left) / 2; if (isBadVersion(mid)) { right = mid; } else { left = mid + 1; } } return left; }}In this approach:
- We maintain two pointers, left and right, initially pointing to 1 and n respectively
- We calculate the middle point using mid = left + (right - left) / 2 to avoid integer overflow
- If the middle version is bad, we know the first bad version is either this one or earlier
- If the middle version is good, we know the first bad version must be after this one
- We continue this process until left and right converge to the first bad version
Complexity
Time
O(log n) - where n is the number of versions, as we divide the search space in half in each iteration
Space
O(1) - only using a constant amount of extra space
Trade-offs
Pros
Efficient logarithmic time complexity
Minimizes the number of API calls
Works well for large inputs
Handles integer overflow properly
Cons
Slightly more complex implementation than linear search
Requires understanding of binary search concept
Solutions
Solution
/* 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 ; } }/** * Definition for isBadVersion() * * @param {integer} version number * @return {boolean} whether the version is bad * isBadVersion = function(version) { * ... * }; */ /** * @param {function} isBadVersion() * @return {function} */ var solution = function ( isBadVersion ) { /** * @param {integer} n Total versions * @return {integer} The first bad version */ return function ( n ) { let left = 1 ; let right = n ; while ( left < right ) { const mid = ( left + right ) >>> 1 ; if ( isBadVersion ( mid )) { right = mid ; } else { left = mid + 1 ; } } return left ; }; };// The API isBadVersion is defined for you. // bool isBadVersion(int version); class Solution { public: int firstBadVersion ( int n ) { int left = 1 , right = n ; while ( left < right ) { int mid = left + (( right - left ) >> 1 ); if ( isBadVersion ( mid )) { right = mid ; } else { left = mid + 1 ; } } return left ; } };# The isBadVersion API is already defined for you. # @param version, an integer # @return an integer # def isBadVersion(version): class Solution : def firstBadVersion ( self , n ): """ :type n: int :rtype: int """ left , right = 1 , n while left < right : mid = ( left + right ) >> 1 if isBadVersion ( mid ): right = mid else : left = mid + 1 return leftVideo 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.