Leetcode 278 Solution

This article provides solution to leetcode question 278 (first-bad-version)
Categories:
Tags:
Access this page by simply typing in "lcs 278" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/first-bad-version

Thinking Process

Very basic binary search problem. Using our binary search framework. isBadVersion is just our condition function. Put it in the binary_search_template, we get the final result.

Time & Space Complexity

Assuming N is the size of the array:

  • Time complexity: O(lg N)
  • Space complexity: O(1)

Solution

# The isBadVersion API is already defined for you.
# def isBadVersion(version: int) -> bool:

class Solution:
    def firstBadVersion(self, n: int) -> int:
        l = 1
        r = n

        while l < r:
            m = (l + r) // 2

            if isBadVersion(m):
                r = m
            else:
                l = m + 1
        return l