Two Pointers

def max_area(height: list[int]) -> int:
    """Most water two of the vertical lines in `height` can hold."""
    left, right = 0, len(height) - 1
    best = 0
    while left < right:
        water = min(height[left], height[right]) * (right - left)
        best = max(best, water)
        # The shorter line caps the water. Moving the taller one inward can only
        # shrink the width without raising that cap, so move the shorter one.
        if height[left] < height[right]:
            left += 1
        else:
            right -= 1
    return best


if __name__ == "__main__":
    print(max_area([1, 8, 6, 2, 5, 4, 8, 3, 7]))  # 49
    print(max_area([1, 1]))  # 1
    print(max_area([4, 3, 2, 1, 4]))  # 16

// Most water two of the vertical lines in `height` can hold.
export function maxArea(height: number[]): number {
  let left = 0;
  let right = height.length - 1;
  let best = 0;
  while (left < right) {
    const water = Math.min(height[left], height[right]) * (right - left);
    best = Math.max(best, water);
    // The shorter line caps the water. Moving the taller one inward can only
    // shrink the width without raising that cap, so move the shorter one.
    if (height[left] < height[right]) left++;
    else right--;
  }
  return best;
}

console.log(maxArea([1, 8, 6, 2, 5, 4, 8, 3, 7])); // 49
console.log(maxArea([1, 1])); // 1
console.log(maxArea([4, 3, 2, 1, 4])); // 16

package main

import "fmt"

// maxArea returns the most water two of the vertical lines in height can hold.
func maxArea(height []int) int {
	left, right := 0, len(height)-1
	best := 0
	for left < right {
		water := min(height[left], height[right]) * (right - left)
		best = max(best, water)
		// The shorter line caps the water. Moving the taller one inward can only
		// shrink the width without raising that cap, so move the shorter one.
		if height[left] < height[right] {
			left++
		} else {
			right--
		}
	}
	return best
}

func main() {
	fmt.Println(maxArea([]int{1, 8, 6, 2, 5, 4, 8, 3, 7})) // 49
	fmt.Println(maxArea([]int{1, 1}))                      // 1
	fmt.Println(maxArea([]int{4, 3, 2, 1, 4}))             // 16
}

using System;

public class Solution
{
    // Most water two of the vertical lines in height can hold.
    public static int MaxArea(int[] height)
    {
        int left = 0, right = height.Length - 1;
        int best = 0;
        while (left < right)
        {
            int water = Math.Min(height[left], height[right]) * (right - left);
            best = Math.Max(best, water);
            // The shorter line caps the water. Moving the taller one inward can only
            // shrink the width without raising that cap, so move the shorter one.
            if (height[left] < height[right]) left++;
            else right--;
        }
        return best;
    }

    public static void Main()
    {
        Console.WriteLine(MaxArea(new[] { 1, 8, 6, 2, 5, 4, 8, 3, 7 })); // 49
        Console.WriteLine(MaxArea(new[] { 1, 1 })); // 1
        Console.WriteLine(MaxArea(new[] { 4, 3, 2, 1, 4 })); // 16
    }
}

public class Solution {
    // Most water two of the vertical lines in height can hold.
    static int maxArea(int[] height) {
        int left = 0, right = height.length - 1;
        int best = 0;
        while (left < right) {
            int water = Math.min(height[left], height[right]) * (right - left);
            best = Math.max(best, water);
            // The shorter line caps the water. Moving the taller one inward can only
            // shrink the width without raising that cap, so move the shorter one.
            if (height[left] < height[right]) left++;
            else right--;
        }
        return best;
    }

    public static void main(String[] args) {
        System.out.println(maxArea(new int[] {1, 8, 6, 2, 5, 4, 8, 3, 7})); // 49
        System.out.println(maxArea(new int[] {1, 1})); // 1
        System.out.println(maxArea(new int[] {4, 3, 2, 1, 4})); // 16
    }
}

def three_sum(nums: list[int]) -> list[list[int]]:
    """Every unique triplet in `nums` that sums to zero, each in ascending order."""
    nums = sorted(nums)
    result = []
    for i in range(len(nums) - 2):
        if nums[i] > 0:
            break  # Everything after is positive too.
        if i > 0 and nums[i] == nums[i - 1]:
            continue  # Same first number, same triplets.
        left, right = i + 1, len(nums) - 1
        while left < right:
            total = nums[i] + nums[left] + nums[right]
            if total < 0:
                left += 1
            elif total > 0:
                right -= 1
            else:
                result.append([nums[i], nums[left], nums[right]])
                left += 1
                right -= 1
                # Step past repeats so the same triplet isn't added twice.
                while left < right and nums[left] == nums[left - 1]:
                    left += 1
                while left < right and nums[right] == nums[right + 1]:
                    right -= 1
    return result


if __name__ == "__main__":
    print(three_sum([-1, 0, 1, 2, -1, -4]))  # [[-1, -1, 2], [-1, 0, 1]]
    print(three_sum([0, 1, 1]))  # []
    print(three_sum([0, 0, 0, 0]))  # [[0, 0, 0]]

