First Bad Version
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, Python, C++ and JavaScript, 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.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 4 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
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.
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 code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Linear scan | O(n) | O(1) |
| Optimal (first true with binary search) | O(log n) | O(1) |
1Linear scan
O(n)O(1)Call isBadVersion from 1 upward and return the first true.
- for v = 1..n: if isBadVersion(v) return v.
public class Solution extends VersionControl {
public int firstBadVersion(int n) {
for (int v = 1; v < n; v++) if (isBadVersion(v)) return v;
return n;
}
}class Solution:
def firstBadVersion(self, n: int) -> int:
for v in range(1, n):
if isBadVersion(v):
return v
return nclass Solution {
public:
int firstBadVersion(int n) {
for (int v = 1; v < n; v++) if (isBadVersion(v)) return v;
return n;
}
};function firstBadVersion(n) {
for (let v = 1; v < n; v++) if (isBadVersion(v)) return v;
return n;
}2Optimal (first true with binary search)
O(log n)O(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.
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;
}
}class Solution:
def firstBadVersion(self, n: int) -> int:
lo, hi = 1, n
while lo < hi:
mid = lo + (hi - lo) // 2
if isBadVersion(mid):
hi = mid
else:
lo = mid + 1
return loclass Solution {
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;
}
};function firstBadVersion(n) {
let lo = 1, hi = n;
while (lo < hi) {
const mid = lo + Math.floor((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.