Q3. In a test Kartik gave students an array of n non-negative integers a1, a2, …, an ,where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). The task is to find two lines, which together with x-axis forms a container, such that the container contains the most water.

Write a program to find the maximum water the container contains.

Question Link - Click Here to Solve This Problem

Intuition Behind the Algorithm

The "Container with Most Water" problem is an excellent example of a two-pointer approach in algorithm design. The core idea is to maximize the area of water a container can hold, formed by vertical lines and the x-axis. The intuition is to start with the widest possible container and then move the pointers inward, ensuring that at each step, the potential for a larger area is not missed. The algorithm exploits the fact that the area is limited by the shorter line, and hence, moves the pointer at the shorter line inward, aiming to find a taller line that could help in maximizing the area.

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n; // Reading the number of vertical lines

    // Dynamically allocating array to store the heights of the lines
    int *height = new int[n];

    // Reading the heights of each line
    for (int i = 0; i < n; i++) {
        cin >> height[i];
    }

    int left = 0;           // Left pointer starting from the beginning of the array
    int right = n - 1;      // Right pointer starting from the end of the array
    int area = 0;           // Variable to store the maximum area

    // Loop to find the maximum area
    while (left < right) {
        // Calculating the area for the current pair of lines
        // and updating the maximum area found so far
        area = max(area, min(height[left], height[right]) * (right - left));

        // Moving the pointer of the shorter line towards the center
        if (height[left] < height[right]) {
            left++;
        } else {
            right--;
        }
    }

    cout << area << endl; // Printing the maximum area

    delete[] height; // Freeing the dynamically allocated memory
    return 0;
}

Code Walkthrough

• Initialization: The program begins by reading the number of lines n and then the heights of these lines into an array height.

• Setting Two Pointers: Two pointers, left and right, are initialized at the start and end of the array, representing the current container's width.

• Iterating Through Lines: The algorithm enters a loop where it calculates the area formed between the lines at the left and right pointers and updates the maximum area found so far.

• Area Calculation: min(height[left], height[right]) * (right - left) calculates the current area. It uses the shorter of the two lines to ensure the container's boundaries are correctly represented.

• Pointer Movement: Depending on which line is shorter, the corresponding pointer (left or right) is moved inward to explore potentially larger areas.

• Exit Condition: The loop continues until the left and right pointers meet, indicating that all possible containers have been considered.

Time and Space Complexity Analysis

• Time Complexity: The algorithm runs in O(n) time. This efficiency is due to the linear traversal of the array with the two pointers, ensuring that each element is considered exactly once.
• Space Complexity: The space complexity is O(1) since the algorithm doesn't use any auxiliary space apart from the input.

Key Points of the Algorithm

• Two-Pointer Technique: Efficiently explores the solution space by starting with the maximum width and then narrowing down.
• Greedy Choice: By always moving the shorter line, the algorithm makes a greedy choice that ensures no potential larger area is missed.
• Linear Time Complexity: Achieved by avoiding nested loops and exploring the entire array with just a single pass.

Conclusion

The provided solution is an efficient approach to solving the "Container with Most Water" problem. It elegantly combines the two-pointer technique with a greedy strategy to achieve linear time complexity.