The Power of Two Pointer
-- OverView
The are lots of algorithm problems that can be solved by the two (slow & fast) pointer technique. What's more, we could use this technique to in place deal with many String manipulation problem in O(n) time, which requires a programmer have solid coding skills and deep impression about the physical meaning of two pointer in each problem.
-- Examples
1. First, Let's look at a pretty basic problem: The partition method we used when we perform quick sort. There are lots of different way to write the code for partition, but with this two pointer technique, I was just impressed. How clear the code will be !
By choosing a random pivot value, we partition the given array, from left to right, that all the value that smaller than pivot value be in the left of array, and or the value that is bigger or equal to pivot value sit right hand side of pivot. Finally we return the pivot index value as out put.
private int partition(int[] a, int left, int right){
}
2.1: The First Occurrence
Given a target integer T and an integer array A sorted in ascending order, find the index of the first occurrence of T in A or return -1 if there is no such index.
Assumptions
- There can be duplicate elements in the array.
Examples
- A = {1, 2, 3}, T = 2, return 1
- A = {1, 2, 3}, T = 4, return -1
- A = {1, 2, 2, 2, 3}, T = 2, return 1
Corner Cases
- What if A is null or A of zero length? We should return -1 in this case.
2.2. The Last Occurrence
Given a target integer T and an integer array A sorted in ascending order, find the index of the last occurrence of T in A or return -1 if there is no such index.
Assumptions
- There can be duplicate elements in the array.
Examples
- A = {1, 2, 3}, T = 2, return 1
- A = {1, 2, 3}, T = 4, return -1
- A = {1, 2, 2, 2, 3}, T = 2, return 3
Corner Cases
- What if A is null or A is array of zero length? We should return -1 in this case.
Note: The only difference of 2.1 and 2.2, is the 2 place I made comment in the code above.
2.3.The Closest Occurrence
Given a target integer T and an integer array A sorted in ascending order, find the index i in A such that A[i] is closest to T.
Assumptions
- There can be duplicate elements in the array, and we can return any of the indices with same value.
Examples
- A = {1, 2, 3}, T = 2, return 1
- A = {1, 4, 6}, T = 3, return 1
- A = {1, 4, 6}, T = 5, return 1 or 2
- A = {1, 3, 3, 4}, T = 2, return 0 or 1 or 2
Corner Cases
- What if A is null or A is of zero length? We should return -1 in this case.
3. Remove Extra White Space
Given a string, remove all leading/trailing/duplicated empty spaces.
Assumptions:
- The given string is not null.
Examples:
- “ a” --> “a”
- “ I love DP ” --> “I love DP”
Note: People may find various of ways to solve this problem, but the following solution that used slow and fast pointer is the most elegant one that I found so far.
In this example the i is the fast pointer and the slow value is the slow pointer, the physical meaning is: the result are at left side of slow pointer
4. Remove Adjacent Repeated Characters
4.1:
Remove adjacent, repeated characters in a given string, leaving only one character for each group of such characters.
Assumptions
- Try to do it in place.
Examples
- “aaaabbbc” is transferred to “abc”
Corner Cases
- If the given string is null, we do not need to do anything.
Note: We will still use two pinter here, "end" pointer here is the slow pointer and it also will act like the top of a "Virtual Stack", where when we move the i, the fast pointer here, we constantly look at the top of our stack, see if there is a duplication happen.
4.2:
Repeatedly remove all adjacent, repeated characters in a given string from left to right.
No adjacent characters should be identified in the final string.
Examples
- "abbbaaccz" → "aaaccz" → "ccz" → "z"
- "aabccdc" → "bccdc" → "bdc"
Note: I comment the only difference between 4.1 and 4.2, For 4.2, if there is a duplication we do not preserve any of them, so we pop off from our stack whenever we find there is adjacent duplication.
5. String Abbreviation Matching
Word “book” can be abbreviated to 4, b3, b2k, etc. Given a string and an abbreviation, return if the string matches the abbreviation.
Assumptions:
- The original string only contains alphabetic characters.
- Both input and pattern are not null.
Examples:
- pattern “s11d” matches input “sophisticated” since “11” matches eleven chars “ophisticate”.
Note: If someone still remember we discussed Wild card matching before, then you will find that it is a easy version of wild card matching and also could use recursive method to solve it ( as we did in Regular Expression matching)
Basically, we will keep one pointer for input , and the other for pattern. and if they will reach end at the same time, we had a successful matching !
-- End:
Actually, if you would like to add sliding window algorithm into two pointer technique, which is also make sense. I hope you enjoy this basic but very powerful tool that we could use. Thanks.
Happy Coding -_-
Ye Jiang
No comments:
Post a Comment