Algorithm - Double pointers

2020-10-17

Word count: 1.1k | Reading time≈ 7 min

¶Introduction

The so-called double pointer algorithm refers to the process of traversal, instead of the normal use of a single pointer for cyclic access, two pointers in the same or opposite direction are used for scanning, so as to achieve the corresponding purpose. The double pointer method makes full use of the array ordering feature, which can simplify some operations and reduce time complexity in some cases.

It’s worthy to point out that, no matter how fancy the algorithm is, it’s just a variant of some well-known and easy-sought algorithm at the bottom. In this case, double pointer, which is O(n) in time complexity, is a special case to brutal force search. e.g. A naive brutal force algorithm can be written as:

```
for (int i = 0; i < N; i++)
  for (int j = 0; j < N; j++)
    if (condition)
      continue

It’s O(n^2) at first glance, but it can essentially be O(nlogn) or O(n) depending on how condition is designed and met. So double pointers algorithm can effectively kill tons of solution space to land on a O(n) time complexity.

This article summarizes several applications of the double pointer algorithm in array-like topics.

¶Colliding Pointers

The first kind of double pointer algorithms are AKA sliding windows. Normally there will be two pointers from both end of an array and the search scope will narrow down. The data is typically sorted. A valid question to ask is, how to ensure that the sliding window covers all feasible solutions? Let’s dive in.
*167-Two sum(sorted)
*11-Container With Most Water

167-Two sum(sorted)
Given an array of integers numbers that is already *sorted in ascending order*, find two numbers such that they add up to a specific target number.

Return the indices of the two numbers (1-indexed) as an integer array answer of size 2, where 1 <= answer[0] < answer[1] <= numbers.length.

Attack

Set two pointers i and j at begin and last element. The branch pruning (or solution space compression) strategy is, if answer[i]+answer[j]<target, answer[i] can be excluded from searching because answer[i]+answer[k]<targer,k<j.

11-Container With Most Water
Given n non-negative integers a1, a2, ..., an , where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of the line i is at (i, ai) and (i, 0). Find two lines, which, together with the x-axis forms a container, such that the container contains the most water.

Attack

Pretty similar to previous one: if min(ai,aj)*(aj-ai+1)<current_max, min(ai,aj) can be excluded from searching because cureent_max can never be attained.

¶Chasing Pointers

Chasing pointers is a pair of pointes starting one end and the left one chaseing the right. It’s a variant or representation of sliding window.
*3-Longest Substring Without Repeating Characters
*1590-Delete Sublist to Make Sum Divisible By K
*713-Subarray Product Less Than K

3-Longest Substring Without Repeating Characters

Given a string s, find the length of the longest substring without repeating characters.

Attack

If s[start]...s[end] satisfies, keep pushing right boundary, otherwise, s[end] is a repeat of some char with the above range. Find that first occurance, say index j, then start from j+1. Here we prove by contradiction why there is no missing feasible solution.
Assume candidate s[i]...s[j] is a valid substring and missed. Since the right boundary j increments by 1, the only possibility to miss is to skip over i. Assume m < i < k < j, at one point, m is fast forwarded to k. It is obvious that s[m]...s[j] is another valid substring and also longer than candidate. No need to consider the candidate and just let it go!
Similar problems:

1. Substring with Concatenation of All Words
1. Max Consecutive Ones
1. Minimum Size Subarray Sum

1590-Delete Sublist to Make Sum Divisible By K
You are given a list of positive integers nums and a positive integer k. Return the length of the shortest sublist (can be empty sublist ) you can delete such that the resulting list’s sum is divisible by k. You cannot delete the entire list. If it’s not possible, return -1.

Attack

You need the help from hashtable to record the mods of prefix sums. The main point of this problem is: remainderSum = totalSum - prefixsum[j] + prefixsum[i], i < j and it has to meet the requirement that mod(remainderSum,k)===0. With the pointer increments, mod(prefimsum[i],k) can be recoreded and updated by a hastable. Say prefixsum[m]-prefixsum[n], m > n, is a multiple of k , entry prefixsum[n] will be flushed out by prefixsum[m] as they both meet the requirement. Looks though only once pointer is used, the hashtable acts as a pointer.

713-Subarray Product Less Than K
Your are given an array of positive integers nums.

Count and print the number of (contiguous) subarrays where the product of all the elements in the subarray is less than k.

Attack
The solution space can be viewed as a union of A_j, 0<j<n, where A_j is the set of solutions ended with j(included). [i...j] being a solution implies [i+1...j],...,[j-1...j] are all solutions. With these, we can increment right boundary j and find the left boundary i under a certain j. Moving to next j, the last left boundary i can be reused.

¶Fast and Slow Ponters

The fast and slow pointers are also double pointers, but the two pointers traverse the array from the same side, defining the two pointers as fast and slow respectively, and the two pointers move with different strategies until the values of the two pointers are equal (or other special conditions), e.g. fast grows by two at a time and slow grows by one at a time.
*26-Remove Duplicates from Sorted Array

26-Remove Duplicates from Sorted Array
Given a sorted array nums, remove the duplicates in-place such that each element appears only once and returns the new length.

Attack
After the array is sorted, we can place two pointers i and j, where i is the slow pointer and j is the fast pointer. As soon as nums[i] = nums[j], we increment j to skip duplicate items. when encountered nums[j]!=nums[i], copy its nums[j] to nums[i+1]. Then increment i.