283. Move Zeroes

The objective is to reorganize an array such that all non-zero elements are positioned before any zeros. This operation must be performed in-place without allocating additional space for another array.

Instead of using a secondary buffer, we can utilize a tracking pointer to mark the position where the next non-zero element should be placed. As we iterate through the array with a scout pointer, whenever a non-zero value is encountered, it is swapped with the value at the tracking pointer, effectively pushing zeros towards the end.

def move_zeroes(arr):
    # Position to place the next non-zero element
    insert_pos = 0
    
    for scout in range(len(arr)):
        if arr[scout] != 0:
            # Swap current element with the insert position
            arr[insert_pos], arr[scout] = arr[scout], arr[insert_pos]
            insert_pos += 1

11. Container With Most Water

Given an array of non-negative integers representing heights, the task is to find two lines that together with the x-axis form a container capable of holding the most water. The volume is determined by the distance between the lines and the height of the shorter line.

A brute force approach checking every pair would result in O(n^2) time complexity. By using two pointers starting at both ends of the array, we can optimize this. The logic dictates that moving the pointer pointing to the shorter line inward might lead to a larger area, whereas moving the longer line cannot increase the height constraint and only reduces the width.

def max_area(height):
    left = 0
    right = len(height) - 1
    max_vol = 0
    
    while left < right:
        # Calculate current volume
        width = right - left
        current_height = min(height[left], height[right])
        max_vol = max(max_vol, width * current_height)
        
        # Move the pointer pointing to the shorter line
        if height[left] < height[right]:
            left += 1
        else:
            right -= 1
            
    return max_vol

15. 3Sum

This problem requires finding all unique triplets in an array that sum up to zero. A naive triple loop is inefficient. Instead, we can sort the array and fix one number, then use a two-pointer technique to find the other two numbers that sum to the negative of the fixed number.

To ensure uniqueness, we skip duplicate values for the fixed number as well as for the second and third numbers within the inner loop.

def three_sum(nums):
    nums.sort()
    n = len(nums)
    result = []
    
    for i in range(n - 2):
        # Skip duplicates for the first element
        if i > 0 and nums[i] == nums[i - 1]:
            continue
            
        low, high = i + 1, n - 1
        target = -nums[i]
        
        while low < high:
            current_sum = nums[low] + nums[high]
            
            if current_sum == target:
                result.append([nums[i], nums[low], nums[high]])
                # Skip duplicates for the second element
                while low < high and nums[low] == nums[low + 1]:
                    low += 1
                # Skip duplicates for the third element
                while low < high and nums[high] == nums[high - 1]:
                    high -= 1
                low += 1
                high -= 1
            elif current_sum < target:
                low += 1
            else:
                high -= 1
                
    return result

42. Trapping Rain Water

Given an elevation map where the width of each bar is 1, compute how much water it can trap after raining. The water trapped at any specific index depends on the highest bar to its left and the highest bar to its right. The water level is the minimum of these two maximum heights.

We can solve this efficiently using two pointers. By maintaining `left_max` and `right_max`, we determine which side limits the water level. If `left_max` is smaller, we know the water trapped at the left pointer is determined by `left_max` (since there is a higher barrier on the right), and we process the left side. Otherwise, we process the right side.

def trap(height):
    if not height:
        return 0
        
    left, right = 0, len(height) - 1
    left_max, right_max = height[left], height[right]
    total_water = 0
    
    while left < right:
        if left_max < right_max:
            left += 1
            left_max = max(left_max, height[left])
            total_water += left_max - height[left]
        else:
            right -= 1
            right_max = max(right_max, height[right])
            total_water += right_max - height[right]
            
    return total_water