In the previous chapter, we solve some problems by iterating the array. Typically, we only use one pointer starting from the first element and ending at the last one to do iteration. However, sometimes, we might need to use two pointers at the same time to do the iteration.
Reverse the elements in an array.
The idea is to swap the first element with the end, advance to the next element and swapping repeatedly until it reaches the middle position.
We can use two pointers at the same time to do the iteration:
one starts from the first element and another starts from the last element.
Continue swapping the elements until the two pointers meet each other.
public static void reverse(int[] v, int N) {
int i = 0;
int j = N - 1;
while (i < j) {
swap(v, i, j); // this is a self-defined function
i++;
j--;
}
}
To summarize, one of the typical scenarios to use two-pointer technique is that you want to
Iterate the array from two ends to the middle.
Notice
This technique is often used in a sorted array.
Thoughts:
A[i–] is the same as executing:
A[i];
i--;
Moreover:
–i decrements and then uses the variable.
i– uses and then decrements the variable.
We need to track both the currNum of ones whenever we come across a block of 1s. And each time we take the maximum of the currNum and maxNum so that maxNum is always representing the maximum number of ones.
If we didn’t come across any 1’s, we will set the currNum to 0.
Given an array of positive integers nums and a positive integer target, return the minimal length of a contiguous subarray [numsl, numsl+1, ..., numsr-1, numsr] of which the sum is greater than or equal to target.
If there is no such subarray, return 0 instead.
First, check if the array is empty. If so, return 0;
if (nums.length == 0) return 0;
The algorithm follows:
int minNum = Integer.MAX_VALUE;
int val_sum = 0;
int left = 0;
for (int i = 0; i < nums.length; i++){
val_sum += nums[i];
while (val_sum >= target){
minNum = Math.min(minNum, i-left+1);
val_sum -= nums[left];
left ++;
}
return minNum != Integer.MAX_VALUE ? minNum : 0;
First, what need ed to be approached is to make sure
Proof In this problem, the smart scan way is to set two pointers initialized at both ends of the array. Every time move the smaller value pointer to inner array. Then after the two pointers meet, all possible max cases have been scanned and the max situation is 100% reached somewhere in the scan. Following is a brief prove of this.
Given a1,a2,a3…..an as input array. Lets assume a10 and a20 are the max area situation. We need to prove that a10 can be reached by left pointer and during the time left pointer stays at a10, a20 can be reached by right pointer. That is to say, the core problem is to prove: when left pointer is at a10 and right pointer is at a21, the next move must be right pointer to a20.
Since we are always moving the pointer with the smaller value, i.e. if a10 > a21, we should move pointer at a21 to a20, as we hope. Why a10 >a21? Because if a21>a10, then area of a10 and a20 must be less than area of a10 and a21. Because the area of a10 and a21 is at least height[a10] _ (21-10) while the area of a10 and a20 is at most height[a10] _ (20-10). So there is a contradiction of assumption a10 and a20 has the max area. So, a10 must be greater than a21, then next move a21 has to be move to a20. The max cases must be reached.
s = s.replaceAll("[^a-zA-Z0-9]", "").toLowerCase();
public boolean isPalindrome(String s) {
s = s.replaceAll("[^a-zA-Z0-9]", "").toLowerCase();
int ap = 0, bp = s.length() - 1;
while(ap < bp){
if (s.charAt(ap) != s.charAt(bp)){
return false;
}
ap ++;
bp --;
}
return true;
}
time: O(n^2)
Space: O(1)
class Solution {
public boolean validPalindrome(String s) {
int i = 0, j = s.length() - 1;
while (i < j){
if (s.charAt(i) != s.charAt(j)){
return isPalindrome(s, i+1, j) || isPalindrome(s,i, j-1);
}
i ++;
j --;
}
return true;
}
private boolean isPalindrome(String s, int i, int j){
while (i < j){
if (s.charAt(i) != s.charAt(j)){
return false;
}
i ++;
j --;
}
return true;
}
}
use a fast pointer right to see if character right is in the hash set or not,
public int lengthOfLongestSubstring(String s) {
int left = 0;
int right = 0;
int max = 0;
HashSet<Character> set = new HashSet<>();
while (right < s.length()){
if (! set.contains(s.charAt(right))){
set.add(s.charAt(right));
max = Math.max(max, set.size());
right ++;
}else{
set.remove(s.charAt(left));
left ++;
}
}
return max;
}
class Solution {
public int lengthOfLongestSubstring(String s) {
if (s.length() == 0) return 0;
HashMap<Character, Integer> map = new HashMap<>();
int max = 0;
for(int i = 0, j = 0; i < s.length(); i ++){
if (map.containsKey(s.charAt(i))){
j = Math.max(j,map.get(s.charAt(i))+1);
}
map.put(s.charAt(i),i);
max = Math.max(max,i-j+1);
}
return max;
}
}
public int lengthOfLongestSubstring(String s) {
int result = 0;
int[] cache = new int[256];
for (int i = 0, j = 0; i < s.length(); i++) {
j = (cache[s.charAt(i)] > 0) ? Math.max(j, cache[s.charAt(i)]) : j;
cache[s.charAt(i)] = i + 1;
result = Math.max(result, i - j + 1);
}
return result;
}
Max =0 ;
Left and right pointer
width = 8 - 0 = 8
height = min (1,7)
area = 8*1 = 8
area = (R-L) * min(height[L], height[R])
if left == right, move both left and right foward!
a small optimization tho
always move the smaller height
if we have a smaller height, we don't care about it
so we could have a higher potential.
public int maxArea(int[] height) {
int left = 0;
int right = height.length - 1;
int max = Integer.MIN_VALUE;
while(left < right){
int area = (right - left) * Math.min(height[left], height[right]);
max = Math.max(max, area);
if (height[left] < height[right]){
left ++;
}else if (height[right] < height[left]){
right --;
}else{
left ++;
right --;
}
}
return max;
}