Learn and practice the Two Pointers, and Modified Binary Search patterns to solve coding interview problems.

Speedrun the Google Coding Interview: Top Problems in Java

This module groups together two of the most common patterns that may be used to solve problems where the input data is linear: Two Pointers and Modified Binary Search. Both the Two Pointers and the Modified Binary Search patterns derive their power from their ability to efficiently reduce the size of the search space, that is, both exemplify the divide and conquer approach to problem-solving. After completing this module, we will have the knowledge of how to use this set of related patterns to solve a diverse range of problems.

Two Pointers & Co.

#
## Statement

You're given an integer array `height` of length $n$, and there are $n$ vertical lines drawn such that the two endpoints of the $i^{th}$ line are $(i, 0)$ and ($i$, `height[i]`).

Find two lines from the input array that, together with the x-axis, form a container that holds as much water as possible. Return the maximum amount of water a container can store.

> **Note:** You may not slant the container.

**Constraints:**

- $n =$ `height.length`

- $2 \leq$ $n$ $\leq 10^3$

- $0 \leq$ `height[i]` $\leq 10^3$

## Solution
So far, you’ve probably brainstormed some approaches and have an idea of how to solve this problem. Let’s explore some of these approaches and figure out which to follow based on considerations such as time complexity and implementation constraints.

### Naive approach
A naive approach to solve this problem would be to find the area of every possible pair of vertical lines and select the maximum area out of them.

The time complexity for this approach would be $O(n^2)$, where $n$ is the length of the input array. The space complexity would be $O(1)$, since only a constant amount of extra space is used.

### Optimized approach using two pointers

An optimized approach to solve this problem is using two pointers, `start` and `end`, initialized at the beginning and end of the array, respectively. We also create a variable to store the maximum area and set it to zero.

While iterating through the array, `height`, the algorithm proceeds through the following steps:

- Calculate the distance, `width`, between the two vertical lines pointed by `start` and `end` pointer as `width` $=$ `end` $-$ `start`.
- The height of the container is determined by the shorter of the two vertical lines pointed by the `start` and `end` pointers. Then, multiply this height by the `width` to calculate the area of the container.
- If the calculated area is greater than the current value of the maximum area, update the maximum area.
- Move the pointer pointing to the shorter vertical line inward by one step. This is because if we try to move the pointer at the longer vertical line, we won't gain any increase in area, since the shorter line limits it.
- Keep iterating through the array until the pointers meet.

After iterating through the array, return the maximum area.

Now, let’s look at the following illustration to get a better understanding of the solution:



Let's solve the Container with Most Water problem using the Two Pointers pattern.


Solution: Container with Most Water

Let's solve the Container with Most Water problem using the Two Pointers pattern.

Two Pointers

Modified Binary Search

Conclusion

Solution: Container With the Most Water

Statement

Solution

Naive approach

Optimized approach using two pointers