https://www.interviewbit.com/tutorial/two-pointers/
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:
- 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.
- ‘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.
https://www.interviewbit.com/courses/programming/topics/two-pointers/
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.
https://leetcode.com/articles/two-pointer-technique/
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:
One pointer starts from the beginning while the other pointer starts from the end.
https://www.geeksforgeeks.org/two-pointers-technique/\
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.
bool isPairSum(A[], N, X)
{
int i = 0;
int j = N - 1;
while (i < j) {
if (A[i] + A[j] == X)
return true;
else if (A[i] + A[j] < X)
i++;
else
j--;
}
return false;
}
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
- 一个数组, 从两边向中间移动(对撞型)
- 一个数组, 同时向前移动(前向型)
- 两个数组(并行型)
- 重点是记住: 模版是死的, 人是活的. 不要拘泥于模版. 参见min Substring contains target把题做少, 即所有新题都往会的方法上面靠.
对撞型
- 2 sum
- partition
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
-
-
- 通过2层循环, 找到每一个pair组合构成的面积. O(n^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.
前向型
- 窗口类: 注意和sliding window不同, sliding window是给定了窗口大小, 找一个符合条件的窗口; 而two pointer的窗口型是指大小不确定, 找一个符合条件的窗口. 所以前者使用heap, deque维护. 后者通过指针来维护.
- 快慢类
-
-
-
-
- 意思如图:
. 关键在于实现. 特别是找到window之后, 怎么advance pointer以及更新状态?
代码如下
public String minWindow(String source, String target) {
if (source == null || source.length() == 0 || target == null || target.length() == 0) return "";
int tarLen = target.length();
HashMap<Character, Integer> dict = new HashMap<>();
for (char c : target.toCharArray())
dict.put(c, dict.containsKey(c) ? dict.get(c) + 1 : 1);
int hitCount = 0;
int l = 0;
int minWindow = source.length() + 1;
int start = 0;
for (int r = 0; r < source.length(); r++) {
char cur = source.charAt(r);
if (!dict.containsKey(cur)) continue;
dict.put(cur, dict.get(cur) - 1);
if (dict.get(cur) >= 0) hitCount++;
while (hitCount == tarLen) {
if (minWindow > r - l + 1) {
start = l;
minWindow = r - l + 1;
}
char prevChar = source.charAt(l);
if (dict.containsKey(prevChar)) {
dict.put(prevChar, dict.get(prevChar) + 1);
if (dict.get(prevChar) > 0) hitCount--;
}
l++;
}
}
if (minWindow > source.length()) return "";
return source.substring(start, start + minWindow);
}
Read full article from
Unit 4 Two Pointers | LeetLintcode
