Leetcode diary: 1884. Egg Drop With 2 Eggs and N Floors
Tags: javascript, algorithms, devjournal, motivation
Published: 2022-01-11 07:05:11

This is a new series where I document my struggles of leetcode questions hoping seeing however small of an audience I get gives me the motivation to continue.  

[link](https://leetcode.com/problems/egg-drop-with-2-eggs-and-n-floors)

This problem was ...interesting. The author literally wrote out how to solve this problem for us lol ...
so the thought process is as:

1.) we need to find out what's the nearest sum from 1 to i such that their sum is smaller than n and sum += i+1 would be greater than n. We return the index. At this point it is O(N^2) performance (before the memoization).
```
let memo = [0];
function sumToN(n) {
    let currentLargest = memo[memo.length-1];
    if (currentLargest > n) {
        return findInMemo(n);
    }
    
    for (let i=memo.length; i<n; i++) {
        if(currentLargest + i > n) {
            break;
        }
        currentLargest += i;
        memo.push(currentLargest);
    }; 
    
    return memo.length-1;
}
```

2.) Once we have that index, we only need to check whether memo[index] === n, if so return index, otherwise return index+1. 

the +1 case is the first step in the example description that subtracts n by some number so that the rest can proceed as index, index-1, index-2 ... 

```
var twoEggDropa = function(n) {
    if(n==1) return 1;
    
    const nearestNindex = sumToN(n);
    return n === memo[nearestNindex] ? nearestNindex : 1 + nearestNindex;
};
```
 

3.) We memoize the result on each iteration. Should the next n be smaller than the largest value in memo[], then we use binary search to find the smallest index that memo[index] is less than n.

This part was tricky as I failed the submission numerous times only to realize that start, mid, end all could be the that last index we are looking for. There is also one additional case where memo[start] is still greater than n, so we have to return start-1 instead.

```
function binarySearchNearest(arr, val) {
  let start = 0;
  let end = arr.length - 1;

  while (start <= end) {
    let mid = Math.floor((start + end) / 2);
    
    if (arr[mid] === val || mid === start || mid ===end) {
        if(arr[mid] === val) return mid
        else if(arr[end] < val) return end
        else if (arr[start] < val) return start
        else { return start-1 }
    }

    if (val < arr[mid]) {
      end = mid - 1;
    } else {
      start = mid + 1;
    }
  }
    
  return -1; //should be unnecessary;
}
```

I have to admit I found this binary search code online. It is by far the cleanest version; you'd think something so few lines won't change too much. The key memory points are these:
1.) while loop with start <= end //same as most
2.) end = Math.floor((start+end)/2); //same as most
3.) condition to stop //same as most
4.) comparison to val: end = mid -1 or start = mid + 1

For some reason other variations I remember have either only mid -1 or mid +1, this one has both so it's easier to remember; the easy to read syntax was nice touch too. I don't know if there is anything special about the +-1, lemme know if you do!

Let me know anything on your mind after reading through this, THANKS!