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 - 1The key idea behind First Bad Version is recognizing that versions follow a monotonic pattern: once a bad version appears, all versions after it are also bad. This structure makes the problem ideal for Binary Search.
Instead of checking every version sequentially, you repeatedly divide the search space. Use the provided isBadVersion(version) API to determine whether the middle version is bad. If it is bad, the first bad version must be at that position or earlier, so you move the right boundary. If it is good, the first bad version must appear after it, so you shift the left boundary forward.
This approach efficiently narrows down the search range until the exact boundary between good and bad versions is found. Compared to a linear scan, binary search drastically reduces the number of API calls. The algorithm runs in O(log n) time with O(1) extra space, making it optimal for large inputs.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Binary Search | O(log n) | O(1) |
Techdose
This approach uses the concept of binary search to efficiently find the first bad version by minimizing the number of calls made to the given isBadVersion API. By leveraging binary search, we can reduce the problem set size by half with each iteration, therefore achieving O(log n) time complexity.
Time Complexity: O(log n)
Space Complexity: O(1)
1/**
2 * Definition for isBadVersion()
3 *
4 * @param {integer} version number
5 * @return {boolean} whether the version is bad
6 * isBadVersion = function(version) {
The JavaScript version adheres to the binary search approach. With each iteration, it checks whether the middle point indicates a bad version, adjusting the search range respectively till left pinpoint the first bad version.
This approach explores a recursive implementation of the binary search technique to identify the first bad version. Employing recursion allows the continual division of the search problem into smaller subproblems until the solution is found.
Time Complexity: O(log n)
Space Complexity: O(log n) - due to recursion stack
1
// Forward declaration of isBadVersion API.
bool isBadVersion(int version);
int binarySearch(int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2;
if (isBadVersion(mid)) return binarySearch(left, mid);
else return binarySearch(mid + 1, right);
}
return left;
}
class Solution {
public:
int firstBadVersion(int n) {
return binarySearch(1, n);
}
};Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, this problem is a common interview question at large tech companies. It tests understanding of binary search, boundary conditions, and how to minimize expensive API calls.
The optimal approach is binary search. Because versions change from good to bad only once, you can repeatedly check the middle version using the API and shrink the search range. This reduces the number of checks to logarithmic time.
Binary search works because the versions follow a monotonic pattern: all good versions appear before all bad ones. Once a bad version is found, the answer must lie at that index or earlier. This property allows efficient halving of the search space.
No special data structure is required for this problem. The solution mainly relies on index boundaries and the provided API to evaluate versions while applying the binary search technique.
The solution takes advantage of C++'s support for recursive functions to spot the first bad version through binarySearch. With each recursive call, it assesses the midpoint and adjusts the search range, seeking to locate the first bad version.