two pointer approach

Work in Progress

Summary

Two pointer approach

mainly used with linear data structures
keep track of two pointers to various elements

Opposite ends

one pointer at each end
ends when they meet in the middle

java

int left = 0, right = arr.length - 1;

while (left < right) { // determine whether we should overlap in the middle or not
	left++; // increment left pointer based on condition
	
	right--; // decrement right pointer based on condition
}

Sliding window

start the two pointers at the start
update the property when adding a new element/removing the last one
increment each pointer based on properties of the enclosed window

Slow and fast

two pointers move at different rates

java

int slow = 0, fast = 0;

while (fast < arr.length) {
	slow += 1;
	fast += 2; // increment the fast pointer at a higher rate
}

Application

Leetcode: Contains Duplicate II

sliding window

java

if (nums.length < 2)
	return false;

// naive O(n^2) approach
for (int l = 0; l < nums.length - 1; l++) {
	for (int i = 1; i <= k; i++) { // check within the sliding 
		if (l + i >= nums.length)
			break;
		if (nums[l] == nums[l + i])
			return true;
	}
}

return false;

Leetcode: Shortest Unsorted Continuous Subarray

improves upon the naive solution
use the opposite ends approach with greedy max and min

java

int n = nums.length, max = nums[0], min = nums[n - 1], end = -1, beg = 0;
for (int i = 1; i < n; i++) { // O(n)
	if (nums[i] >= max) { // largest index which is less than the max on the left
		max = nums[i];
	} else {
		end = i;
	}

	if (nums[n - 1 - i] <= min) { // smallest index which is more than the min on the right
		min = nums[n - 1 - i];
	} else {
		beg = n - 1 - i;
	}
}

return end - beg + 1;

Leetcode: Ugly Number II

multi-pointer approach

java

int[] a = new int[n];
a[0] = 1;
int x = 0, y = 0, z = 0;
for (int i = 1; i < n; i++) {
	a[i] = Math.min(a[x] * 2, Math.min(a[y] * 3, a[z] * 5));
	if (a[i] == a[x] * 2)
		x++;
	if (a[i] == a[y] * 3)
		y++;
	// else // won't work cause there may be overlaps 
	if (a[i] == a[z] * 5)
		z++;
}
return a[n - 1];

Extra

Problems