Leetcode-Two Pointers
Reference: Link
167. Two Sum II - Input array is sorted (Easy)
I think this is the simplest problem which can be solved by two pointers, so I don’t explain how to solve this problem. Time complexity is O(n). Space complexity is O(1). Here is the link.
633. Sum of Square Numbers (Easy)
This problem is easy too. But you need to pay attention to the initial value of two pointers. One is 0, the other is Math.sqrt(target). If c is a square number, we need to return true. so one of a or b has to be 0 and the other is Math.sqrt(c). Time complexity is O(Math.sqrt(target)). Space complexity is O(1). Here is the link.
345. Reverse Vowels of a String (Easy)
If you know a problem can be solved by two pointers, the solution will be very intuitive. This problem is easy too. You just need to start from the left and right until you find two vowels. Time complexity is O(n). Space complexity is O(n). Here is the link.
680. Valid Palindrome II (Easy)
This problem is a little bit more hard than first three problems. You should use two pointers and greedy to solve this problem. If you find somewhere cannot build a palindrome, you should check (left+1,right) and (left,right-1). If at least one of these two substrings is a palindrome, then the whole string could be a palindrome. Time complexity is O(n). Space complexity is O(1). Here is the link.
88. Merge Sorted Array (Easy)
This problem is very easy if you create a new array as your answer. But the problem requires us to use the origin array as the answer. Therefore, we need to be careful about the initial value of two pointers. In this problem, the initial value of two pointers should be right of these two arrays. You cannot start from the left. You will override nums1 and lose data if you start from the left. Time complexity is O(m+n). Space complexity is O(1). Here is the link.
141. Linked List Cycle (Easy)
Well, I didn’t find I could use two pointers to solve this problem when I first tried to solve it. The leetcode gives a details explanation.
The space complexity can be reduced to O(1) by considering two pointers at different speed - a slow pointer and a fast pointer. The slow pointer moves one step at a time while the fast pointer moves two steps at a time.
If there is no cycle in the list, the fast pointer will eventually reach the end and we can return false in this case.
Now consider a cyclic list and imagine the slow and fast pointers are two runners racing around a circle track. The fast runner will eventually meet the slow runner. Why? Consider this case (we name it case A) - The fast runner is just one step behind the slow runner. In the next iteration, they both increment one and two steps respectively and meet each other.
How about other cases? For example, we have not considered cases where the fast runner is two or three steps behind the slow runner yet. This is simple, because in the next or next’s next iteration, this case will be reduced to case A mentioned above.
Time complexity O(n). Space complexity O(1). Here is the link.
524. Longest Word in Dictionary through Deleting (Medium)
This is the only medium problem. Through this problem, we can use two pointers to find the substring of a string. For this problem, you only need to consider about strings which are longer than your current answer. What’s more,
str1.compareTo(str2)
can be use to find the smaller lexicographical string. if the return value is smaller than 0, lexicographical order is str1<str2.
Time complexity : O(n⋅x). One iteration over all strings is required. Here n refers to the number of strings in list d and x refers to average string length.
Space complexity : O(x). max_str variable is used.
Here is the link.
75. Sort Colors (Medium)
We need to two pointers. But these two pointers don’t move until we need to swap an element with these two pointers. A pointer starts from left. The other starts from right. If we find 0 at the k, we
swap(nums[k],nums[left++]).
If we find 2,
we swap(nums[k--],nums[right--]).
Be careful about the value of k. k cannot be larger than right, because right part is already sorted.
Time complexity is O(n). Space complexity is O(1).
public void sortColors(int[] nums) {
int red = 0;
int blue = nums.length-1;
for(int i =0;i<=blue;i++){
if(nums[i]==0){
int temp = nums[i];
nums[i] = nums[red];
nums[red] = temp;
red++;
}
else if(nums[i]==2){
int temp = nums[i];
nums[i] = nums[blue];
nums[blue] = temp;
i--;
blue--;
}
}
}
392. Is Subsequence (Easy)
You need two pointers for these two strings. If you find the characters are same, move the pointer of s.
Time complexity is O(n). n is the length of string t. Space complexity is O(1). Here is the link.
public boolean isSubsequence(String s, String t) {
int index =0;
if(s.length()==0)return true;
for(int j =0;j<t.length();j++){
if(t.charAt(j)==s.charAt(index)){
index++;
if(index == s.length())return true;
}
}
return false;
}
Follow up:
I used javascript to solve the follow up question.
If we use the first solution to solve the follow up question, the time complexity is O(nk). k is the number of string s. It’s not time efficient.
We can use binary search to solve this problem. Think about an example. Now we have a string s and a string t. For each character in string s, we need to find the same character in string t and the index should be larger than the previous one (the index of the previous matched character). That’s why I use binary search. We are given an ascending order list and we need to find the first value which is larger than the target.
- At first, you need to build a list of arrays for 26 letters.
- Iterate string t. For each character in string t, push the index of the character to corresponding list in step 1.
- Iterate string s. Find the corresponding list for each character. If the corresponding list is empty, return false.
- Use binary search for the corresponding list. The corresponding list is consist of indices of the same character in string t. We need to find the first index which is larger than previous index.(The initial value of previous index is 0)
- If the result is equal to the size of list which means the previous index is larger than all indices in the list. This also means we can’t find corresponding character after previous index in string t. We return false. Otherwise, we set the previous index to the result plus 1 and iterate next character of string s.
let’s say t’s length is N, the binary search is O(logN), suppose the average length of the incoming strings is M, and the number of incoming strings is K, the total runtime would be O(MKlogN + N). Space complexity is O(N).
var isSubsequence = function (s, t) {
let dict = [];
for (let i = 0; i < 26; i++) {
dict.push([]);
}
for (let i = 0; i < t.length; i++) {
dict[t.charCodeAt(i) - 97].push(i);
}
let prev = 0;
for (let i = 0; i < s.length; i++) {
if(dict[s.charCodeAt(i) - 97].length===0) return false;
let index = binarySearch(dict[s.charCodeAt(i) - 97], prev);
if(index === dict[s.charCodeAt(i) - 97].length) return false;
prev = dict[s.charCodeAt(i) - 97][index]+1;
// console.log(prev)
}
return true;
};
var binarySearch = function (list, target) {
let left = 0;
let right = list.length - 1;
while (left <= right) {
let mid = parseInt(left + (right - left) / 2);
if (list[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return left;
};
Summary
If you find you can use two pointers to solve a problem. this problem will be very easy. Two pointers are used to iterate array, list and string. You can use two pointers to find the target value in array and substring of the string.
In this kind of problem, you need to be careful about the initial value of two pointers. There are some situations:
- One pointer starts from the left of array/string, the other starts from the right/end of the array/string.
- Two pointers starts from the left/right of two arrays/strings.
- One pointer is faster than the other, like leetocde 141.
You also need to be careful about how to move these two pointers. This depends on problem requirement.