Problem 42 - First Bad Version

Explore our archive for previous posts.

Problem 41 - Add Binary

Problem 40 - Remove Element

Problem 39 - Intersection of Two Arrays

Question

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

Approach

This problem is a classic example of a binary search algorithm. The task is to find the first occurrence of a "bad version" in a given range of versions. Here's a high-level approach:

1. Initialize: Set start to 1 and end to the total number of versions.

2. Binary Search: Check the middle version. If it is bad, set end to the middle; otherwise, set start to the middle + 1.

3. Repeat: Continue the process until start and end converge.

Solution

Solve it here

public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        // Initialize start and end pointers
        int start = 1, end = n;
        
        // Binary search
        while (start < end) {
            int mid = start + (end - start) / 2;
            
            // Check if mid is a bad version
            if (isBadVersion(mid)) {
                // Move end to mid to search in the left half
                end = mid;
            } else {
                // Move start to mid + 1 to search in the right half
                start = mid + 1;
            }
        }
        
        // Start and end converge to the first bad version
        return start;
    }
}

Time and space complexity

Time Complexity: The time complexity of this algorithm is O(log n) because the search space is halved in each iteration.

Space Complexity: The space complexity is O(1) as we only use a constant amount of extra space for variables (start, end, mid). The algorithm is performed in-place and does not require additional data structures.

Explore more?

Missed a previous edition? Catch up on the insightful content you might have missed by visiting our archive here. Thank you for being a valued reader of our newsletter. We appreciate your continued support!

Nailing Coding Interviews: Mindset Matters

Ethical Dilemmas in Coding Interviews: Should You Reveal Prior Knowledge?