First Bad Version

The problem description can be found in LeetCode.

Approach

The problem looks very easy. It would be enough to iterate over the list and simply find the first bad version. which means that you have to return the index of the first element that is True. This simple solution would require $O(n)$ time and $O(1)$ space.

Sometimes it is very useful to draw pictures or write examples of the inputs to graphically represent the problem. This is a classic example where this could help a lot.

Let's write some examples:

versions1 = [False, True, True, True]
versions2 = [True, True, True, True]
versions3 = [False, False, False]

Which could be written as:

versions1 = [0, 1, 1, 1]
versions2 = [1, 1, 1, 1]
versions3 = [0, 0, 0]

Where False values are 0s and True values are 1s.

What do we notice?

Well, the input is already sorted. As usual, having a sorted list always means that Binary Search might be used.

In this particular case, we can apply Binary Search to find the leftmost True value, as we explained in the Binary Search ~ Additional Usage section.

Solution

class Solution:
    def firstBadVersion(self, n: int) -> int:
        left, right = 1, n
        ans = -1

        while left <= right:
            mid = (left + right) // 2
            if isBadVersion(mid):
                ans = mid
                right = mid - 1
            else:
                left = mid + 1

        assert ans != -1, "expected one solution"

        return ans

Complexity

• Time: $O(log(n))$
• Space: $O(1)$

Where $n$ is the number of versions, which the unique parameter of our function.