algoadvance

Leetcode 11. Container With Most Water

Problem Statement

You are given an array height of n non-negative integers where each element represents the height of a vertical line on a 2D plane. The goal is to find two lines such that, together with the x-axis, they form a container that holds the maximum amount of water.

Return the maximum amount of water a container can store.

Example

Given the array height = [1,8,6,2,5,4,8,3,7], the maximum amount of water the container can store is 49 (formed by the lines at index 1 and 8).

Assumptions

Clarifying Questions

  1. What is the size range of the input array?
    • The array length can range from 2 to (10^5).
  2. What is the range of heights in the input array?
    • Each height is a non-negative integer ranging from 0 to (10^4).
  3. Can there be multiple solutions or just one?
    • We only need to return the maximum water capacity, so the number of optimal solutions does not matter.
  4. Do we need to handle any specific edge cases?
    • As long as we adhere to the input constraints where there are at least two elements and all heights are non-negative, typical edge cases should be manageable by ensuring the algorithm can handle small and large input sizes efficiently.

Strategy

To solve this problem efficiently, we can use the two-pointer approach:

  1. Initialize two pointers:
    • One at the beginning (left = 0) and one at the end (right = n-1) of the array.
  2. Calculate the area:
    • Compute the area formed between the lines at the two pointers and determine the minimum of the heights of these two lines to determine the water level.
    • Move the pointer pointing to the shorter line inward by one position since the limiting factor in height will need to potentially find a taller line to increase the area.
  3. Iterate:
    • Repeat the process while adjusting the pointers towards each other until they meet.
  4. Track the maximum area:
    • Keep track of the maximum area encountered during iterations.

This approach ensures an efficient O(n) time complexity with a single pass through the array.

Code

#include <vector>
#include <algorithm>

class Solution {
public:
    int maxArea(std::vector<int>& height) {
        int left = 0; 
        int right = height.size() - 1;
        int max_area = 0;

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

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

        return max_area;
    }
};

Time Complexity

The time complexity of this solution is O(n), where n is the number of elements in the input array. This is because we only make a single pass through the array with the two pointers, moving them towards the center.

The space complexity is O(1), as we are only using a fixed amount of extra space.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI