1/21 two pointers - clashing(对撞型)

分为以下几类：

  • two sum类
    • note that the assumptions:
      • original array should be sorted
      • while (left < right) ...
  • partition 类
    • 3 way partition: motivation: Arrays with large numbers of duplicate sort keys arise frequently in applications. In such applications, there is potential to reduce the time of the sort from linearithmic to linear. One straightforward idea is to partition the array into three parts, one each for items with keys smaller than, equal to, and larger than the partitioning item's key.
    • wiggle sort: the key is how to keep the relation,
  • 灌水类
    • 本质还是两指针，但是有可能需要别的指针辅助

two sum 类：

two sum 1:

the basic idea is that: We can do it in one pass. While we iterate and inserting elements into the table, we also look back to check if current element's complement already exists in the table. If it exists, we have found a solution and return immediately.

the implementation is simple.

two sum 2:

check whether array is sorted, if yes, we can use two pointers to solve the problem; if not, we only use hash table to store the number and position pair. and the problem converted into the two sum 1.

in this problem, we know that the original array is sorted. So We use two indexes, initially pointing to the first and last element respectively. Compare the sum of these two elements with target. If the sum is equal to target, we found the exactly only solution. If it is less than target, we increase the smaller index by one. If it is greater than target, we decrease the larger index by one. Move the indexes and repeat the comparison until the solution is found.

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int left = 0, right = numbers.length - 1;

        while (left < right) {
            int val = numbers[left] + numbers[right];
            if (val < target) {
                left++;
            } else if (val > target) {
                right--;
            } else {
                return new int[]{left + 1, right + 1};
            }
        }
        return new int[]{-1, -1};
    }
}

3 sum

at first, need to sort the original array, then we need to pay attention to removing duplicates, 尤其是找到解之后的去重

clarify: -is the array sorted? do we need to consider the situation where input contains duplicates?

The idea is to sort an input array and then run through all indices of a possible first element of a triplet. For each possible first element we make a standard bi-directional 2Sum sweep of the remaining part of the array. Also we want to skip equal elements to avoid duplicates in the answer without making a set or smth like that.

time complexity: O(n^2)

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        if (nums == null || nums.length == 0) return res;

        Arrays.sort(nums);
        for (int i = 0; i < nums.length - 2; i++) {
            if (i != 0 && nums[i] == nums[i - 1]) continue;

            int first = nums[i];
            int left = i + 1, right = nums.length - 1;
            while (left < right) {
                int val = nums[left] + nums[right];
                if (val > -first) {
                    right--;
                } else if (val < -first) {
                    left++;
                } else {
                    List<Integer> list = Arrays.asList(first, nums[left], nums[right]);
                    res.add(list);

                    while (left < right && nums[left] == nums[left + 1]) left++;
                    while (left < right && nums[right] == nums[right - 1]) right--;
                    left++;
                    right--;
                }
            }

        }
        return res;
    }
}

3 sum closest

要求返回sum 当存在 min difference的时候，所以用一个变量用来存sum，一个变量存diff。初始值设为无穷大，之后在每次循环里update。note that, we need to return the sum of the three numbers that satisfy the requirement.

good explaination: "Similar to 3 Sum problem, use 3 pointers to point current element, next element and the last element. If the sum is less than target, it means we have to add a larger element so next element move to the next. If the sum is greater, it means we have to add a smaller element so last element move to the second last element. Keep doing this until the end. Each time compare the difference between sum and target, if it is less than minimum difference so far, then replace result with it, otherwise keep iterating."

是不是sorted，要clarify。

class Solution {
    public int threeSumClosest(int[] nums, int target) {
        if (nums == null || nums.length == 0) return -1;
        int diff = Integer.MAX_VALUE;
        int sum = Integer.MAX_VALUE;

        Arrays.sort(nums);
        for (int i = 0; i < nums.length - 2; i++) {
            if (i != 0 && nums[i] == nums[i - 1]) continue;

            int first = nums[i];
            int left = i + 1, right = nums.length - 1;
            while (left < right) {
                int total = first + nums[left] + nums[right];
                if (total - target > 0) {
                    if (Math.abs(total - target) < diff) {
                        diff = (int)Math.abs(total - target);
                        sum = total;
                    }
                    right--;
                } else if (total - target < 0) {
                    if (Math.abs(total - target) < diff) {
                        diff = (int)Math.abs(total - target);
                        sum = total;
                    }
                    left++;
                } else {
                    diff = 0;
                    sum = target;
                    break;
                }
            }
        }
        return sum;
    }
}

