DEV Community: Franziska Hinkelmann, Ph.D.

Leetcode: Container With Most Water

Franziska Hinkelmann, Ph.D. — Sun, 27 Feb 2022 22:24:00 +0000

I love solving Leetcode coding problems for fun. I came across this problem and was intrigued to prove why the sliding window algorithm is correct.

Given an array of heights, find two lines that together with the x-axis form a container, such that the container contains the most water.

Representation of [1,8,6,2,5,4,8,3,7]. For this input, the most water a container can contain is 49.

You can solve this brute force by comparing all possible combinations of left and right lines and keeping track of the most water. The complexity of this solution is quadratic.

function maxWaterQuadratic(height) {
    let left = 0; 
    let right = 1;
    let max = 0;

    while(right < height.length) {
        while(left < right) {
            let h = Math.min(height[right], height[left]);
            max = Math.max(max, h*(right - left));
            left++;
        }
        right++;
        left = 0;
    }

    return max;
};

Algorithms with quadratic complexity do not work well for very large datasets. For example, given an array with 100 entries as input to a quadratic algorithm takes on the order of 100^2 = 10,000 instructions. No problem for a modern computer. But as the array size increases, say to 300 million (population size of the US), now we need something on the order of 90,000,000,000,000,000 instructions. Given that we measure CPUs in GHz (billions of instructions), a quadratic algorithm would not work for this scale. In fact, if you submit this algorithm on Leetcode, you get a Time Limit Exceeded error for one of the test cases.

Linear vs quadratic complexity

Can we solves this problem with linear complexity? Is there an algorithm that looks at each array entry just once (or a constant multiple of once) instead of all combinations of pairs of entries?

In fact, yes, there's a solution that runs in linear time: Start with the widest container. That means use the first and last element as the left and right boundary. Move the shorter of the left and right boundary one step inwards. Keep track of the most water until the left and right boundaries overlap. This is a sliding window algorithm where one pointer starts at the front, the other at the back.

function maxWaterLinear(height) {
    let max = 0;
    let left = 0;
    let right = height.length-1;
    while(left < right) {
        let area = (right - left) * Math.min(height[left], height[right]);
        max = Math.max(area, max);
        height[left] < height[right]) ? left++ : right--;
    }

    return max;
};

Why is this algorithm correct though? It passes all the test cases on Leetcode - that doesn't prove correctness though. How do we know there isn't some edge case where this algorithm would give us the wrong solution?

Proof of Sliding Window Algorithm

Suppose the real solution of the problem is from index a to b with water height h. Then both a and b are greater or equal to h. Then for any index to the left or to the right of the optimal container, the height must be less than h. Otherwise we could extend the optimal container to that index without sacrificing height and have a larger water container.

In our sliding window algorithm, as we move our indexes from the outside in, we will eventually reach a or b. Suppose we reach a first. We just proved that everything outside of the other index b, must be smaller than h and thus smaller than a. Therefore, one pointer in our algorithm will keep moving until it reaches b while the other pointer stays on a. At which point the optimal volume is recorded. If we reach b first, the argument is exactly the same. Thus, this linear time algorithm will always find the optimal solution.

Happy algorithm coding!

How I learned to love the terminal

Franziska Hinkelmann, Ph.D. — Wed, 13 Nov 2019 21:19:16 +0000

An introduction to the command line.

Knowing your way around the commnand line has many benefits. With a bit of practice, you can accomplish many tasks much faster on the command line than using any other tool.

The command line is almost always available, unlike some GUI tools that must be installed. You can save frequently-used commands as aliases and save time. Your bash history will save your bacon at least once when you forget how to do something. When you ssh into a remote machine, such as your work station or a virtual machine in the cloud, you can use the command line instead of a slow GUI.

Here are some tips that'll make working on the command line much easier.

Shortcuts instead of typing full commands

Use the arrow up and arrow down keys to iterate over the last used commands.

Use tab completion to complete commands, directories and files, and even some parameters. Start typing one or two characters of a command. Then hit tab twice. If that gives you several options, type a few more letters and then hit tab again. You should never type out a full filename. Use tab aggressivly. It's muscle memory you need to build if you want to be fast on the command line.

If you remember part of a command, but not necessarily the beginning, you can search for that command using reverse-i-search. To use reverse-i-search, press Ctrl+R, then start typing the command. If there are commands that match what you've typed, you'll see a suggestion. You can keep typing to further refine your search results or press Ctrl+R again to cycle through the commands that match your search query in reverse order.

Navigate around

Use cd .. to navigate up one directory. Use cd to jump to your home directory. This is the same as cd ~/. Use cd / to jump to the root directory and cd - to go back to the last directory.

Jump to the beginning and end of the line with Ctrl A and Ctrl E. You can move word by word with option arrow left and option arrow right.

When you realize that you're typing the wrong command, use Ctrl C to start over. This is faster than deleting the command character by character.

Hidden config files

To see hidden files, i.e., filenames that start with a dot, use ls -la. Check out the hidden .gitconfig in your home directory. Or edit the .gitignore file in a git project to exclude files from source control. You can configure a lot of tools via a dot file. Many follow the convention of the config file name ending in rc ("run command"), like .npmrc for npm config settings.

Configure your terminal

The config file .bash_profile determines how your terminal, more specifically bash, behaves¹. The .bash_profile file is in your home directory (~/) . In this file you can do things like

specify shortcuts with alias
configure your prompt
set environment variables.

Git on the command line

If you use git on the command line, there are a few tricks to make your life easier. You can enable tab completion for git and configure custom shortcuts like git co for git checkout. For me, the most important feature is to always see what branch I'm on.

My bash shows the current directory and the branch I'm on if I'm in a git directory. I configure this behavior in my .bash_profile with the following lines:

# The next line enables git autocompletion
. ~/.git-completion.bash

# The next lines configures a fancy prompt
. ~/.git-prompt.sh
export GIT_PS1_SHOWDIRTYSTATE=1
export PS1='\[\e[35m\]\w$(__git_ps1 " (%s)")\$\[\e[0m\] '

Download the scripts from the git source code mirror and follow the instructions: .git-prompt.sh and .git-completion.bash. You can customize the color of the prompt. I use different colors on different machines to easily see what machine I'm ssh'ed into.

Most importantly

Be adventurous. Don't let the terminal intimidate you! Once you know some basics, it's easy to work efficiently with the command line. Search StackOverflow for tips to make things even easier. Read through other people's config files (mine are here). Go explore and try a few things. Lots of tips are really helpful, you just need to find those that work for you.

¹ .bash_profile is the default config for bash on MacOS. On Linux, use .bashrc.

Many thanks to Amy Unruh, Sofia Leon, ErinMcKean, Sandra Friesen, and Sarah Clark for their thoughtful reviews and comments.