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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

First Bad Version

Number: 278

Difficulty: Easy

Paid? No

Companies: Google, Meta, Microsoft, Amazon, Apple, Adobe, Uber, TikTok

Problem Description

Given n versions [1, 2, ..., n] and an API isBadVersion(version) that returns whether a version is bad, determine the first bad version. Once a bad version is identified, all subsequent versions are bad, and the goal is to minimize the number of API calls.

Key Insights

  • The API returns true for bad versions and all versions after a bad version.
  • The problem is essentially about finding a transition point in a sorted sequence which calls for a binary search approach.
  • The aim is to minimize the number of calls to isBadVersion by leveraging the ordered nature of the versions.

Space and Time Complexity

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

Solution

We use binary search to efficiently locate the first bad version. Initialize two pointers, left and right, at 1 and n respectively. At each step, compute the mid point and call isBadVersion(mid). If mid is bad, it indicates that the first bad version may be mid or to its left, so adjust right to mid. Otherwise, adjust left to mid + 1. Continue the process until the pointers converge. The converged pointer will be the first bad version. Key structures include simple integer variables for left, right, and mid, with binary search being the fundamental algorithm to reduce the search space logarithmically.

Code Solutions

# Python implementation of First Bad Version
class Solution:
    def firstBadVersion(self, n: int) -> int:
        # Initialize the left pointer to the first version and right pointer to the last version
        left, right = 1, n
        while left < right:
            # Calculate the mid point to avoid potential overflow
            mid = left + (right - left) // 2
            # Call the API isBadVersion to check if mid version is bad
            if isBadVersion(mid):
                # If mid is bad, search the left half including mid
                right = mid
            else:
                # If mid is not bad, search the right half excluding mid
                left = mid + 1
        # When left equals right, we found the first bad version
        return left
← Back to All Questions