Background

The Two-Pointer Pattern

This is a method that is usually used to solve algorithm questions involving arrays where you usually need to find two or more elements of said array that satisfy some condition. This method is so named because two pointers are required, the head and the tail. At the start of the iteration through the array, the head points to the first element, while the tail points to the last element. These pointer variables could be named something else, but the names chosen improve readability.

Problem Statement

You're given an array of integers, height of length n. There are n vertical lines drawn so that two endpoints of the i^th line are (i, 0) and (i, height[i]).

Find two lines that together with the x-axis, form a container such that the container contains the most water.

Return the maximum amount of water a container can store.

Example

Input: height = [1, 8, 6, 2, 5, 4, 8, 3, 7]

Output: 49

Explanation: The above vertical lines are represented by the array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.

Distance between 8 and 7 (height[1] and height[8]) = difference in their respective index = 8 - 1 = 7.

Height = minimum height between 8 and 7 (the minimum is required because above this point the water starts to spill out) = 7.

∴ Area = 7 * 7 = 49.

The question and example above were referenced from this Leetcode problem.

Solution

First Thoughts

For this solution, my first thoughts are on how to maximize the distance between the heights (i.e. elements in the height array) and then gradually reduce this distance while determining the area generated by the two pointers and comparing it with a maximum area variable.

Approach

To approach this problem, a maximum area variable, maxArea is initialized with the smallest possible integer, as well as a head and tail variable for traversing the array.

function maxArea(height: number[]): number {
    let maxArea = Number.MIN_SAFE_INTEGER;
    let head = 0;
    let tail = height.length - 1;

    // ...
};

Then a while loop is initiated to traverse the array. The terminating condition for this loop is that the head doesn't exceed the tail. For each run of the loop, the following happens:

The effective height of the container is determined by taking the minimum of the two current heights i.e. height[head] and height[tail] . This is done because if the water exceeds this minimum height, it's going to start spilling over.

function maxArea(height: number[]): number {
    let maxArea = Number.MIN_SAFE_INTEGER;
    let head = 0;
    let tail = height.length - 1;

    while (head < tail) {
        const effectiveHeight = Math.min(height[head], height[tail]);    
    }
    // ...
};

The base of the container which can be thought of as the distance between the two heights is also calculated by subtracting the head index from the tail index.

function maxArea(height: number[]): number {
    let maxArea = Number.MIN_SAFE_INTEGER;
    let head = 0;
    let tail = height.length - 1;

    while (head < tail) {
        const effectiveHeight = Math.min(height[head], height[tail]); 
        const base = tail - head;   
    }
    // ...
};

The area of the container is calculated by simply multiplying the effective height of the container by the base.

function maxArea(height: number[]): number {
    let maxArea = Number.MIN_SAFE_INTEGER;
    let head = 0;
    let tail = height.length - 1;

    while (head < tail) {
        const effectiveHeight = Math.min(height[head], height[tail]); 
        const base = tail - head; 
        const area = effectiveHeight * base;  
    }
    // ...
};

The next thing to do is to get the higher area value between the current calculated area and the maxArea and set the maxArea to this value.

function maxArea(height: number[]): number {
    let maxArea = Number.MIN_SAFE_INTEGER;
    let head = 0;
    let tail = height.length - 1;

    while (head < tail) {
        const effectiveHeight = Math.min(height[head], height[tail]); 
        const base = tail - head; 
        const area = effectiveHeight * base;

        maxArea = Math.max(area, maxArea);  
    }
    // ...
};

Now comes the iterating logic, we want to check if height[head] is smaller than height[tail]. If it is, increase head by 1, and if not decrease tail by 1. This serves to always ensure that we're picking the largest heights possible for our calculations.

function maxArea(height: number[]): number {
    let maxArea = Number.MIN_SAFE_INTEGER;
    let head = 0;
    let tail = height.length - 1;

    while (head < tail) {
        const effectiveHeight = Math.min(height[head], height[tail]); 
        const base = tail - head; 
        const area = effectiveHeight * base;

        maxArea = Math.max(area, maxArea); 

        if (height[head] < height[tail]) head++;
        else tail--; 
    }
    // ...
};

The last thing to do to complete the function is to return the maxArea variable.

function maxArea(height: number[]): number {
    let maxArea = Number.MIN_SAFE_INTEGER;
    let head = 0;
    let tail = height.length - 1;

    while (head < tail) {
        const effectiveHeight = Math.min(height[head], height[tail]); 
        const base = tail - head; 
        const area = effectiveHeight * base;

        maxArea = Math.max(area, maxArea); 

        if (height[head] < height[tail]) head++;
        else tail--; 
    }

    return maxArea;
};

Complexity

Time Complexity - O(n)

Since the while loop continues until head and tail meet, the number of iterations required will be proportional to the length of the input array height. Therefore, the time complexity of this code is O(n), where n is the length of the input array.
Space Complexity - O(1)

The code uses a few variables to store intermediate values but doesn't require any additional space that grows with the size of the input. The space complexity of this code is O(1), which means it uses constant space.

Summary

I hope this article has introduced you to how to use the two-pointer pattern to solve algorithm problems as well as showing you how to use it to solve the "container with the most water" problem. Feel free to drop any questions or comments you have right here or you can message me on any social media listed below.

Thank you for your time and I hope to see you in the next article. 👌

Let's Connect!

Don't be shy and say hello to me whenever you can. I'm always happy to meet new people.

Mubaraq's Musings