https://www.interviewbit.com/tutorial/two-pointers/
https://www.interviewbit.com/courses/programming/topics/two-pointers/
https://tp-iiita.quora.com/The-Two-Pointer-Algorithm
https://leetcode.com/articles/two-pointer-technique/
This topic in itself is not particularly broad. However, a lot of interviews tend to be a little biased to questions using this technique which prompted us to separate it out as another topic.
So, two pointer ( or N pointer for that matter ) is usually a really clever optimization on some bruteforce approches in certain condition.
Let us start looking at this with the help of a question. Then we will generalize our approach.
Example:
Given a sorted array A ( sorted in ascending order ),
find if there exists 2 integers A[i] and A[j] such that A[i] + A[j] = 0, i != j
Now, with the same analysis, as ‘i’ increases, A[i] also increases.
And the number of iterations after which ‘j’ breaks also increases.
But note what changes when ‘i’ moves to i + 1:
And the number of iterations after which ‘j’ breaks also increases.
But note what changes when ‘i’ moves to i + 1:
- If A[i] + A[J] > 0,
- Then A[i + 1] + A[J] is also greater than 0, as A[i + 1] > A[i].
This means if we have tried J for ‘i’, then when moving to i + 1, we should only try values of j < J.
This concludes that our ‘j’ should be monotonically decreasing and we could re-write the above solution as :
int j = A.size() - 1;
for (int i = 0; i < A.size(); i++)
for (; j > i; j--) {
if (i != j && A[i] + A[j] == 0) return true; // solution found.
if (A[i] + A[j] < 0) break; // Clearly A[i] + A[j] would decrease as j decreases.
}
Let us analyze the time complexity of the above solution.
Let us say A.size() = n.
Let us say A.size() = n.
- ‘i’ moves in total of n steps.
- ‘j’ also moves in total of n steps
( j– is executed atmost n times. Note that we are never increasing the value of j. Neither are we resetting it ).
That means we take in total of n + n steps = O(n).
In general, all two pointer approach work similarly. You look at the naive solution involving multiple loops and then you start analyzing the pattern on each loop.
Try to look for monotonicity in one of the loops as other loops move forward. If you find that, you have found your optimization.
Try to look for monotonicity in one of the loops as other loops move forward. If you find that, you have found your optimization.
https://tp-iiita.quora.com/The-Two-Pointer-Algorithm
Motivation Problem: Given two sorted arrays and each having length and respectively. Form a new sorted merged array having values of both the arrays in sorted format.
These kind of problems usually involve two pointers:
One slow-runner and the other fast-runner.
A classic example is to remove duplicates from a sorted array, which is available for you to practice here.
There is another variation to that:
https://www.geeksforgeeks.org/two-pointers-technique/\One pointer starts from the beginning while the other pointer starts from the end.
Two pointer is really an easy and effective technique which is typically used for searching pairs in a sorted arrays.
Given a sorted array A (sorted in ascending order), having N integers, find if there exists any pair of elements (A[i], A[j]) such that their sum is equal to X.
The 2 pointer technique is mostly applicable in sorted arrays where we try to perform a search in O(N).
Unit 4 Two Pointers | LeetLintcode
2根指针有3种题型:
- 一个数组, 从两边向中间移动(对撞型)
- 一个数组, 同时向前移动(前向型)
- 两个数组(并行型)
- 重点是记住: 模版是死的, 人是活的. 不要拘泥于模版. 参见min Substring contains target把题做少, 即所有新题都往会的方法上面靠.
对撞型
inspired by Qsort's partition. 有2个类型的题目:
- 2 sum
- partition
- 模版
- Two sum模版
int i = 0, j = leng-1;
while (i < j) {
if (a[i] + a[j] > sum) {
do something
j--;
}
else if (a[i] + aj] < sum) {
do something
i++;
}
else {
do something
i++/j--/
}- 总结模版
int i = 0, j = leng-1;
while (i < j) {
if (A[i]和A[j]满足某个条件) {
j--; // 直接跳过k ∈ [i+1, j-1] 和j组成的pair, 这需要证明. 也是O(n^2)-> O(n)的关键.
do something
}
else if (A[i]和A[j]不满足某个条件) {
i++; // 直接跳过i和k E [i+1, j-1]组成的pair.
do something
}
else {
do something
i++或者j--.
}
}
Trapping water area
container with most water
- 方法1: brute force.
- 通过2层循环, 找到每一个pair组合构成的面积. O(n^2).
- 方法2: 灌水型的都想到对撞型指针.
- 条件是什么呢? 这里有个数学分析: 先找到l/r里面的短板. 那么重点来了: 不用循环i跟[i~j]的板子组成的container. 因为面积由短板决定. 所以若[i~j]之间有比i更小的板, 那么面积只会是heights[k] (k-i). 所以比[i,j]组成的小. 或者, 如果[i~j]之间有比i大的板子, 那么面积也只会是heights[i] (k-i). 因为k < j. 所以更小. 于是证明了, 每次只要找到短板构成的面积, 然后和全局res来update.
前向型
2类题目:
- 窗口类: 注意和sliding window不同, sliding window是给定了窗口大小, 找一个符合条件的窗口; 而two pointer的窗口型是指大小不确定, 找一个符合条件的窗口. 所以前者使用heap, deque维护. 后者通过指针来维护.
- 快慢类
- 模版:
int i,j; while (i < leng) { while (j < leng) { if (满足条件) { 更新结果/HashMap j++; } else { break; } } 更新结果/HashMap i++; }
Minimum Window Substring contains target string in source
题目: Given a set T of characters and a string S, find the minimum window in S which will contain all the characters in T in complexity O(n). S = “ADOBECODEBANC” T = “ABC” Minimum window is “BANC”.
- 类似题目: longest substring with at most k distinct characters
- Key: 重点在于理解前向型双指针的算法思想. 而不是生搬硬套九章模版(应该适当修改). 学习如何用HashMap来作为数组存在判定.
- 分析: 我一开始按照九章的前向型模版套着写的, 很简单, 但是也不太好. 因为每一次都要对256个数字判断. 所以Time complexity是O(256N). 老师讲了用source hash - target hash的方法. 但是我写的有错. 不知道怎么处理找到window的时候怎么去掉第一个char, 以及更新状态(即所有全局变量).
- 然后搜到了Leetcode的答案, 以及Rui Bi精彩的Java实现. 其实就是前向型双指针的使用, 不过和template有点小小区别.
- 意思如图:
. 关键在于实现. 特别是找到window之后, 怎么advance pointer以及更新状态?
- 意思如图:
- 代码如下
/**
* http://xmruibi.github.io/2015/10/08/minimum-window-substring/
* http://articles.leetcode.com/2010/11/finding-minimum-window-in-s-which.html
*/
public String minWindow(String source, String target) {
// preload for target checking
if (source == null || source.length() == 0 || target == null || target.length() == 0) return "";
int tarLen = target.length();
HashMap<Character, Integer> dict = new HashMap<>(); // target hash
for (char c : target.toCharArray()) // 简洁
dict.put(c, dict.containsKey(c) ? dict.get(c) + 1 : 1); // 好写法!
int hitCount = 0; // record current window hits how many characters in target
int l = 0; // record the left bound of current window
int minWindow = source.length() + 1; // initial the minimum window length
int start = 0; // hold the global left bound of min window
for (int r = 0; r < source.length(); r++) {
char cur = source.charAt(r); // 因为只考虑一个char, 所以保存起来, 避免每次都用charAt求.
if (!dict.containsKey(cur)) continue; // 若不符合, 就找下一个点.即增加right.
dict.put(cur, dict.get(cur) - 1); // 更新Target hash. 注意这个也同时表示了Diff hash. 即当前window和target hash之差. 所以找到一个window并不是说Target hash全为0. 例如AAAABC里面找ABC. 则第一个window就会导致Thash的A为-3.
if (dict.get(cur) >= 0) hitCount++; // 关键之一: 通过Target hash, 判定是否已经找到了一个有效字符. 负数的次数也是有用的, 表明当前window有多于target的target[j]. 这在前移left的时候用到.
// check the windows has amount of this char more than it in target string
// loop until the amount back to normal, but always reduce the prev index char
while (hitCount == tarLen) { // 满足条件的情况.
if (minWindow > r - l + 1) {
start = l;
minWindow = r - l + 1;
}
char prevChar = source.charAt(l);
if (dict.containsKey(prevChar)) { // hashmap比int[256]好处在于存在就是target里的char.
dict.put(prevChar, dict.get(prevChar) + 1); // 关键2: 如何更新状态? 恢复dict即说明下一次for要继续找到prevChar.
if (dict.get(prevChar) > 0) hitCount--; // 当Target hash里面有正数个prevChar, 那就要找这个char, 于是hitcount恢复为自减1.
}
l++;
}
}
//
if (minWindow > source.length()) return ""; // 注意如果没找到, 应该回复空.
return source.substring(start, start + minWindow);
}