You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the ith line are (i, 0) and (i, height[i]).

Find two lines that together with the x-axis form a container, such that the container contains the most water.

Return the maximum amount of water a container can store.

Notice that you may not slant the container.

Example 1:

Input: height = [1,8,6,2,5,4,8,3,7] Output: 49 Explanation: 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.

Example 2:

Input: height = [1,1] Output: 1

Constraints:

• n == height.length
• 2 <= n <= 105
• 0 <= height[i] <= 104

Approach: Hash Map (Optimal Solution)

Algorithm

1. Create a hash map to store values and their indices
2. Iterate through the array
3. For each element, calculate the complement (target - current value)
4. If complement exists in hash map, return the indices
5. Otherwise, store current value and index in hash map

Time & Space Complexity

• Time Complexity: O(n) - single pass through array
• Space Complexity: O(n) - hash map storage

Java Implementation

java

import java.util.HashMap;
import java.util.Map;

public class TwoSum {
    
    /**
     * Find indices of two numbers that add up to target.
     * @param nums Array of integers
     * @param target Target sum
     * @return Array containing indices of two numbers that sum to target
     */
    public static int[] twoSum(int[] nums, int target) {
        // Hash map to store value -> index mapping
        Map<Integer, Integer> numMap = new HashMap<>();
        
        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
            
            // If complement exists in map, we found our answer
            if (numMap.containsKey(complement)) {
                return new int[]{numMap.get(complement), i};
            }
            
            // Store current number and its index
            numMap.put(nums[i], i);
        }
        
        // This should never be reached given problem constraints
        return new int[]{};
    }
    
    // Test method
    public static void main(String[] args) {
        // Test case 1
        int[] nums1 = {2, 7, 11, 15};
        int target1 = 9;
        int[] result1 = twoSum(nums1, target1);
        System.out.println("Input: nums = [2, 7, 11, 15], target = 9");
        System.out.println("Output: [" + result1[0] + ", " + result1[1] + "]"); // Expected: [0, 1]
        
        // Test case 2
        int[] nums2 = {3, 2, 4};
        int target2 = 6;
        int[] result2 = twoSum(nums2, target2);
        System.out.println("Input: nums = [3, 2, 4], target = 6");
        System.out.println("Output: [" + result2[0] + ", " + result2[1] + "]"); // Expected: [1, 2]
        
        // Test case 3
        int[] nums3 = {3, 3};
        int target3 = 6;
        int[] result3 = twoSum(nums3, target3);
        System.out.println("Input: nums = [3, 3], target = 6");
        System.out.println("Output: [" + result3[0] + ", " + result3[1] + "]"); // Expected: [0, 1]
    }
}

Alternative Implementation with Enhanced Output

java

import java.util.HashMap;
import java.util.Map;

public class TwoSumEnhanced {
    
    /**
     * Find indices of two numbers that add up to target.
     * @param nums Array of integers
     * @param target Target sum
     * @return Array containing indices of two numbers that sum to target
     */
    public static int[] twoSum(int[] nums, int target) {
        // Hash map to store value -> index mapping
        Map<Integer, Integer> numMap = new HashMap<>();
        
        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
            
            // If complement exists in map, we found our answer
            if (numMap.containsKey(complement)) {
                return new int[]{numMap.get(complement), i};
            }
            
            // Store current number and its index
            numMap.put(nums[i], i);
        }
        
        // Return empty array if no solution found (shouldn't happen per problem constraints)
        return new int[]{};
    }
    
    /**
     * Helper method to print array
     */
    public static void printArray(int[] arr) {
        System.out.print("[");
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]);
            if (i < arr.length - 1) {
                System.out.print(", ");
            }
        }
        System.out.println("]");
    }
    
    // Test method
    public static void main(String[] args) {
        System.out.println("Two Sum Problem - Java Implementation");
        System.out.println("=====================================");
        
        // Test case 1
        int[] nums1 = {2, 7, 11, 15};
        int target1 = 9;
        int[] result1 = twoSum(nums1, target1);
        System.out.println("Test Case 1:");
        System.out.print("Input: nums = ");
        printArray(nums1);
        System.out.println("Target: " + target1);
        System.out.print("Output: ");
        printArray(result1);
        System.out.println();
        
        // Test case 2
        int[] nums2 = {3, 2, 4};
        int target2 = 6;
        int[] result2 = twoSum(nums2, target2);
        System.out.println("Test Case 2:");
        System.out.print("Input: nums = ");
        printArray(nums2);
        System.out.println("Target: " + target2);
        System.out.print("Output: ");
        printArray(result2);
        System.out.println();
        
        // Test case 3
        int[] nums3 = {3, 3};
        int target3 = 6;
        int[] result3 = twoSum(nums3, target3);
        System.out.println("Test Case 3:");
        System.out.print("Input: nums = ");
        printArray(nums3);
        System.out.println("Target: " + target3);
        System.out.print("Output: ");
        printArray(result3);
    }
}

Example Walkthrough

For nums = [2, 7, 11, 15] and target = 9:

