TwoPointer

Template

11. Container With Most Water

Given n non-negative integers a1, a2, ..., an , where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

Example:

Input: [1,8,6,2,5,4,8,3,7] Output: 49

• 受制於比較矮的那一邊

• The shorter line's pointer might find higher line to overcome the reduction in area caused by the width reduction.

public int maxArea(int[] height) {
    int i=0, j=height.length-1;
    int max = Integer.MIN_VALUE;
    while(i<j){
        if(height[i] < height[j]){
            max = Math.max(max, height[i]*(j-i));
            i++;
        }else{
            max = Math.max(max, height[j]*(j-i));
            j--;
        }
    }
    return max;

42 Trapping Rain Water

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

Solution [https://leetcode.com/problems/trapping-rain-water/solution/]

1. DP

   • Record the highest point so far from left to right and right to left.

   • sum += min(left[i], right[i]) - height[i]

   • Time O(n), Space O(n)

2. Two Pointer

   • 在最高點左邊，trap只會受到leftMax影響。反之，在最高點右邊，trap只會受到rightMax影響

   • twoPointer從左右逐漸向最高點逼近

def trap(self, height: List[int]) -> int:
    l, r, s = 0, len(height)-1, 0
    lMax, rMax = 0, 0
    
    while l<r:
        if height[l] < height[r]:
            if height[l] < lMax: s += lMax - height[l]
            else: lMax = height[l]
            l+=1
        else:
            if height[r] < rMax: s += rMax - height[r]
            else: rMax = height[r]
            r-=1
    return s

407. Trapping Rain Water II

Given an m x n matrix of positive integers representing the height of each unit cell in a 2D elevation map, compute the volume of water it is able to trap after raining.

Example
[
  [1,4,3,1,3,2],
  [3,2,1,3,2,4],
  [2,3,3,2,3,1]
]

Return 4

• Greedy + minHeap

• Put boundary heights in minHeap, starting from the lowest boundary

• Update current height, traverse 4 directions

• Add to answer whenever we can see nextHeight < currentHeight

• Video explain

from heapq import *
class Solution:
    def trapRainWater(self, heightMap: List[List[int]]) -> int:
        m, n = len(heightMap), len(heightMap[0])
        maxHeight = float('-inf')
        visit = set()
        heap = []
        ans = 0
        
        for i in (0, m-1):
            for j in range(n):
                heappush(heap, (heightMap[i][j], i, j))
                visit.add((i, j))
        
        for j in (0, n-1):
            for i in range(1, m-1):
                heappush(heap, (heightMap[i][j], i, j))
                visit.add((i, j))
        
        while heap:
            height, x, y = heappop(heap)
            maxHeight = max(maxHeight, height)
            
            for dx, dy in ((0, 1), (1, 0), (0, -1), (-1, 0)):
                nx, ny = x + dx, y + dy
                
                if not (0 <= nx < m and 0 <= ny < n): continue
                if (nx, ny) in visit: continue
                visit.add((nx, ny))
                
                nextHeight = heightMap[nx][ny]
                if maxHeight > nextHeight:
                    ans += maxHeight - nextHeight
                heappush(heap, (nextHeight, nx, ny))
        
        return ans

768. Max Chunks To Make Sorted II

769 with duplicate number

• Store the max from left and store the min from left

• A pivot point is at the point minRight[i+1] >= maxMin[i]

public int maxChunksToSorted(int[] arr) {
    int len = arr.length;
    int[] maxLeft = new int[len];
    int[] minRight = new int[len];

    maxLeft[0] = arr[0];
    for(int i=1; i<len; i++){
        maxLeft[i] = Math.max(maxLeft[i-1], arr[i]); 
    }
    minRight[len-1] = arr[len-1];
    for(int i=len-2; i>=0; i--){
        minRight[i]= Math.min(minRight[i+1], arr[i]);
    }
    int count =1;
    for(int i=0; i<len-1; i++){
        if(minRight[i+1] >= maxLeft[i]) count++;
    }
    return count;
}

769. Max Chunks To Make Sorted

Given an array arr that is a permutation of [0, 1, ..., arr.length - 1], split the array into chunks, and individually sort each chunk. After concatenating them, the result equals the sorted array.

What is the most number of chunks we could have made?

• Use index as sorted answer array to match the current array

• Take the max number as pivot point

public int maxChunksToSorted(int[] arr) {
    /** index 0, 1, 2, 3, 4
     *  max   1, 1, 2, 3, 4  return 4
     *
     *  index 0, 1, 2, 3, 4
     *  max   4, 4, 4, 4, 4  return 1
     */
    int count = 0;
    int max = arr[0];

    for(int i=0; i< arr.length; i++){
        max = Math.max(max, arr[i]);
        if(max == i) count++;
    }
    return count;
}