3 sum smaller

这道题注意，我们要返回的是满足条件的index triplet的数量，所以不用去重复，

class Solution {
    public int threeSumSmaller(int[] nums, int target) {
        if (nums == null || nums.length == 0) return 0;

        Arrays.sort(nums);
        int count = 0;
        for (int i = 0; i < nums.length - 2; i++) {
            int first = nums[i];
            int left = i + 1, right = nums.length - 1;
            while (left < right) {
                int total = first + nums[left] + nums[right];
                if (total < target) {
                    count += (right - left);   // pay attention
                    left++;
                } else {
                    right--;
                }
            }
        }
        return count;
    }
}

similar problems: Two sum - Greater than target (lintcode)

Triangle sort

如果按照原来two pointer的思路，外面的就是用i = 1 to n做最外循环，j和k都在i后面，这样的话，如果当前条件不满足，j++和k--都可以是对的。就违反了双指针不同程度上利用的单调性，一次只把一个指针往一个方向推，而且不回头。正确的做法是，最外围遍历的是k， 而i, j都处于k的左面，那么每次就只有一个正确方 向，挪动一个指针可以保证正确性了，即让num[i] + num[j]变大，或者变小.

based on the necessity of the length of the sides of a triangle, (a + b > c) && (a + c > b) && (b + c > a), in a sorted array a<b<c, we only need to make sure a + b < c,

public class Solution {
    /*
     * @param S: A list of integers
     * @return: An integer
     */
    public int triangleCount(int[] S) {
        // write your code here
        if (S == null || S.length == 0) return 0;

        Arrays.sort(S);
        int n = S.length, count = 0;
        for (int k = 0; k < n; k++) {
            int left = 0, right = k - 1;
            while (left < right) {
                if (S[left] + S[right] <= S[k]) {
                    left++;
                } else {
                    count += (right - left);
                    right--;
                }
            }
        }
        return count;
    }
}

partition 类

规范一下自己写array问题的变量名用法：

  • left, right 代表移动指针
  • start, end 代表区间起始
  • low, high when it comes to binary search

Kth Largest Element in an Array

除了用quick select，还可以用3 way partitioning思路来写，复杂度一样

sort colors

其实 3 way partitioning中，key可以再细分为lowerKey 和higherKey，然后array 就被分隔为三个区间，这道题 lowerKey = higherKey = 1. 使用two pointers在one-pass解决。要注意的是，当和指针right重合后才停止，因为重合的位置也可能要swap。还有在blue swap后，不要继续往前走，还要check swap过来的color，red swap不用，因为之前已经访问过了。

// ## 0, 1, 2 = red, white, blue

class Solution {
    public static void sortColors(int[] nums) {
        int left = 0, right = nums.length - 1;
        int cur = 0, key = 1;

        while (cur <= right) {
            if (nums[cur] < key) {
                swap(nums, cur++, left++);
            } else if (nums[cur] > key) {
                swap(nums, cur, right--);
            } else {
                cur++;
            }
        }
    }

    private static void swap(int[] nums, int a, int b) {
        int temp = nums[a];
        nums[a] = nums[b];
        nums[b] = temp;
    }
}

sort colors 2

这道题在上一题基础上做一个k way partitioning.

tip: simplest way to output an array: System.out.println(Arrays.toString(nums)); O(nk)

最容易犯的错误是，套用sort color 1, 然后每次变化lowKey 和highKey, 搜索范围还是整个array，问题是当lowKey + 1 == highKey时，你没法确保中间那一段是有序的。注意要想completely sorted, lowKey和 highKey 要用==。

public class Solution {

    public void sortColors2(int[] colors, int k) {
        // write your code here
        if (colors == null || colors.length == 0) return;

        int left = 0, right = colors.length - 1, i = 0, lowKey = 1, highKey = k;
        while (lowKey < highKey) {
            i = left;
            while (i <= right) {
                if (colors[i] == lowKey) {
                    swap(colors, left++, i++);
                } else if (colors[i] == highKey) {
                    swap(colors, i, right--);
                } else {
                    i++;
                }
            }
            lowKey++;
            highKey--;
        }
    }

    private void swap(int[] nums, int a, int b) {
        int temp = nums[a];
        nums[a] = nums[b];
        nums[b] = temp;
    }
}

