DEV Community

Cover image for LeetCode Challenge: 11. πŸ“¦ Container With Most Water - JavaScript Solution πŸš€
Rahul Kumar Barnwal
Rahul Kumar Barnwal

Posted on

3 1 1 1 2

LeetCode Challenge: 11. πŸ“¦ Container With Most Water - JavaScript Solution πŸš€

Top Interview 150

When it comes to solving LeetCode Problem 11: Container With Most Water, we aim to optimize for both time and space complexity. This problem is a classic example of leveraging the two-pointer technique to solve a greedy algorithm challenge efficiently.

Let’s dive in! πŸŠβ€β™‚οΈ


Problem Breakdown πŸ“

You're given an array height where each element represents the height of vertical lines on a coordinate plane. The goal is to:

  • Find two lines that, along with the x-axis, form a container holding the most water.
  • Return the maximum amount of water the container can store. The water area between two lines is determined by:

Formula


πŸ”‘ Key Constraints:

Key Constraints


Examples ✨

Example 1:

Example1

Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
Enter fullscreen mode Exit fullscreen mode

Explanation:
The two lines at indices 1 and 8 (heights 8 and 7, respectively) create a container of width 8 - 1 = 7 and height 7. Thus, the area is:

Formula

Example 2:

Input: height = [1,1]
Output: 1
Enter fullscreen mode Exit fullscreen mode

Explanation:
The two lines are both of height 1. The width is 1, so the area is:

Formula


πŸš€ Efficient Solution: Two-Pointer Technique

The brute-force approach of checking all pairs of lines would require
O(n2) time, which is not feasible for large inputs. Instead, we use two pointers:

  • Start with one pointer at the leftmost index (left) and another at the rightmost index (right).
  • Calculate the area between these two lines.
  • Move the pointer pointing to the shorter line inward, as the area is constrained by the shorter height.
  • Repeat until the two pointers meet.

JavaScript Code Implementation πŸ‘¨β€πŸ’»

var maxArea = function(height) {
    let left = 0;
    let right = height.length - 1;
    let maxArea = 0;

    while (left < right) {
        const width = right - left;
        const currentArea = Math.min(height[left], height[right]) * width;

        maxArea = Math.max(maxArea, currentArea);

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

    return maxArea;
};
Enter fullscreen mode Exit fullscreen mode

πŸ“Š Complexity Analysis:

  • Time Complexity: O(n)
    • The two pointers traverse the array at most once.
  • Space Complexity: O(1)
    • No extra space is used.

Dry Run 🧐

Let’s break down the code step-by-step with the input height = [1,8,6,2,5,4,8,3,7]:

Dry Run
Final output: 49


Why It Works πŸ”

  • Greedy Approach: Moving the pointer with the smaller height eliminates a line that would have limited the container’s capacity. This ensures we maximize the potential for a larger area.
  • Two-Pointer Efficiency: Only one pass is made through the array, minimizing time complexity.

🚩 Constraints Check

  • The algorithm handles the edge cases, such as:
    • Height array with only two elements: Returns the correct result.
    • All heights are zero: Returns 0.
    • Varying heights: Maximizes the area.

πŸ† Results

The above solution:

  • Time Complexity: O(n)
  • Space Complexity: O(1)

This implementation is efficient and scalable, capable of handling the upper constraint of 10^5 elements.


Final Thoughts πŸ’‘

Understanding the two-pointer technique is a game-changer for many array-based problems. This approach minimizes redundant calculations and optimizes performance.

If you enjoyed this post or have questions, let me know in the comments! πŸ™Œ

πŸ‘‰ Try it out and share your results below. Happy coding! 😊


Top comments (1)

Collapse
 
rahulgithubweb profile image
Rahul Kumar Barnwal β€’

Follow Me on GitHub πŸš€

If you found this solution helpful, check out more of my projects and solutions on my GitHub profile.

Don't forget to follow for more updates!

Billboard image

The Next Generation Developer Platform

Coherence is the first Platform-as-a-Service you can control. Unlike "black-box" platforms that are opinionated about the infra you can deploy, Coherence is powered by CNC, the open-source IaC framework, which offers limitless customization.

Learn more

πŸ‘‹ Kindness is contagious

Please leave a ❀️ or a friendly comment on this post if you found it helpful!

Okay