Coding Interview Questions | First Bad Version

December 26th, 2023

First Bad Version Problem Introduction:

This summary will talk about my solution to the first bad version problem as seen on leetcode here.

First Bad Version Solution:

var solution = function (isBadVersion: (n: number) => boolean) {
  return function (n: number): number {
    if (n === 1) {
      return 1;
    }

    let minProductIsGoodIdx = n - 1;
    let maxProductIsBadIdx = 0;

    while (maxProductIsBadIdx <= minProductIsGoodIdx) {
      const midProductIdx = Math.floor(
        (maxProductIsBadIdx + minProductIsGoodIdx) / 2
      );
      const isMidProductBad = isBadVersion(midProductIdx + 1);

      if (isMidProductBad) {
        minProductIsGoodIdx = midProductIdx - 1;
      } else {
        maxProductIsBadIdx = midProductIdx + 1;
      }
    }

    // Array is 0-indexed but bad product starts at 1-index
    return maxProductIsBadIdx + 1;
  };
};

Flood Fill Solution Summary:

• Overview: The solution uses binary search to find the first bad version efficiently.
• Two pointers: Two pointers, minProductIsGoodIdx and maxProductIsBadIdx, are employed to narrow down the search space.
• Pointer Modification: Based on the API result, it adjusts the pointers to further narrow down the search until the first bad version is identified.
• Index Conversion: The final result is returned, considering the 1-indexed nature of the versions.
• Summary: Overall, the solution uses a binary search strategy for identifying the first bad version while minimizes API calls to a maximum of O(log n)