First Bad Version solution and explanation
Google
9 more videos on this problem
First bad version | Leetcode #278Techdose · 4:44 · 55K views
LeetCode First Bad Version Solution Explained - JavaNick White · 3:30 · 32K views
First Bad Version - Leetcode 278 - Binary Search (Python)Greg Hogg · 8:12 · 14K views
LeetCode 278. First Bad Version - Interview Prep Ep 74Fisher Coder · 7:09 · 3K views
First Bad Version - LeetCode 278 - Coding Interview QuestionsOne Code Man · 4:02 · 2K views
FIRST BAD VERSION | LEETCODE 278 | PYTHON BINARY SEARCH SOLUTIONCracking FAANG · 8:35 · 2K views
LeetCode Tutorial 278. First Bad VersionGoodTecher · 10:43 · 2K views
LeetCode 278. First Bad Version | JSer - JavaScript & AlgorithmJSer · 7:29 · 1K views
LeetCode 278: First Bad Version Solution Explained | Binary Search ApproachPrepflix · 9:29 · 734 views
278. First Bad Version || using C++ || Leetcode Problem || Binary search topicCogent Coder · 9:50 · 194 views
The problem
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 <= 231 - 1
Approach overview
Problem Overview: You receive n product versions and an API isBadVersion(version). Once a version becomes bad, every version after it is also bad. The goal is to find the first bad version while minimizing API calls.
Approach 1: Linear Scan (O(n) time, O(1) space)
The most straightforward strategy is checking each version sequentially from 1 to n. Call isBadVersion(i) for every version until the API returns true. The first time it returns true is the answer. This works because versions before the first bad one are guaranteed to be good. The downside is efficiency: in the worst case you call the API n times, which becomes expensive for very large inputs.
Approach 2: Binary Search Optimization (O(log n) time, O(1) space)
The key observation is that the versions form a monotonic pattern: a sequence of good versions followed by bad ones. That structure makes the problem ideal for binary search. Start with a search range [1, n]. Check the middle version. If isBadVersion(mid) is true, the first bad version lies in the left half (including mid). Otherwise, it must be in the right half. Narrow the search range until left == right. That index is the first bad version. This approach drastically reduces API calls from O(n) to O(log n).
Approach 3: Recursive Binary Search Method (O(log n) time, O(log n) space)
This version applies the same binary search idea but uses recursion instead of a loop. Each recursive call splits the search range and evaluates isBadVersion(mid). If the mid version is bad, recurse into the left half; otherwise recurse into the right half. The logic mirrors divide-and-conquer patterns common in binary search and interactive API problems. The time complexity remains O(log n), but recursion adds a call stack cost of O(log n).
Recommended for interviews: Interviewers expect the binary search solution. The linear scan proves you understand the problem constraints, but it fails scalability requirements. Implementing the iterative binary search shows you recognize the monotonic property and can minimize expensive API calls—exactly the optimization interviewers look for in search problems.
Approach 1: Binary Search Optimization
This approach uses the concept of binary search to efficiently find the first bad version by minimizing the number of calls made to the given isBadVersion API. By leveraging binary search, we can reduce the problem set size by half with each iteration, therefore achieving O(log n) time complexity.
class Solution:
def firstBadVersion(self, n: int) -> int:
left, right = 1, n
while left < right:
mid = left + (right - left) // 2
if isBadVersion(mid):
right = mid
else:
left = mid + 1
return leftpublic class Solution extends VersionControl {
public int firstBadVersion(int n) {
int left = 1, right = n;
while (left < right) {
int mid = left + (right - left) / 2;
if (isBadVersion(mid)) right = mid;
else left = mid + 1;
}
return left;
}
}#include <stdbool.h>
// Forward declaration of isBadVersion API.
bool isBadVersion(int version);
class Solution {
public:
int firstBadVersion(int n) {
int left = 1, right = n;
while (left < right) {
int mid = left + (right - left) / 2;
if (isBadVersion(mid)) right = mid;
else left = mid + 1;
}
return left;
}
};/**
* Definition for isBadVersion()
*
* @param {integer} version number
* @return {boolean} whether the version is bad
* isBadVersion = function(version) {
* ...
* };
*/
/**
* @param {function} isBadVersion()
* @return {function}
*/
var solution = function(isBadVersion) {
/**
* @param {integer} n Total versions
* @return {integer} The first bad version
*/
return function(n) {
let left = 1, right = n;
while (left < right) {
let mid = Math.floor(left + (right - left) / 2);
if (isBadVersion(mid)) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
};
};#include <stdbool.h>
// Forward declaration of isBadVersion API.
bool isBadVersion(int version);
int firstBadVersion(int n) {
int left = 1, right = n;
while (left < right) {
int mid = left + (right - left) / 2;
if (isBadVersion(mid)) right = mid;
else left = mid + 1;
}
return left;
}public class Solution : VersionControl {
public int FirstBadVersion(int n) {
int left = 1, right = n;
while (left < right) {
int mid = left + (right - left) / 2;
if (IsBadVersion(mid)) right = mid;
else left = mid + 1;
}
return left;
}
}The Python implementation adopts the same binary search approach. The function initializes the left and right pointers, then iteratively refines the search range based on the evaluation provided by isBadVersion. The first bad version is identified when left converges with right.
Time Complexity: O(log n)
Space Complexity: O(1)
Approach 2: Recursive Binary Search Method
This approach explores a recursive implementation of the binary search technique to identify the first bad version. Employing recursion allows the continual division of the search problem into smaller subproblems until the solution is found.
class Solution:
def binarySearch(self, left: int, right: int) -> int:
if left < right:
mid = left + (right - left) // 2
if isBadVersion(mid):
return self.binarySearch(left, mid)
else:
return self.binarySearch(mid + 1, right)
return left
def firstBadVersion(self, n: int) -> int:
return self.binarySearch(1, n)public class Solution extends VersionControl {
private int binarySearch(int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2;
if (isBadVersion(mid)) return binarySearch(left, mid);
else return binarySearch(mid + 1, right);
}
return left;
}
public int firstBadVersion(int n) {
return binarySearch(1, n);
}
}#include <stdbool.h>
// Forward declaration of isBadVersion API.
bool isBadVersion(int version);
int binarySearch(int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2;
if (isBadVersion(mid)) return binarySearch(left, mid);
else return binarySearch(mid + 1, right);
}
return left;
}
class Solution {
public:
int firstBadVersion(int n) {
return binarySearch(1, n);
}
};/**
* Definition for isBadVersion()
*
* @param {integer} version number
* @return {boolean} whether the version is bad
* isBadVersion = function(version) {
* ...
* };
*/
/**
* @param {function} isBadVersion()
* @return {function}
*/
var solution = function(isBadVersion) {
/**
* @param {integer} n Total versions
* @return {integer} The first bad version
*/
function binarySearch(left, right) {
if (left < right) {
let mid = Math.floor(left + (right - left) / 2);
if (isBadVersion(mid)) {
return binarySearch(left, mid);
} else {
return binarySearch(mid + 1, right);
}
}
return left;
}
return function(n) {
return binarySearch(1, n);
};
};#include <stdbool.h>
// Forward declaration of isBadVersion API.
bool isBadVersion(int version);
int binarySearch(int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2;
if (isBadVersion(mid)) return binarySearch(left, mid);
else return binarySearch(mid + 1, right);
}
return left;
}
int firstBadVersion(int n) {
return binarySearch(1, n);
}public class Solution : VersionControl {
private int BinarySearch(int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2;
if (IsBadVersion(mid)) return BinarySearch(left, mid);
else return BinarySearch(mid + 1, right);
}
return left;
}
public int FirstBadVersion(int n) {
return BinarySearch(1, n);
}
}This Python solution embeds a binarySearch helper function to recursively zero in on the first bad version. Each call analyzes the status of the mid-point version, narrowing the searcher's focus until the exact location of the first bad version is discerned.
Time Complexity: O(log n)
Space Complexity: O(log n) - due to recursion stack
Approach 3: Binary Search
We define the left boundary of the binary search as l = 1 and the right boundary as r = n.
While l < r, we calculate the middle position mid = \left\lfloor \frac{l + r}{2} \right\rfloor, then call the isBadVersion(mid) API. If it returns true, it means the first bad version is between [l, mid], so we set r = mid; otherwise, the first bad version is between [mid + 1, r], so we set l = mid + 1.
Finally, we return l.
The time complexity is O(log n), and the space complexity is O(1).
/**
* The knows API is defined in the parent class Relation.
* isBadVersion(version: number): boolean {
* ...
* };
*/
var solution = function (isBadVersion: any) {
return function (n: number): number {
let [l, r] = [1, n];
while (l < r) {
const mid = (l + r) >>> 1;
if (isBadVersion(mid)) {
r = mid;
} else {
l = mid + 1;
}
}
return l;
};
};/**
* Forward declaration of isBadVersion API.
* @param version your guess about first bad version
* @return true if current version is bad
* false if current version is good
* func isBadVersion(version int) bool;
*/
func firstBadVersion(n int) int {
l, r := 1, n
for l < r {
mid := (l + r) >> 1
if isBadVersion(mid) {
r = mid
} else {
l = mid + 1
}
}
return l
}// The API isBadVersion is defined for you.
// isBadVersion(version:i32)-> bool;
// to call it use self.isBadVersion(version)
impl Solution {
pub fn first_bad_version(&self, n: i32) -> i32 {
let (mut l, mut r) = (1, n);
while l < r {
let mid = l + (r - l) / 2;
if self.isBadVersion(mid) {
r = mid;
} else {
l = mid + 1;
}
}
l
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Binary Search Optimization | Time Complexity: |
| Recursive Binary Search Method | Time Complexity: |
| Binary Search | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Linear Scan | O(n) | O(1) | Simple baseline solution or when n is very small |
| Binary Search Optimization | O(log n) | O(1) | Optimal approach when versions follow a monotonic good→bad pattern |
| Recursive Binary Search | O(log n) | O(log n) | When recursion is preferred for divide-and-conquer clarity |
Frequently asked questions
Is First Bad Version easy or hard?
First Bad Version is categorized as an Easy problem on LeetCode. The implementation is short, but it tests whether you recognize the monotonic pattern and apply binary search correctly to minimize API calls.
First Bad Version Python/Java solution
Both Python and Java implementations follow the same binary search pattern. Maintain left and right boundaries, check the middle version using isBadVersion, and shrink the search space accordingly. The final index where left equals right is the first bad version with O(log n) time complexity.
How to solve First Bad Version in O(log n)?
Use binary search on the version range from 1 to n. Compute mid and call isBadVersion(mid). If mid is bad, move the right boundary to mid; otherwise move the left boundary to mid + 1. Continue until both pointers meet, which identifies the first bad version in O(log n) time.
What is the best approach for First Bad Version?
Binary search is the optimal approach because versions form a monotonic sequence: all good versions come before bad ones. By repeatedly halving the search range, you find the first bad version in O(log n) time while using only O(1) space. This also minimizes expensive API calls to isBadVersion.
Is First Bad Version asked at Google/Amazon/Meta?
First Bad Version is a classic binary search interview question and has appeared in coding interviews at companies like Google and Amazon. It tests recognition of monotonic conditions and efficient search using minimal API calls.
What data structure is used in First Bad Version?
No special data structure is required. The solution relies on the binary search algorithm over an implicit sorted range of version numbers. The monotonic property (good versions followed by bad versions) enables efficient searching.
What is the time complexity of First Bad Version?
The optimal binary search solution runs in O(log n) time because the search range is halved on every step. A naive linear scan would take O(n) time since it may check every version sequentially. Space complexity is O(1) for the iterative solution.