Solving a Leetcode problem daily — Day 9 | First Bad Version

Solving a Leetcode problem daily — Day 9 | First Bad Version | by Subhradeep Saha | May, 2024 | Medium

Subhradeep Saha ・ May 9, 2024 ・

Medium

---

Here is the Leetcode problem link — First Bad Version

---

Problem Statement

Imagine you’re a product manager leading a software development team. During quality checks, you discover a bad version in your product. Since each version builds upon the previous one, any versions released after the bad one will also be faulty.

The challenge is to identify the first bad version as efficiently as possible. You’re given an array representing versions ([1, 2, ..., n]) and an API function isBadVersion(version) that returns true if the version is bad and false otherwise. The goal is to write a function that finds the index of the first bad version using the minimum number of API calls.

Example 1:

• Input: n = 5, bad version at index 4

• Output: 4

Explanation:

• isBadVersion(3) returns false (version 3 is good).

• isBadVersion(5) returns true (version 5 is bad).

• Since version 4 is right before the first bad version (version 5), the answer is 4.

Example 2:

• Input: n = 1, bad version at index 0 (only one version)

• Output: 1

Explanation: The single version is bad, so the answer is 1.

Constraints:

• 1 <= bad <= n <= 2^31 - 1 (n is within the range of a 32-bit integer)

High-Level Approach

The direct method entails iterating from version 1 to n-1. If a version is good and the subsequent version is bad, we designate the next version as the solution. However, this could lead to calling isBadVersion() 2* (n-1)times(2 calls for each version from 2 to n-1and 1 call each for versions 1, n) at worst, potentially becoming inefficient for large n.

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

class Solution {
public:
  int firstBadVersion(int n) {
    for(int x=1; x<=n-1; x++) {
        if(!isBadVersion(x) && isBadVersion(x+1)) {
            return x+1;
        }
     }
    return n;
  }
};

Reduce calls by using some space?

In the direct approach discussed above, it can be clearly seen that for every number from 2 to n-1, the call is made twice:

x = 1

x = 2

As seen above, there are redundant calls to isBadVersion(2). Perhaps we can optimize this by storing the calculated value during the initial run and then utilize the stored value for subsequent calls. This approach reduces the number of calls to just one for each number from 1 to n. However, the total no of calls still remains relatively high if n is very large.

Hint for Binary Search?

Since versions are ordered (1, 2, 3, …), bad versions will always cluster after the first bad version. Binary search allows us to exploit this ordering by repeatedly dividing the search space in half. We strategically pick a ‘middle’ version and use isBadVersion() for it and its next number. Based on the result, we can efficiently narrow down the search space to locate the first bad version.

Since with every iteration, we are dividing the search space by half, the number of calls to isBadVersion() drastically reduces to a complexity of O(log(n)) from the earlier complexity of O(n) .

Binary search is definitely a strategy to consider when dealing with sorted data. However, it’s worth noting that while binary search is effective for many such cases, it may not always be a perfect solution. Nevertheless, it remains a valuable option whenever we detect data sorted in some order.

Code Implementation(in C++)

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

class Solution {
public:
  int firstBadVersion(int n) {
    int l = 1, h = n;
    while (l < h) {
      int m = l + (h - l) / 2;
      if (!isBadVersion(m) && isBadVersion(m + 1)) {
        return m + 1;
      }
      if (isBadVersion(m)) {
        h = m;
      } else {
        l = m;
      }
    }
    return l;
  }
};

Breakdown of the Code

Binary Search Initialization:

• l (lower bound) is set to 1 (represents the first version).

• h (upper bound) is set to n (represents the last version).

• m (middle index) will be calculated during the search loop.

Binary Search Loop:

• The while loop continues as long as l is less than h. This ensures the search space keeps narrowing down.

Inside the loop:

• m is calculated as the middle index between l and h.

• The key logic relies on two isBadVersion calls:

• The first check is !isBadVersion(m) && isBadVersion(m + 1). This condition is true only if the middle version (m) is good (not bad) and the next version (m + 1) is bad. In this case, we've found the first bad version at index m + 1, and the loop terminates, returning this value.

Binary Search Refinement:

• If the condition !isBadVersion(m) && isBadVersion(m + 1) isn't met, we need to refine the search space further.

• If isBadVersion(m) is true (meaning m is bad), it signifies the first bad version could be within the lower half of the search space including m. We update h to m (excluding the upper half).

• Conversely, if isBadVersion(m) is false (meaning m is good), the first bad version must lie in the upper half. We update l to m(excluding the lower half)

why updating l to m and not m+1? since in the while loop we check for the middle number to be good - that’s why we need to keep atleast 1 good version for the next iteration.

Returning the Result:

When the loop terminates (either by finding the first bad version or reaching the boundaries), the value of l is returned. Since the loop stops when l ≥ h, l will always point to the first bad version after the loop completes.

If the input nis 1, it means there’s only one version under consideration, which is then designated as the bad version. The code accommodates this scenario as well.

Further improvements in the code

• One clear point of improvement is we can store the value of isBadVersion(m) in a boolean variable and reused instead of making one more call during the same iteration.

• Another area for improvement involves storing the values of isBadVersion(m) and isBadVersion(m+1). This strategy helps us to reuse the previously checked version outputs, leading to a reduction in overall calls to the isBadVersion(version) function. However, it’s worth noting that Leetcode seems to be imposing space restrictions for larger values of n in this problem.

Dry Run with a Test Case

Let’s perform a dry run on the code using the example n = 5 and the first bad version as 3:

Initialization:

• l is set to 1.

• h is set to 5.

• m is not yet calculated.

Iteration 1:

• m is calculated as 3.

• isBadVersion(m) (checking version 3) returns true.

• isBadVersion(m+1) (checking version 4) returns true .

• Since m is bad, we update h = m .

Iteration 2:

• l = 1, h = 3

• m is calculated to be 2

• isBadVersion(m) (checking version 2) returns false.

• isBadVersion(m+1) (checking version 3) returns true thereby returning m+1 = 3 as the first bad version

Time and Space Complexity Analysis

• Time Complexity: O(log n). The binary search approach significantly reduces the number of API calls needed to locate the first bad version. With each iteration, the search space is halved, leading to a logarithmic time complexity in terms of n.

• Space Complexity: O(1). The code utilizes a constant amount of extra space for variables like l, h, and m, regardless of the input size n. This makes the solution memory-efficient.

Conclusion

This blog post explored how Binary search can be used to solve Leetcode’s First Bad Version problem. We delved into the details of the problem statement and found out how Binary search can be thought of as an option whenever the problem contains some data ordered in a predictable way. Time complexity get reduced to a much smaller logarithmic scale thereby improving the solution’s efficiency by a whole margin.

References

• Cover photo by Agence Olloweb on Unsplash

• Diagrams in the Dry run section are created using Canva

---

If you liked this post, do applaude by clicking on the clap hands icon and follow me https://medium.com/@subhradeep_saha for such posts.

If you want to follow on with binary search problems, do consider reading this post https://blog.devgenius.io/solving-a-leetcode-problem-daily-day-8-sqrt-x-5e2521ef6fbe where I explained how binary search can be used to efficiently find the square root of a number — there is 1 Math hack as well described in the post about square roots so dont forget to checkout and applaude that post. Thanks!!