loading...

LeetCode: First Bad Version

aroup profile image Aroup Goldar Dhruba Updated on ・2 min read

LeetCode May Challenge (19 Part Series)

1) LeetCode: First Bad Version 2) LeetCode: Jewels and Stones 3 ... 17 3) LeetCode: Ransom Note 4) LeetCode: Number Complement 5) LeetCode: First Unique Character in a String 6) LeetCode: Majority Element 7) LeetCode: Cousins in Binary Tree 8) LeetCode: Check If It Is a Straight Line 9) LeetCode: Valid Perfect Square 10) LeetCode: Find the Town Judge 11) LeetCode: Flood Fill 12) LeetCode: Single Element in a Sorted Array 13) LeetCode: Remove K Digits 14) LeetCode: Implement Trie (Prefix Tree) 15) LeetCode: Maximum Sum Circular Subarray 16) LeetCode: Odd Even Linked List 17) LeetCode: Find All Anagrams in a String 18) LeetCode: Permutation in String 19) LeetCode: Online Stock Span

Problem Statement

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 will return whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.

Example

Given n = 5, and version = 4 is the first bad version.

call isBadVersion(3) -> false
call isBadVersion(5) -> true
call isBadVersion(4) -> true

Then 4 is the first bad version. 

Solution thought process

If you have to find the first occurrence of an element in a sorted array of some kind, binary search should be the first thing we should be thinking of.

Let's think of the first scenario:

Scenario #1: isBadVersion(mid) => false

 1 2 3 4 5 6 7 8 9
 G G G G G G B B B       G = Good, B = Bad
 |       |       |
left    mid    right

If we can see that the isBadVersion is returning false for mid, we can adjust our left to be equal to mid+1, because we know that we don't have to consider previous [left, mid] region for the answer, as we can see it from the scenario #1.

Scenario #2: isBadVersion(mid) => true

 1 2 3 4 5 6 7 8 9
 G G G B B B B B B       G = Good, B = Bad
 |       |       |
left    mid    right

If we can see that isBadVersion is returning true for mid, we can adjust our right to be mid-1 and our result = mid because we have to find the first occurrence of the bad product.

Solution

// The API isBadVersion is defined for you.
// bool isBadVersion(int version);

class Solution {
private:
    int binarySearch(int t)
    {
        int L = 1, U = t, result = -1;
        while(L<=U)
        {
            int M = L + (U-L)/2;
            bool badVersionResult = isBadVersion(M);
            if(badVersionResult == true)
            {
                result = M;
                U = M-1;
            }
            else {
                L = M+1;
            }
        }
        return result;
    }
public:
    int firstBadVersion(int n) {
        return binarySearch(n);
    }
};

Complexity

Time complexity: O(logn), on every loop we are making the candidate space into half, giving it a logarithmic complexity.

Space Complexity: O(1), we are not assigning any additional array.

LeetCode May Challenge (19 Part Series)

1) LeetCode: First Bad Version 2) LeetCode: Jewels and Stones 3 ... 17 3) LeetCode: Ransom Note 4) LeetCode: Number Complement 5) LeetCode: First Unique Character in a String 6) LeetCode: Majority Element 7) LeetCode: Cousins in Binary Tree 8) LeetCode: Check If It Is a Straight Line 9) LeetCode: Valid Perfect Square 10) LeetCode: Find the Town Judge 11) LeetCode: Flood Fill 12) LeetCode: Single Element in a Sorted Array 13) LeetCode: Remove K Digits 14) LeetCode: Implement Trie (Prefix Tree) 15) LeetCode: Maximum Sum Circular Subarray 16) LeetCode: Odd Even Linked List 17) LeetCode: Find All Anagrams in a String 18) LeetCode: Permutation in String 19) LeetCode: Online Stock Span

Posted on by:

aroup profile

Aroup Goldar Dhruba

@aroup

❄️❄️❄️❄️❄️

Discussion

markdown guide