Problem Statement:

You are given an array of non-negative integers representing the height of walls. The width of each wall is 1. Imagine that these walls are containers of water, and you task is to find two walls that can hold the most water. Determine the maximum area that can be formed between two walls by using them as the sides of a container.

Examples:

Example 1:

Input: heights = {1, 8, 6, 2, 5, 4, 8, 3, 7}
Output: 49

Explanation: The container formed by the walls at indices 1 and 8 can hold the most water. The height of the container is min(8, 7) = 7, and the width is 8-1 = 7. Therefore, the maximum area is 7 * 7 = 49.

The above vertical lines are represented by 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.

Problem Understanding:

To approach this problem, let's break down the key aspects:

Container Formation:

• The container is formed by two vertical lines and the x-axis.
• The width of the container is the difference in indices of the two lines.

Area Calculation:

• The area of the container is calculated as the product of the width and the minimum height of the two lines.

Maximizing Water Trapped:

• The goal is to find two lines that maximize the area, i.e., maximize the water trapped.

Different Approaches

1️⃣ Brute Force Approach

The brute force considers all possible pairs of lines and calculates the area for each pair. It iterates through every combination of lines using two nested loops. The maximum are among all pairs is stored and returned.

#include <vector>

int maxAreaBruteForce(std::vector<int>& height) {
    int n = height.size();
    int maxArea = 0;

    for (int i = 0; i < n - 1; ++i) {
        for (int j = i + 1; j < n; ++j) {
            int h = std::min(height[i], height[j]);
            int w = j - i;
            maxArea = std::max(maxArea, h * w);
        }
    }

    return maxArea;
}

Complexity Analysis:

• Time Complexity: O(n^2)
  The algorithm explores all pairs, resulting in a quadratic time complexity.
• Space Complexity: O(1)
  The algorithm uses only a constant amount of additional space.

2️⃣ Two Pointers Approach

The two-pointer approach starts with two pointers, one at the beginning and one at the end of the array. It calculates the area formed by these two lines and then moves the pointers towards each other. At each step, it chooses the line with greater height to potentially increase the area.

#include <vector>
#include <algorithm>

int maxAreaTwoPointers(std::vector<int>& height) {
    int maxArea = 0;
    int left = 0, right = height.size() - 1;

    while (left < right) {
        int h = std::min(height[left], height[right]);
        int w = right - left;
        maxArea = std::max(maxArea, h * w);

        if (height[left] < height[right]) {
            ++left;
        } else {
            --right;
        }
    }

    return maxArea;
}

Complexity Analysis:

• Time Complexity: O(n)
  • Both pointers traverse the array once, resulting in a linear time complexity.
• Space Complexity: O(1)
  • The algorithm uses only a constant amount of additional space.