what if the array contains some irrelevant numbers? the assumption is that # of kinds of sorted numbers should be 3.

private static void sortColors3(int[] nums) {
        if (nums == null || nums.length == 0) return;

        int n = nums.length;
        int low = 0, high = n - 1, cur = low;

        while (cur <= high) {

            if (nums[cur] == 0) {
                while (nums[low] != nums[cur] &&
                        nums[low] != 0 &&
                        nums[low] != 1 &&
                        nums[low] != 2) {
                    low++;
                }
                swap(nums, cur++, low++);
            } else if (nums[cur] == 2) {
                while (nums[high] != nums[cur] &&
                        nums[high] != 0 &&
                        nums[high] != 1 &&
                        nums[high] != 2) {
                    high--;
                }
                swap(nums, cur, high--);
            } else {
                cur++;
            }
        }
}

private static void swap(int[] nums, int a, int b) {
    int temp = nums[a];
    nums[a] = nums[b];
    nums[b] = temp;
}

related problems: Sort an array according to the order defined by another array

https://www.geeksforgeeks.org/sort-array-according-order-defined-another-array/

wiggle sort

考察如何利用数组的单调性monotonicity，这个单调性每走一步会变一次方向。

naive implementation: Time: O(n log(n))

class Solution {
    public void wiggleSort(int[] nums) {
        Arrays.sort(nums);

        for (int i = 1; i < nums.length - 1; i += 2) {
            swap(nums, i, i + 1);
        }
    }

    private void swap(int[] nums, int a, int b) {
        int temp = nums[a];
        nums[a] = nums[b];
        nums[b] = temp;
    }
}

下面的这个解法 Time: O(n)，来分析下

0 1 2 3 4 5

1, 6, 2, 5, 3, 4

We want to guarantee that the number in odd index should be in peak while the number in even index should be in valley.

class Solution {
    public void wiggleSort(int[] nums) {
        if (nums == null || nums.length < 2) return;

        for (int i = 1; i < nums.length; i++) {
            if ((i%2 == 1 && nums[i] < nums[i - 1]) || (i%2 == 0 && nums[i] > nums[i - 1])) {
                int temp = nums[i];
                nums[i] = nums[i - 1];
                nums[i - 1] = temp;
            }
        }
    }
}

how to prove that? let we analyze further one situation.

0 1 2 3 4 5

3, 5, 2, 1, 6, 4

assuming we already keep the relation: Num(Ind(1)) >= Num(Ind(2)), and then we reach index 3, find that Num(Ind(2)) >= Num(Ind(3)), so we want to swap(Ind(2), Ind(3)). Based on previous two relation inequations, we definitely can keep the relation that Num(Ind(1)) >= Num(Ind(3)) <= Num(Ind(2)).

一道google 面经题，generalized wiggle sort, 深刻理解什么是wiggle sort

wiggle sort 2

很重要的题，考察怎么样去划分array，怎样穿插fill，下面这个解法是time: O(n log(n)) space: O(n)

idea is that:

0, 1, 2, 3, 4

1, 2, 2, 3, 3

: <- mid <- end

找到中位数 mid = (n - 1) / 2 end = n - 1; where n is the length of the array, 然后从后往前填充array

class Solution {
    public void wiggleSort(int[] nums) {
        if (nums == null || nums.length == 0) return;

        Arrays.sort(nums);
        int n = nums.length;
        int mid = (n - 1) / 2, end = n - 1, index = 0;
        int[] arr = new int[n];
        while (index < n) {
            if (index == n - 1) {
                arr[index++] = nums[mid--];
                break;
            }
            arr[index++] = nums[mid--];
            arr[index++] = nums[end--];
        }
        for (int i = 0; i < n; i++) {
            nums[i] = arr[i];
        }
    }
}

另一种解法能实现time: O(n) space O(1) 后面添加理解！

original : 0, 1, 2, 3, 4, 5

mapped ind: 1, 3, 5, 0, 1, 2

the mapping is (1 + 2*index) % (n | 1)

   public void wiggleSort(int[] nums) {
        int median = findKthLargest(nums, (nums.length + 1) / 2);
        int n = nums.length;

        int left = 0, i = 0, right = n - 1;

        while (i <= right) {

            if (nums[newIndex(i,n)] > median) {
                swap(nums, newIndex(left++,n), newIndex(i++,n));
            }
            else if (nums[newIndex(i,n)] < median) {
                swap(nums, newIndex(right--,n), newIndex(i,n));
            }
            else {
                i++;
            }
        }


    }

    private int newIndex(int index, int n) {
        return (1 + 2*index) % (n | 1);
    }