// Every unique triplet in `nums` that sums to zero, each in ascending order.
export function threeSum(nums: number[]): number[][] {
  const sorted = [...nums].sort((a, b) => a - b);
  const result: number[][] = [];
  for (let i = 0; i < sorted.length - 2; i++) {
    if (sorted[i] > 0) break; // Everything after is positive too.
    if (i > 0 && sorted[i] === sorted[i - 1]) continue; // Same first number, same triplets.
    let left = i + 1;
    let right = sorted.length - 1;
    while (left < right) {
      const sum = sorted[i] + sorted[left] + sorted[right];
      if (sum < 0) left++;
      else if (sum > 0) right--;
      else {
        result.push([sorted[i], sorted[left], sorted[right]]);
        left++;
        right--;
        // Step past repeats so the same triplet isn't added twice.
        while (left < right && sorted[left] === sorted[left - 1]) left++;
        while (left < right && sorted[right] === sorted[right + 1]) right--;
      }
    }
  }
  return result;
}

console.log(JSON.stringify(threeSum([-1, 0, 1, 2, -1, -4]))); // [[-1,-1,2],[-1,0,1]]
console.log(JSON.stringify(threeSum([0, 1, 1]))); // []
console.log(JSON.stringify(threeSum([0, 0, 0, 0]))); // [[0,0,0]]

package main

import (
	"fmt"
	"slices"
)

// threeSum returns every unique triplet in nums that sums to zero, each in
// ascending order.
func threeSum(nums []int) [][]int {
	sorted := slices.Clone(nums)
	slices.Sort(sorted)
	result := [][]int{}
	for i := 0; i < len(sorted)-2; i++ {
		if sorted[i] > 0 {
			break // Everything after is positive too.
		}
		if i > 0 && sorted[i] == sorted[i-1] {
			continue // Same first number, same triplets.
		}
		left, right := i+1, len(sorted)-1
		for left < right {
			sum := sorted[i] + sorted[left] + sorted[right]
			switch {
			case sum < 0:
				left++
			case sum > 0:
				right--
			default:
				result = append(result, []int{sorted[i], sorted[left], sorted[right]})
				left++
				right--
				// Step past repeats so the same triplet isn't added twice.
				for left < right && sorted[left] == sorted[left-1] {
					left++
				}
				for left < right && sorted[right] == sorted[right+1] {
					right--
				}
			}
		}
	}
	return result
}

func main() {
	fmt.Println(threeSum([]int{-1, 0, 1, 2, -1, -4})) // [[-1 -1 2] [-1 0 1]]
	fmt.Println(threeSum([]int{0, 1, 1}))             // []
	fmt.Println(threeSum([]int{0, 0, 0, 0}))          // [[0 0 0]]
}

using System;
using System.Collections.Generic;
using System.Linq;

public class Solution
{
    // Every unique triplet in nums that sums to zero, each in ascending order.
    public static List<int[]> ThreeSum(int[] nums)
    {
        var sorted = nums.OrderBy(n => n).ToArray();
        var result = new List<int[]>();
        for (int i = 0; i < sorted.Length - 2; i++)
        {
            if (sorted[i] > 0) break; // Everything after is positive too.
            if (i > 0 && sorted[i] == sorted[i - 1]) continue; // Same first number, same triplets.
            int left = i + 1, right = sorted.Length - 1;
            while (left < right)
            {
                int sum = sorted[i] + sorted[left] + sorted[right];
                if (sum < 0) left++;
                else if (sum > 0) right--;
                else
                {
                    result.Add(new[] { sorted[i], sorted[left], sorted[right] });
                    left++;
                    right--;
                    // Step past repeats so the same triplet isn't added twice.
                    while (left < right && sorted[left] == sorted[left - 1]) left++;
                    while (left < right && sorted[right] == sorted[right + 1]) right--;
                }
            }
        }
        return result;
    }

    public static void Main()
    {
        Console.WriteLine(Format(ThreeSum(new[] { -1, 0, 1, 2, -1, -4 }))); // [[-1, -1, 2], [-1, 0, 1]]
        Console.WriteLine(Format(ThreeSum(new[] { 0, 1, 1 }))); // []
        Console.WriteLine(Format(ThreeSum(new[] { 0, 0, 0, 0 }))); // [[0, 0, 0]]
    }

    static string Format(List<int[]> triplets) =>
        "[" + string.Join(", ", triplets.Select(t => "[" + string.Join(", ", t) + "]")) + "]";
}

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Solution {
    // Every unique triplet in nums that sums to zero, each in ascending order.
    static List<List<Integer>> threeSum(int[] nums) {
        int[] sorted = nums.clone();
        Arrays.sort(sorted);
        List<List<Integer>> result = new ArrayList<>();
        for (int i = 0; i < sorted.length - 2; i++) {
            if (sorted[i] > 0) break; // Everything after is positive too.
            if (i > 0 && sorted[i] == sorted[i - 1]) continue; // Same first number, same triplets.
            int left = i + 1, right = sorted.length - 1;
            while (left < right) {
                int sum = sorted[i] + sorted[left] + sorted[right];
                if (sum < 0) left++;
                else if (sum > 0) right--;
                else {
                    result.add(List.of(sorted[i], sorted[left], sorted[right]));
                    left++;
                    right--;
                    // Step past repeats so the same triplet isn't added twice.
                    while (left < right && sorted[left] == sorted[left - 1]) left++;
                    while (left < right && sorted[right] == sorted[right + 1]) right--;
                }
            }
        }
        return result;
    }

    public static void main(String[] args) {
        System.out.println(threeSum(new int[] {-1, 0, 1, 2, -1, -4})); // [[-1, -1, 2], [-1, 0, 1]]
        System.out.println(threeSum(new int[] {0, 1, 1})); // []
        System.out.println(threeSum(new int[] {0, 0, 0, 0})); // [[0, 0, 0]]
    }
}