#278 First Bad Version
the problem
In plain words
Your product has versions 1 to n. One version was bad, and every version built after it is bad too. You may call isBadVersion(version) — LeetCode provides it through a parent class VersionControl that your Solution extends. Return the first bad version, calling the API as few times as you can.
in n = 5, bad = 4
out 4
isBadVersion(3) = false, isBadVersion(4) = true, isBadVersion(5) = true — so 4 is the first bad one.
in n = 1, bad = 1
out 1
- 1 ≤ bad ≤ n ≤ 2³¹ − 1
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternBinary search (exact & bounds)
where this runsgit bisect runs this exact search over your commit history to find the commit that introduced a bug.
isBadVersion(1), …, isBadVersion(n) reads false, false, …, true, true — a sorted row of booleans. Find the first true with the boundary template. Because n can be 2³¹ − 1, lo + hi overflows: compute mid as lo + (hi − lo) / 2.
solutions
From brute force to optimal
Ask about version 1, 2, 3, … and return the first bad one.
- For v = 1 to n − 1: if isBadVersion(v), return v.
- Otherwise the bad one must be n.
Up to n − 1 calls — about 2·10⁹ when n = 2³¹ − 1.
One counter.
class Solution extends VersionControl { public int firstBadVersion(int n) { for (int v = 1; v < n; v++) { if (isBadVersion(v)) return v; // the first bad one we meet } return n; // a bad version always exists, so it must be n }}Keep the first bad version inside [lo, hi]. A bad mid might be the answer, so keep it (hi = mid); a good mid can't be (lo = mid + 1).
- lo = 1, hi = n.
- While lo < hi: mid = lo + (hi − lo) / 2.
- isBadVersion(mid) → hi = mid; else lo = mid + 1.
- Return lo.
Each call halves [lo, hi]: at most ⌈log₂ n⌉ = 31 calls for n = 2³¹ − 1.
Three ints.
class Solution extends VersionControl { public int firstBadVersion(int n) { int lo = 1, hi = n; // the first bad version is in [lo, hi] while (lo < hi) { int mid = lo + (hi - lo) / 2; // (lo + hi) / 2 overflows when n is near 2^31 if (isBadVersion(mid)) hi = mid; // mid is bad: the first bad is mid or earlier else lo = mid + 1; // mid is good: the first bad comes after mid } return lo; // lo == hi: the first bad version }}Dry run
in the room
How to say it in the interview
talk track
- Restate it: the answers look like F…F T…T, and I want the first T.
- Pick the boundary template and say why hi = mid: a bad mid might itself be the first bad version.
- Mention the overflow before writing mid — n can be 2³¹ − 1, so lo + hi doesn't fit in an int.
- Count the calls: at most ⌈log₂ n⌉ — 31 here.
traps
(lo + hi) / 2overflows for big n — mid goes negative and the API is asked about a version that doesn't exist.hi = mid − 1after a bad mid can skip the answer when mid is the first bad version.- Returning mid on the first bad hit inside the loop — it is bad, but maybe not the first.
what they ask next
Follow-ups
What if each check is slow — a full build and test run?
That's git bisect: you mark commits good or bad and it halves the range each time. Binary search is the best you can do with a yes/no check: about ⌈log₂ n⌉ checks.
What if some versions can't be tested (the build is broken)?
git bisect skip handles that by trying a nearby version instead; the search can then take a few more steps.
before you submit
Edge cases to test
- n = 1: version 1 is the bad one.
- Every version is bad (bad = 1), or only the last one is (bad = n).
- n = 2³¹ − 1: lo + hi overflows an int, and checking one by one would take up to 2·10⁹ calls.
practise next
Similar problems
- #35Search Insert PositionEasyin Binary Search
- #34Find First and Last Position of Element in Sorted ArrayMediumin Binary Search
- #875Koko Eating BananasMediumin Binary Search