https://leetcode.com/problems/wiggle-sort-ii/discuss/77682/

灌水类

container with most water

We have to maximize the Area that can be formed between the vertical lines using the shorter line as length and the distance between the lines as the width of the rectangle forming the area. In BF, we will simply consider the area for every possible pair of the lines and find out the maximum area out of those. The time complexity would be O(n^2), space complexity would be O(1).

In two pointer approach, We take two pointers, one at the beginning and one at the end of the array constituting the length of the lines. Futher, we maintain a variable maxArea to store the maximum area obtained till now. At every step, we find out the area formed between them, update maxArea and move the pointer pointing to the shorter line towards the other end by one step.

class Solution {
    public int maxArea(int[] height) {
        if (height == null || height.length == 0) return 0;

        int n = height.length;

        int maxArea = Integer.MIN_VALUE;
        int left = 0, right = n - 1;
        while (left < right) {
            maxArea = Math.max(maxArea, Math.min(height[left], height[right]) * (right - left));
            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
        }
        return maxArea;
    }
}

trap rain water 1

和之前水桶题的区别在于，你不仅要知道当前能装多少水，还需要keep lower boundary of the container，so we keep the lowBound variable as left and right pointer move in the opposite direction.

class Solution {
    public int trap(int[] height) {
        if (height == null || height.length == 0) return 0;

        int left = 0, right = height.length - 1;
        int lowBound = 0, area = 0;

        while (left < right) {
            lowBound = Math.max(lowBound, Math.min(height[left], height[right]));

            if (height[left] <= height[right]) {
                if (height[left] <= lowBound) {
                    area += (lowBound - height[left]);
                }
                left++;
            } else {
                if (height[right] <= lowBound) {
                    area += (lowBound - height[right]);
                }
                right--;
            }
        }
        return area;
    }
}

trap rain water 2

这道题跟上一题的区别在于，是二维的，怎么去找最小的boundary，难点在于找完后怎么添加。有以下几点注意下：

  • 用priority queue 去找最小的boundary
  • 用2D visited array 去重复
  • 访问过一个cell后，不管这个cell的height是多少，我们要添加一个新的cell，其height为自身height与访问它的cell height的较大值。
class Solution {
    class Cell{
        int val;
        int row;
        int col;

        public Cell(int num, int row, int col) {
            this.val = num;
            this.row = row;
            this.col = col;
        }
    }
    public int trapRainWater(int[][] heightMap) {
        if (heightMap == null || heightMap.length == 0 || heightMap[0].length == 0) return 0;

        int m = heightMap.length;
        int n = heightMap[0].length;

        PriorityQueue<Cell> pqmin = new PriorityQueue<>(new Comparator<Cell>(){
           public int compare(Cell a, Cell b) {
               return Integer.compare(a.val, b.val);
           } 
        });

        boolean[][] visited = new boolean[m][n];
        for (int i = 0; i < m; i++) {
            visited[i][0] = true;
            visited[i][n - 1] = true;
            pqmin.offer(new Cell(heightMap[i][0], i, 0));
            pqmin.offer(new Cell(heightMap[i][n - 1], i, n - 1));
        }

        for (int i = 0; i < n; i++) {
            visited[0][i] = true;
            visited[m - 1][i] = true;
            pqmin.offer(new Cell(heightMap[0][i], 0, i));
            pqmin.offer(new Cell(heightMap[m - 1][i], m - 1, i));
        }

        int area = 0;

        while (!pqmin.isEmpty()) {
            Cell c = pqmin.poll();

            for (int[] pair : pairs) {
                int x = pair[0] + c.row;
                int y = pair[1] + c.col;

                if (x < 0 || x > m - 1 || y < 0 || y > n - 1 || visited[x][y]) continue;

                visited[x][y] = true;

                if (heightMap[x][y] <= c.val) {
                    area += (c.val - heightMap[x][y]);
                }

                pqmin.offer(new Cell(Math.max(heightMap[x][y], c.val), x, y));   // pay attention!!!
            }
        }
        return area;
    }

    private int[][] pairs = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
}

results matching ""

    No results matching ""