1. i=0, num=2: complement = 9-2 = 7. 7 not in map. Store {2: 0}
2. i=1, num=7: complement = 9-7 = 2. 2 is in map at index 0. Return [0, 1]

Key Points

1. HashMap Usage: Uses HashMap<Integer, Integer> to store value-index pairs
2. Single Pass: Only iterates through array once for O(n) time complexity
3. Index Retrieval: Returns the actual indices, not the values
4. Edge Cases: Properly handles duplicate values like [3,3] with target 6
5. Memory Efficiency: Uses O(n) space for the hash map

The Java implementation follows the same logic as the Python version but uses Java’s HashMap and array syntax. The solution is optimal with linear time and space complexity.

Qwen3-Coder 30B-A3B Instruct

1,601 tokens 44s 35.65 t/s

You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the ith line are (i, 0) and (i, height[i]). Find two lines that together with the x-axis form a container, such that the container contains the most water. Return the maximum amount of water a container can store. Notice that you may not slant the container.

94 tokens 7.5s 12.50 tokens/s

Container With Most Water Problem Solution

Problem Understanding

Given an array of vertical lines, find two lines that form a container with the maximum amount of water. The container’s area is calculated as:

• Width: distance between the two lines (j - i)
• Height: minimum of the two line heights (min(height[i], height[j]))
• Area: width × height

Approach: Two Pointers (Optimal Solution)

Algorithm

1. Use two pointers, one at the beginning (left) and one at the end (right)
2. Calculate the area formed by these two lines
3. Move the pointer pointing to the shorter line inward
4. Keep track of the maximum area found
5. Continue until pointers meet

Key Insight

The area is limited by the shorter line. Moving the taller line inward can only decrease the width, so we must move the shorter line to potentially find a taller line that might create a larger area.

Time & Space Complexity

• Time Complexity: O(n) - single pass with two pointers
• Space Complexity: O(1) - only using constant extra space

Java Implementation

java

public class ContainerWithMostWater {
    
    /**
     * Find the maximum area of water that can be stored between two lines.
     * @param height Array of line heights
     * @return Maximum area of water that can be stored
     */
    public static int maxArea(int[] height) {
        int left = 0;
        int right = height.length - 1;
        int maxArea = 0;
        
        while (left < right) {
            // Calculate current area
            int width = right - left;
            int minHeight = Math.min(height[left], height[right]);
            int currentArea = width * minHeight;
            
            // Update maximum area
            maxArea = Math.max(maxArea, currentArea);
            
            // Move the pointer pointing to shorter line
            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
        }
        
        return maxArea;
    }
    
    // Test method
    public static void main(String[] args) {
        // Test case 1
        int[] height1 = {1, 8, 6, 2, 5, 4, 8, 3, 7};
        int result1 = maxArea(height1);
        System.out.println("Input: [1,8,6,2,5,4,8,3,7]");
        System.out.println("Maximum area: " + result1); // Expected: 49
        
        // Test case 2
        int[] height2 = {1, 1};
        int result2 = maxArea(height2);
        System.out.println("Input: [1,1]");
        System.out.println("Maximum area: " + result2); // Expected: 1
        
        // Test case 3
        int[] height3 = {4, 3, 2, 1, 4};
        int result3 = maxArea(height3);
        System.out.println("Input: [4,3,2,1,4]");
        System.out.println("Maximum area: " + result3); // Expected: 16
    }
}

Example Walkthrough

For height = [1,8,6,2,5,4,8,3,7]:

1. left=0, right=8: width=8, minHeight=min(1,7)=1, area=8×1=8
2. left=1, right=8: width=7, minHeight=min(8,7)=7, area=7×7=49
3. left=1, right=7: width=6, minHeight=min(8,3)=3, area=6×3=18
4. left=1, right=6: width=5, minHeight=min(8,8)=8, area=5×8=40
5. left=1, right=5: width=4, minHeight=min(8,4)=4, area=4×4=16
6. left=1, right=4: width=3, minHeight=min(8,5)=5, area=3×5=15
7. left=1, right=3: width=2, minHeight=min(8,2)=2, area=2×2=4
8. left=1, right=2: width=1, minHeight=min(8,6)=6, area=1×6=6

Maximum area = 49

Alternative Brute Force Approach (Less Efficient)

java

public static int maxAreaBruteForce(int[] height) {
    int maxArea = 0;
    int n = height.length;
    
    // Check all pairs
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            int width = j - i;
            int minHeight = Math.min(height[i], height[j]);
            int area = width * minHeight;
            maxArea = Math.max(maxArea, area);
        }
    }
    
    return maxArea;
}

Key Insights

1. Two Pointers Technique: Efficient approach that reduces time complexity from O(n²) to O(n)
2. Greedy Strategy: Always move the pointer with smaller height to potentially find a better area
3. Area Calculation: Area = width × min(height[left], height[right])
4. Optimality: The algorithm works because moving the taller line inward can only decrease the width, while moving the shorter line gives a chance to find a taller line

The two-pointer approach is the optimal solution for this problem, providing linear time complexity with constant space usage.