Grind 75 Question 15: First Bad Version
Don’t be fooled by the cute name of this problem.
The Problem
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 returns whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.
The First Attempts
Okay, reading over this question, it isn’t too bad. I think it will involve a binary search (read 0(log n)), which I’ve never implemented, because I messed up the binary search question (heh). So. Today is as good a day as any to learn it!
Here is my “first bad version” of the code:
/**
* Definition for isBadVersion()
*
* @param {integer} version number
* @return {boolean} whether the version is bad
* isBadVersion = function(version) {
* ...
* };
*/
/**
* @param {function} isBadVersion()
* @return {function}
*/
var solution = function(isBadVersion) {
/**
* @param {integer} n Total versions
* @return {integer} The first bad version
*/
return function(n) {
let pointer = (Math.ceil(n.length/2)) - 1
let badVersion = -1;
while(badVersion < 0;){
if(isBadVersion(n[pointer]) && !isBadVersion(n[pointer - 1]){
badVersion = n[pointer];
}
else if(!isBadVersion(n[pointer]) {
pointer += (Math.ceil(n.length - pointer)/2)
};
else pointer -= (Math.ceil(n.length - pointer)/2)
}
};After fixing all my myriad curly brace and parentheses errors, I submit it for test-judging and it times out. Boo.
I trust my code enough to try debugging it before I go straight to Neet. The first issue I discover is that pointer is NaN. So. There’s the reason for the timeout.
After fixing the pointer issue (n is not, in fact, an array — just a number of versions!) and then making it so that pointer is never a decimal (see if you can spot what I did wrong with Math.ceil), and then adding some missing return statements that were causing badNumber to return undefined, the thing runs!
But. It exceeds the time limit. So I’m thinking I can use a hashmap to avoid all the calls? Or just visit Neetcode to actually see how a binary search is implemented…
The Solution
Neetcode doesn’t actually have a video on this specific problem, but I did review his Binary Search video, and it turns out this is also a two-pointer problem. I was darn close — the solution I find in the Leetcode forums is quite similar to mine, but with two pointers instead of fancy calculations. And no hashmap. Heh.
/**
* Definition for isBadVersion()
*
* @param {integer} version number
* @return {boolean} whether the version is bad
* isBadVersion = function(version) {
* ...
* };
*/
/**
* @param {function} isBadVersion()
* @return {function}
*/
var solution = function(isBadVersion) {
/**
* @param {integer} n Total versions
* @return {integer} The first bad version
*/
return function(n) {
let pointerOne = 0;
let pointerTwo = n;
while(pointerOne <= pointerTwo){
let midpoint = Math.floor((pointerOne+pointerTwo)/2)
if(isBadVersion(midpoint) !== isBadVersion(midpoint + 1)){
return midpoint+1;
}
else if(isBadVersion(midpoint) === false) {
pointerOne = midpoint + 1
}
else pointerTwo = midpoint - 1
};
};
};So. Here’s what we’re doing. We’re putting pointerOne as zero and pointerTwo as the final number of versions we’re looking at (n). While pointerOne and pointerTwo haven’t collided:
- We declare the midpoint as halfway between pointerOne and pointerTwo (fancily, don’t worry about that).
- If the midpoint isn’t a bad version and midpoint + 1 is (the only way they could be equal, since there won’t be a good version after a bad one), return midpoint + 1 as the bad version.
- If that’s not the case and midpoint is a good version, pointerOne gets shifted over to the midpoint + 1 (since we’ve already looked at midpoint and know it’s good). Then we perform the same operation.
- If midpoint is a bad version, we do the same as previously stated, except that pointerTwo gets shifted to midpoint -1, again, since we’ve already looked at midpoint and know it’s bad.
- Rinse, repeat until done.
What I Learned
- How to implement a binary search! H’ray! (To be read in a Bluey/Bingo voice)
mins
read
