SDE - 1

Approach to Solve "Container With Most Water"

Two Pointer Technique:
Use two pointers, one starting at the beginning of the array and the other at the end. This technique explores all possible container widths while minimizing redundant calculations.

Calculate Area:
At each step, calculate the area formed by the vertical lines at the two pointers. The area is determined by the formula:

Area= (distance between pointers) ×min⁡(height[left], height[right])

Move the Smaller Pointer:
To maximize water storage, move the pointer pointing to the shorter vertical line inward. This is because the height of the container is limited by the shorter line, and moving it inward might lead to a taller container.

Repeat Until Pointers Meet:
Continue the process until the two pointers converge. Keep track of the maximum area encountered during this process.

This approach ensures an efficient solution with a time complexity of O(n), as each line is processed at most once.

The approach is mainly based on the following facts:

• If we consider a subarray arr[left…right], we can determine the amount of water for either arr[left] or arr[right], provided we know the left max (the maximum element in arr[0…left-1]) and the right max (the maximum element in arr[right+1…n-1]).
• If the left max is less than the right max, we can calculate the water for arr[left]. Otherwise, we can calculate it for arr[right].
• If we calculate for arr[left], the amount of water would be left max – arr[left].

Tip 1: Practice schema design for some case studies.
Tip 2: Discuss the requirements in detail initially before providing a solution.
Tip 3: Discuss everything possible; don’t readily change the schema if any requirements change.