🦇278. First Bad Version

Easy | Grind 75 | September 8th Thursday, 2022

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.

Constraints:

• 1 <= bad <= n <= 2^31 - 1

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

SOLUTION

This is a typical binary search question disguised in fancy wording. Suppose you are given a list of good and bad elements such as [good, good, good, bad, bad, bad]. To find the first "bad" version, You could do an O(n) linear search but the optimal solution would be to perform a binary search of O(logn) runtime. Binary search begins by finding the middle element of the given list. If the middle element is "good", the search space moves to the elements after the current middle. Similarly, if the middle element is "bad", we know all the elements after are "bad". However, we don't know if the current "bad" version was caused by a previous "bad" version. So, we shift the search space to the left of the middle element. This process is repeated until the first bad element is found. The only change from this to adapt to our question is to call the API with the middle index instead of referring to our list.

# The isBadVersion API is already defined for you.
# def isBadVersion(version: int) -> bool:

class Solution:
    def firstBadVersion(self, n: int) -> int:
        start = 0
        end = n 
        first_bad = None
        
        while start <= end: 
            mid = start + (end-start)//2
            
            # is the bad verison, move left
            if isBadVersion(mid): 
                first_bad = mid
                end = mid - 1
            
            # is not the bad verison, move right
            else: 
                start = mid + 1
        
        return first_bad
        
        

TIME AND SPACE COMPLEXITY

TIME: O(logn) where n is the number of versions (also n in the question). Every time we search, we shrink the next search space by half.

SPACE: O(1) we only use three integer variables that are constant regardless of the size of n.