First Bad Version

Q: What is the best time complexity for First Bad Version?

Optimal (first true with binary search) runs in O(log n) time and O(1) extra space.

Q: Which pattern does First Bad Version use?

It is a binary search problem that uses the unique 1-d binary search pattern. Other problems with the same pattern: Single Element in a Sorted Array, Find Peak Element.

Q: Is there a brute force solution for First Bad Version?

Yes. Linear scan takes O(n) time and O(1) space. Call isBadVersion from 1 upward and return the first true.

Q: Which edge cases should I test for First Bad Version?

n near 2^31 - 1 (lo + hi overflows); The first version is bad.

Easy Binary Search Unique 1-D Binary Search Original on LeetCode

First Bad Version is a easy binary search problem solved with the unique 1-d binary search pattern. The best approach, optimal (first true with binary search), runs in O(log n) time and O(1) space. Below are 2 approaches in Java, from linear scan up.

Problem

You have versions 1..n of a product. Once a version is bad, every version after it is bad too. Using an API isBadVersion(v), find the first bad version while making as few calls as possible.

Examples

Example 1

Input: n = 6, first bad = 4
Output: 4
Why: isBadVersion(3) = false, isBadVersion(4) = true.

Example 2

Input: n = 1, first bad = 1
Output: 1

Constraints

1 <= bad <= n <= 2^31 - 1
Minimise calls to isBadVersion.

Animated walkthrough

A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.

Concepts first, then the problem and every approach, step by step.

Code

Code appears here once we start writing it.

Space to play or pause · ← → to jump a step · click or drag the bar to seek

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the Java code.

Approach	Time	Space
Linear scan	`O(n)`	`O(1)`
Optimal (first true with binary search)	`O(log n)`	`O(1)`

1Linear scan

TimeO(n)

SpaceO(1)

Call isBadVersion from 1 upward and return the first true.

for v = 1..n: if isBadVersion(v) return v.

Java

public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        for (int v = 1; v < n; v++) if (isBadVersion(v)) return v;
        return n;
    }
}

2Optimal (first true with binary search)

TimeO(log n)

SpaceO(1)

The results are monotonic: once a version is bad, all later ones are. Search for the first bad version with the half-open template, using lo + (hi - lo) / 2 to avoid overflow.

lo = 1, hi = n.
While lo < hi: if isBadVersion(mid) hi = mid else lo = mid + 1.
Return lo.

Java

public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        int lo = 1, hi = n;
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (isBadVersion(mid)) hi = mid; else lo = mid + 1;
        }
        return lo;
    }
}

Edge cases to test

n near 2^31 - 1 (lo + hi overflows)
The first version is bad

Hints

Hint 1

The answers look like false, false, ..., true, true: find the first true.

FAQ

What is the best time complexity for First Bad Version?

Optimal (first true with binary search) runs in O(log n) time and O(1) extra space.

Which pattern does First Bad Version use?

It is a binary search problem that uses the unique 1-d binary search pattern. Other problems with the same pattern: Single Element in a Sorted Array, Find Peak Element.

Is there a brute force solution for First Bad Version?

Yes. Linear scan takes O(n) time and O(1) space. Call isBadVersion from 1 upward and return the first true.

Which edge cases should I test for First Bad Version?

n near 2^31 - 1 (lo + hi overflows); The first version is bad.