Noob v. Algorithms # 20, iterating from the outside in
If you’re a noob like me you may dread the ‘medium’ level algorithms on LeetCode. As it turns out, a few of them are actually easier than the so-called Easy ones. Here’s a gentle introduction to the medium level.
Today’s challenge from Leetcode is to choose the container that holds the most water:
Let’s talk about volume
The volume of water will be
height x length x depth. In our case, depth is the thickness of the container from back to front — we are assuming it does not change. So for this challenge, we are only concerned with
height x length.
Height: As you can see, the heights vary. In the picture above, we have a container that is 8 units high on one side and 7 high on the other. When we’re making our calculation we have to choose lower one of these heights since the container’s volume is limited by its lowest wall.
Width: In the picture above we can see 9 walls. The width of our container is the x-coordinate of the right wall minus the x-coordinate of the left. Since our input data is in the form of an array, we’ll use index numbers instead of x-coordinates to make that calculation.
From the outside in
Us noobs have a habit of iterating from left to right:
(for let i = 0; i < array.length; i++)
or, when we’re feeling daring, from right to left:
(for let j= array.length = 1; j >= 0 ; j--)
In this case, we need to do both.
We’re going to start with the outside walls, pick the one that’s lower in height, and multiply by the width (the index of the right wall minus the left wall). We’ll call the result area.
Meanwhile, we’re going to set a variable called max, with a default value of 0. Each time we calculate area, we’ll compare it to max, and set max equal to the higher of the two values.
So far, our code looks like this:
Let’s unpack that:
On line 3, we’re setting
i equal to the index of the left wall, starting with
On line 4, we’re setting j equal to the index of the right wall, starting with the last element of the input array
height.length — 1.
On lines 5 and 6, we’re declaring variables for max and area. (Why don’t we set area equal to zero? We could, but we don’t need to. We’re going to calculate area — as you can see on line 9. But we never calculate max — we just set it equal to the higher of two variables, so we need to give it an initial value of 0. )
On line 8, we’re saying we want to iterate while our left wall,
i is still on the left side (i.e. less than) our right wall,
Test Drive — the first loop
Let’s say we have an initial input,
height = [1,8,6,2,5,4,8,3,7]
In our first loop,
i = 0,
j = 8(remember, these are indexes, not values).
The wall at
height[i] is 1 unit high. The wall at
height[j] is 7.
The width is
j — i => 8 — 0 = 8.
height of lower wall * width => 1 x 8 = 8.
We compare that to our
max, which has an initial value of
area is greater than
max, we set
max equal to
Now we’re done with our first loop.
Which way do we iterate for our second loop?
In our first loop, our left wall was lower than our right wall. Now we want to compare the next combination of two walls. The next combination should include the higher of the two walls we already have, plus the wall next to the shorter wall.
Since our right wall is higher, let’s ‘keep’ it (i.e. let’s not change the value of
j, the index of our right wall). Instead, let’s increment
i by 1, which means our new left wall is at index 1.
In our first loop, we compared walls at indexes 0 and Now, in our next loop, we’ll be comparing the walls at indexes 1and 8 (the red walls below).
Here’s what that looks like in code.
Then we keep looping until
j in the middle.
All together now:
And … it runs pretty fast:
You can see the code execute live here on PythonTutor.com and you can play with it here on repl.it:
Copyright © Joan Indiana Lyness 2019