> For the complete documentation index, see [llms.txt](https://netjimmy.gitbook.io/code-interview-note/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://netjimmy.gitbook.io/code-interview-note/array/twopointer.md).

# TwoPointer

[Template](https://leetcode.com/problems/find-all-anagrams-in-a-string/discuss/92007/sliding-window-algorithm-template-to-solve-all-the-leetcode-substring-search-problem)

## 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.

```java
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]&#x20;
   * Time O(n), Space O(n)
2. Two Pointer
   * 在最高點左邊，trap只會受到leftMax影響。反之，在最高點右邊，trap只會受到rightMax影響
   * twoPointer從左右逐漸向最高點逼近

```python
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.

```java
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](https://www.youtube.com/watch?v=cJayBq38VYw)

```python
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]

```java
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

```java
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;
}
```