278. First Bad Version
Problem Description
You are a product manager overseeing the development of a new product, which unfortunately has some versions failing the quality check. Versions of this product are built sequentially where each version builds upon the previous one. If any version is discovered to be faulty, all subsequent versions will inherit this fault.
Your task is to efficiently determine the first version where the defect was introduced, given that subsequent versions will be defective as well. You have n
versions labeled from 1
to n
. To assist in identifying the defective version, you have access to a provided API function isBadVersion(version)
that will return true
if the version is bad, and false
otherwise.
The goal is to minimize the number of API calls you make to isBadVersion
.
Intuition
To solve this problem, a binary search algorithm is an ideal approach. Binary search is applied because we know the versions are ordered from good to bad and the first bad version triggers all the following versions to be bad as well. This creates a sorted pattern of good and bad versions, which is perfect for binary search.
Initially, we know the right boundary (right
) of our search space is n
(the last version) and the left boundary (left
) is 1
(the first version). To minimize the calls to the API, we avoid searching versions sequentially. Instead, we calculate the middle point (mid
) of the current search space and use the isBadVersion
API to check if mid
is a bad version.
If mid
is bad, we know that the first bad version must be at mid
or before mid
, so we set right
to mid
. If not, we know that the first bad version must be after mid
, so we update left
to be mid + 1
. This halves the search space with each iteration.
Repeatedly narrowing the search space like this leads us to converge on the first bad version without checking every version. The loop terminates when left
and right
meet, which is when we have found the first bad version. By utilizing this method, the number of calls we make to the API is reduced to O(log n)
, which is the time complexity of a binary search.
Learn more about Binary Search patterns.
Solution Approach
The solution implements a classic binary search strategy to find the first bad version. This method significantly reduces the time complexity from O(n)
to O(log n)
. Let's walk through the implementation of the solution:
-
We start by initializing two pointers,
left
andright
.left
starts at 1, which represents the first version, andright
starts atn
, which represents the last version. They mark the boundaries of our search space. -
We enter a while loop that will continue running as long as
left
is less thanright
. Inside this loop, we will repeatedly narrow down our search space by inspecting the midpoint ofleft
andright
. -
To calculate the midpoint, we use the expression
(left + right) >> 1
, which is equivalent to(left + right) / 2
but faster computationally as it involves bit-shifting to the right by one bit to do integer division by two. We assign this value to the variablemid
. -
The
isBadVersion(mid)
call tells us whether the midpoint version is bad. If it is, we know the target bad version must be less than or equal tomid
. So, we setright
tomid
, indicating our search space has shifted to the left half fromleft
tomid
. -
Conversely, if
isBadVersion(mid)
returnsfalse
, it means that the first bad version is somewhere aftermid
. Hence, we setleft
tomid + 1
, indicating our search space has shifted to the right half excludingmid
. -
The loop continues, and with each iteration, the range
[left, right]
narrows down untilleft
equalsright
. At this point,left
(or equivalentlyright
) points to the first bad version.
With the binary search pattern applied, we not only find the correct answer but also optimize performance by making the least number of calls necessary to isBadVersion
, satisfying the problem's constraint to minimize API calls. Once the loop finishes, we return left
as it will be the index of the first bad version.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Suppose we have 5 versions of a product and we know that one of the middle versions introduced a defect. Our isBadVersion
API functions as follows for these 5 versions:
isBadVersion(1)
returnsfalse
isBadVersion(2)
returnsfalse
isBadVersion(3)
returnstrue
isBadVersion(4)
returnstrue
isBadVersion(5)
returnstrue
Using the binary search approach, we start with left = 1
and right = 5
. We perform the following steps to identify the first bad version:
-
First, take the midpoint of
left
(1) andright
(5). The midpointmid
is calculated as(1 + 5) >> 1
which equates to 3. -
We check
isBadVersion(3)
and it returnstrue
. Becausemid
is bad, we know all versions after 3 are also bad. So, we setright
tomid
, changing our range from[1, 5]
to[1, 3]
. -
Next, we recalculate the midpoint of the new range. With
left
still at 1 andright
at 3, the newmid
is(1 + 3) >> 1
, which equals 2. -
We call
isBadVersion(2)
and it returnsfalse
. Now we know the first bad version must be greater thanmid
. So we updateleft
tomid + 1
, changing our range from[1, 3]
to[3, 3]
. -
Since
left
andright
meet and the loop terminates, we conclude that the first bad version is 3.
By following this example, the approach narrows down the search space efficiently and we find the first bad version which is 3, with just two API calls to isBadVersion
instead of five, which would have been the case if we had checked each version sequentially. This demonstrates the effectiveness of the binary search technique.
Solution Implementation
1# Assume the isBadVersion API is already defined.
2# @param version: int => An integer representing the version
3# @return bool => True if the version is bad, False otherwise
4# def isBadVersion(version):
5
6
7class Solution:
8 def firstBadVersion(self, n: int) -> int:
9 """
10 Utilize binary search to find the first bad version out of 'n' versions.
11 If a bad version is found, then all subsequent versions are also bad.
12
13 :type n: int The total number of versions to check.
14 :rtype: int The first bad version number.
15 """
16 # Initialize the search space
17 left, right = 1, n
18 # Loop until the search space is reduced to one element
19 while left < right:
20 # Calculate the middle point to divide the search space
21 mid = left + (right - left) // 2
22 # If mid is a bad version, the first bad version is in the left half
23 if isBadVersion(mid):
24 right = mid # Narrow the search to the left half
25 else:
26 left = mid + 1 # Narrow the search to the right half
27
28 # At this point, left is the first bad version
29 return left
30
1public class Solution extends VersionControl {
2 /**
3 * Finds the first version that is bad.
4 *
5 * @param n Total number of versions.
6 * @return The first bad version number.
7 */
8 public int firstBadVersion(int n) {
9 // Initialize pointers for the range start and end.
10 int start = 1;
11 int end = n;
12
13 // Continue searching while the range has more than one version.
14 while (start < end) {
15 // Calculate the middle version of the current range.
16 // Using unsigned right shift operator to avoid integer overflow.
17 int mid = start + (end - start) / 2;
18
19 // Check if the middle version is bad.
20 if (isBadVersion(mid)) {
21 // If the middle version is bad, the first bad version
22 // is before it or it is the first bad version itself.
23 end = mid;
24 } else {
25 // If the middle version is good, the first bad version
26 // must be after it.
27 start = mid + 1;
28 }
29 }
30
31 // At this point, start == end and it is the first bad version.
32 return start;
33 }
34}
35
1// The API isBadVersion is defined for you.
2// bool isBadVersion(int version);
3
4class Solution {
5public:
6 // Function to find the first bad version in a sequence of versions
7 int firstBadVersion(int n) {
8 int left = 1; // Initialize the left boundary of the search range
9 int right = n; // Initialize the right boundary of the search range
10
11 // Perform a binary search to narrow down the first bad version
12 while (left < right) {
13 // Use bitwise shift to avoid the potential overflow of (left + right)
14 int mid = left + ((right - left) >> 1);
15
16 // Check if the middle version is bad
17 if (isBadVersion(mid)) {
18 // If it is bad, we know that the first bad version must be at or before 'mid'
19 right = mid; // Reset the right boundary to 'mid'
20 } else {
21 // If it is not bad, the first bad version must be after 'mid'
22 left = mid + 1; // Reset the left boundary to one after 'mid'
23 }
24 }
25
26 // At the end of the loop, 'left' will be the first bad version
27 return left;
28 }
29};
30
1/**
2 * The `isBadVersion` function is a predicate that determines whether
3 * a given software version is bad. The actual implementation is unspecified.
4 *
5 * @param version - The version number to check.
6 * @returns `true` if the specified version is bad, otherwise `false`.
7 */
8type IsBadVersion = (version: number) => boolean;
9
10/**
11 * This function is a higher-order function that takes in the `isBadVersion` function
12 * and returns a nested function that can be used to find the first bad version.
13 *
14 * @param isBadVersion - A function to determine whether a given version is bad.
15 * @returns A function that accepts the total number of versions `n` and returns the
16 * first bad version found.
17 */
18const solution = (isBadVersion: IsBadVersion): ((n: number) => number) => {
19 /**
20 * This inner function uses binary search to efficiently find the first bad version
21 * within the total number of versions `n`.
22 *
23 * @param n - The total number of versions to search through.
24 * @returns The first bad version number within the total versions.
25 */
26 return (n: number): number => {
27 let left: number = 1;
28 let right: number = n;
29 while (left < right) {
30 // Use Math.floor to ensure the result is an integer after the division.
31 const midpoint: number = left + Math.floor((right - left) / 2);
32 if (isBadVersion(midpoint)) {
33 right = midpoint;
34 } else {
35 left = midpoint + 1;
36 }
37 }
38 // At this point, 'left' is the first bad version.
39 return left;
40 };
41};
42
Time and Space Complexity
The given code snippet uses a binary search algorithm to find the first bad version among n
versions. The binary search successively divides the range of the search in half, narrowing down on the first bad version.
Time Complexity
The time complexity of this algorithm is O(log n)
. This is because with each comparison, it effectively halves the search space, which is a characteristic of binary search. As such, the number of comparisons needed to find the target is proportional to the logarithm of the total number of versions n
.
Space Complexity
The space complexity of this algorithm is O(1)
. This is because it uses a fixed amount of space; only two variables left
and right
are used to keep track of the search space, and the mid
variable is used for the computations. No additional space is dependent on the input size n
.
Learn more about how to find time and space complexity quickly using problem constraints.
Is the following code DFS or BFS?
void search(Node root) { if (!root) return; visit(root); root.visited = true; for (Node node in root.adjacent) { if (!node.visited) { search(node); } } }
Recommended Readings
Binary Search Speedrun For each of the Speedrun questions you will be given a binary search related problem and a corresponding multiple choice question The multiple choice questions are related to the techniques and template s introduced in the binary search section It's recommended that you have gone through at
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Want a Structured Path to Master System Design Too? Donāt Miss This!