First Bad Version

LeetCode 278 | Difficulty: Easy

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.

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 <= 2^31 - 1`

Topics: Binary Search, Interactive

---

Approach

Binary Search

Binary search reduces the search space by half at each step. The key insight is identifying the monotonic property — what condition lets you decide to go left or right?

When to use

Sorted array, or searching for a value in a monotonic function/space.

---

Solutions

Solution 1: C# (Best: 41 ms)

Metric	Value
Runtime	41 ms
Memory	25.2 MB
Date	2021-11-25

Solution

/* The isBadVersion API is defined in the parent class VersionControl.
      bool IsBadVersion(int version); */

public class Solution : VersionControl {
    public int FirstBadVersion(int n) {
        int l=1, r = n;
        int ans = -1;
        while(l<=r)
        {
            int mid = l + (r-l)/2;
           
            if(IsBadVersion(mid))
            {
                ans = mid;
                r = mid-1;
            }
            else l = mid+1;
        }
        return ans;
    }
}

📜 1 more C# submission(s)

Submission (2021-11-25) — 47 ms, 25.4 MB

/* The isBadVersion API is defined in the parent class VersionControl.
      bool IsBadVersion(int version); */

public class Solution : VersionControl {
    public int FirstBadVersion(int n) {
        int l=1, r = n;
        int ans = -1;
        while(l<=r)
        {
            int mid = l + (r-l)/2;
            bool isMidBad = IsBadVersion(mid);
            if(isMidBad)
            {
                ans = mid;
                r = mid-1;
            }
            else l = mid+1;
        }
        return ans;
    }
}

---

Complexity Analysis

Approach	Time	Space
Binary Search	$O(log n)$	$O(1)$

---

Interview Tips

Key Points

• Start by clarifying edge cases: empty input, single element, all duplicates.
• Precisely define what the left and right boundaries represent, and the loop invariant.