How to solve the 2 crystal balls problem in JS
Tags: javascript, beginners, programming, tutorial
Published: 2024-03-13 21:53:05

The 2 crystal balls (or the 2 balls, or the 2 glass balls, or the 2 eggs, or the 2 fragile things) problem is a maths challenge that goes like this:

Given I have two crystal balls and a building with `n` number of floors, find out the maximum height from which a ball can be dropped without breaking.

In other words, find the first floor that a ball will smash if dropped from.

## Let's define our assumptions and constraints

1. The balls' integrity does not diminish when dropped
1. Don't break both balls before you've found out which floor will break them
1. The floors will be represented by a boolean array, where false represents a floor that won't smash our ball and true represents a floor that will smash our ball. E.g. `[false, false, false, false, true, true, true, true]`.

## Our plan

If we only had 1 ball, we would only have one option: we'd have to drop the ball from each floor until it smashed. Doing it any other way to improve our running time would mean the ball would smash before we could determine the exact floor that would smash it. Doing it in this way would be linear time, or `O(n)`.

Because we have 2 balls (cough), we can get a much better running time. Our plan is to use the first ball to walk the array in chunks and if our ball smashes, then we use our 2nd ball to walk the array from the start of the previous chunk to our known breakage point. The 'chunk' unit we'll use (I'll explain why at the end) is the `sqrt(n)` where `n` is the length of our array.

So, our plan is to walk the array with our first ball by `sqrt(n)`, and if our ball breaks, we go back by `sqrt(n)` and walk the array with our 2nd ball linearly until that one breaks.

Let's explain with some pseudo code...

## Some psuedo code

```
jumpAmount = square root of array length

i = jumpAmount

loop from i while i < array.length
	if array[i] = smash
		exit loop
	increment i by jumpAmount

decrement i by jumpAmount

loop from 0 to jumpAmount
	if (array[i]) = smash
		return i

return no smash

```

## Real Code

```typescript
// function takes in a boolean array and returns the
// index at which a ball will smash, or -1
function twoCrystalBalls(floors: boolean[]): number {

	// define our jump / chunk amount as the square root
	// of the array length
	const jumpAmount = Math.floor(Math.sqrt(floors.length));

	// loop through array starting with our jumpAmount
	// and increment by our jumpAmount
	let i = jumpAmount;
	for (; i < floors.length; i += jumpAmount) {

		// if we find a floor where the ball smashes
		// break out the loop
		if (floors[i]) break;
	}

	// decrement our iterator by our jumpAmount
	i -= jumpAmount;

	// walk the array linearly from i
	// a maximum of [jumpAmount] times
	for (let j = 0; j <= jumpAmount && i < floors.length; ++j, ++i) {
		if floors[i] {
			// if we find the floor that breaks our ball
			// return the index
			return i;
		}
	}

	// the ball didn't smash so return -1
	return -1;
}
```

## Time complexity

The biggest question I had with this algorithm was, 'why divide the array by its square root, why not divide in half, or by 10?'. WELL... it's because, if we divided by a fraction, for example 0.25, then our time complexity would be `O(1/2n)`, in which case, we drop our constants so our running time would be `O(n)` which takes us back to linear time. By dividing the array by its square root, our time complexity becomes `O(sqrt(n))`. Neat huh? 🤓