We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

First Bad Version

Difficulty: Easy

Problem Description

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.

Key Insights

  • The problem can be approached using binary search due to the ordered nature of the versions.
  • Once a bad version is found, all subsequent versions are also bad, allowing us to narrow our search range.
  • The goal is to minimize the number of API calls to isBadVersion by efficiently dividing the search space.

Space and Time Complexity

Time Complexity: O(log n)
Space Complexity: O(1)

Solution

The solution leverages a binary search algorithm to efficiently find the first bad version. By maintaining two pointers, left and right, we repeatedly narrow down the search space based on the results of the isBadVersion API call. If the middle version is bad, we search to the left; otherwise, we search to the right. The process continues until the left pointer meets the right pointer, which will point to the first bad version.

Code Solutions

def isBadVersion(version):
    # This is a mock function. In practice, this would be provided.
    pass

def firstBadVersion(n):
    left, right = 1, n
    while left < right:
        mid = left + (right - left) // 2
        if isBadVersion(mid):
            right = mid  # Search in the left half
        else:
            left = mid + 1  # Search in the right half
    return left  # left is the first bad version
← Back to All Questions