DEV Community: Nick Salvatore

Falsey values and -1 returns

Nick Salvatore — Mon, 04 Mar 2024 14:59:10 +0000

This has happened to me a lot, so I thought it was worth reflecting on. I came across a Leetcode problem this morning that asks you to create a method for an array that returns the last item in the array. If the array is empty, return -1.

It’s a beginner-level problem, but the gotcha comes in considering falsey values like null or undefined.

Intuition

The intuition in solving this problem is to simply get the index of the last item using .length-1. If the item exists, return the item. Otherwise, return -1.

This approach has one problem though which is that if the array contains falsey values like null or undefined, it will return -1.

Don’t return -1 explicitly

These Leetcode problems arise pretty regularly where you need to return something in an array, otherwise you return -1.

There’s a strong intuition, at least for me, to check for some case and then explicitly return -1 if that case isn’t met. You’ll fail your tests and then see that since the last item you were trying to access is null, -1 was returned instead of null. Then you’ll add a check for null or undefined, but you’ll find that empty arrays also return undefined.

A sign that you are approaching the problem incorrectly is acting on this intuition to return -1 explicitly.

Derive -1 naturally

If an array is empty, calculating the index with .length-1 will return -1. So to solve the problem eloquently, all you need to do is check for an empty array. If the array is empty, return the index, otherwise return the item.

The code would look something like this.

Array.prototype.last = function() {
    const i = this.length-1

    if (i < 0) {
        return i
    }

    return this[i]
}

The lesson

So again, if you don’t want to deal with the headache of failed Leetcode tests on simple af problems, which leave you feeling like more of an imposter than you already are (I'm projecting, you're probably great), make sure to consider falsey values and also be wary of explicit -1 returns.

Conceptualizing the two crystal ball problem

Nick Salvatore — Tue, 16 Jan 2024 05:09:11 +0000

The problem

You have two identical crystal balls and you are to determine the most efficient way to figure out the lowest floor in a given building where the crystal balls will break when dropped.

Setting up the problem

If all you had was one crystal ball, the only way to guarantee success in finding the answer would be with a linear search, or simply dropping the ball from each story, starting at the first, until you found the solution. Because we have 2 crystal balls though, we have more freedom to jump around. Suppose that the building in the problem has 120 floors. With a linear search, your worst case scenario would be 120 drops. If you moved in intervals of 2 floors though, your worst case scenario would be 61 steps. 60 steps forward, 1 step backward to see if the previous floor was the breaking point or if the floor at step 60 was the breaking point. If you moved in intervals of 3, your worst case scenario would be 42 steps. 40 steps forward, 1 step backward to the floor above the previous interval and 1 more step forward to complete scanning the entire interval.

To write this out mathematically, you could use use the following variables:

n = total number of floors
m = step interval

And the equation would look like this:

n / m + (m - 1) = total number of steps in the worst case

For the example using intervals of 3, the equation would be applied as:

120 / 3 + (3 - 1) => 40 + 2 => 42

So in order to figure out the optimal, or most efficient, interval size, we want to minimize the total number of drops and we can do this by finding the derivative of the function of n / m + (m - 1) which is the square root of n. Another way to find this solution without the use of calculus is to approximate m - 1 as m and set n / m = m. Solve for m, which is also the square root of n.

The solution

Given this minimization, the optimal way to find the lowest floor at which one of the crystal balls would break is by traversing the building in intervals of the square root of n.