Double pointer¶

What is a double pointer¶

As the name suggests, double pointers are two pointers, but unlike pointers in C or C++, it is an algorithmic idea.

If we iterate an array and output each item of the array, we need a pointer to record the currently traversed item. This process is called a single pointer (index).

for(int i = 0;i <nums.size(); i++) {
  Output(nums[i]);
}

(figure 1)

So the double pointer actually has two such pointers, the most classic is the left and right double pointers in the dichotomy.

int l = 0;
int r = nums.size()-1;

while (l <r) {
    if (certain condition) return appropriate value, generally the midpoint of l and r
    if (certain condition) l++
    if (certain condition) r--
}
// Because l == r, the returned l and r are the same
return l

(figure 2)

After reading this, you find that double pointers are a very broad concept. Just like arrays and linked lists, there are many types of them. For example, dichotomy often uses left and right endpoint double pointers. Sliding windows will use fast and slow pointers and fixed-spacing pointers. Therefore, the double pointer is actually a very comprehensive type, similar to arrays, stacks, etc. But the double pointers we are talking about here often refer to certain types of double pointers, rather than "as long as there are two pointers, it is a double pointer."

Having such an algorithm framework, or algorithmic thinking, has great benefits. It can help you clarify your thoughts. When you encounter a new problem and search in your mind, the word double pointer will flash in your mind. When it flashes, you can follow All the routines of the dual pointer are matched with this question exhaustively. This thinking and problem-solving process is like an algorithm, and I will elaborate on it in the advanced chapter "Search Algorithm".

So what exactly does the double pointer mentioned in our algorithm refer to? Let's take a look at the common question types of double pointers in the algorithm.

What are the common question types?¶

Here I divide it into three types, namely:

1. Fast and slow pointers (two pointers have different steps)
2. Left and right endpoint pointers (the two pointers point to the head and tail respectively, and move to the middle, the step length is uncertain)
3. Fixed-spacing pointer (the two pointers have the same spacing and the same step length)

The above is my own classification, no reference to others. It can be found that my classification standard has covered almost all common situations. Everyone must develop the habit of summarizing the types of questions when doing questions in ordinary times. Of course, this summary can be summed up by others, or it can be summed up independently by yourself. Regardless of the type, a certain amount of digestion and absorption must be carried out to turn them into knowledge that truly belongs to them.

Regardless of the type of double pointer, if only the double pointer part is considered, since the entire array will be traversed at most once, the time complexity depends on the step size. If the step size is a constant such as 1, 2, then the time complexity is O(N), if the step size is related to the data size (such as dichotomy), the time complexity is O(logN). And since we only need up to two pointers regardless of the scale, the space complexity is O(1). Let's take a look at the common routines of dual pointers.

Common routines¶

Fast and slow pointer¶

1. Determine whether the linked list has a ring

Here are two very classic questions for everyone, one is 287 questions and the other is 142 questions. The 287 question is relatively un-intuitive and hard to think of.

• 287. Find the Duplicate Number

• 142. Linked List Cycle II

• Read and write pointers. Typical is remove duplicate elements

Here I recommend a question in my warehouse. I wrote a solution here, compared several similar questions horizontally, and analyzed the essence of this question, so that you can see the essence of the question and recommend reading.

• 80. Remove duplicates in sorted array II

Left and right endpoint pointers¶

1. Binary search.

The binary search will be launched in the special section, so I won’t say much here, just know it first.

1. "Enumerate from big to small" in violent enumeration (pruning)

A typical question is a solution I gave when I participated in the official daily question. You can take a look. This solution can be AC. Similarly, I also gave three methods for this question to help you see this question from multiple latitudes. It is strongly recommended that you do multiple solutions to one question. This will help you a lot to do the problem. In addition to one problem with multiple solutions, there is a big trick to solve multiple problems at the same time. This part will be introduced in the special topic.

find-the-longest-substring-containing-vowels-in-even

1. Ordered array.

Different from the binary search above, the pointer movement of this algorithm is continuous, rather than jumpy. The typical ones are LeetCode's Two Number Sum and N Number Sum series problems.

Fixed pitch pointer¶

1. One pass to find the midpoint of the linked list

2. One Pass to find the kth element from the bottom of the linked list

3. Sliding window with fixed window size

Template (pseudo code)¶

Let's take a look at the algorithm framework of the above three topics. At this time, we don't need to entangle with the specific language, here I directly use the pseudo code, just to prevent you from falling into the details.

When you have mastered the details of this algorithm, you should try several topics. On the one hand, it is to check whether you have really mastered it. On the other hand, it is the "details". "Details" are the greatest enemy of human beings, especially software engineers. After all, we are all Mr. Almost.

1. Fast and slow pointer

l = 0
r = 0
while not traversing
  if certain conditions
    l += 1
  r += 1
return appropriate value

1. Left and right endpoint pointers

l = 0
r = n-1
while l <r
  if found
    return found value
  if certain condition 1
    l += 1
  else if certain conditions 2
    r -= 1
return not found

1. Fixed-pitch pointer

l = 0
r = k
while not traversing
  Custom logic
  l += 1
  r += 1
return appropriate value

Topic recommendation¶

If you almost understand the above things, then you can practice your hands with the following questions. Let's Go!

Left and right endpoint pointers¶

• 16.3 Sum Closest (Medium)
• 1. Subarray Product Less Than K (Medium)
• 1. Squares of a Sorted Array (Easy)
• Dutch National Flag Problem

The following is the dichotomous type

• 1. Search in Rotated Sorted Array (Medium)
• 1. Koko Eating Bananas (Medium)
• 1. Boats to Save People (Medium)

Fast and slow pointer¶

• 1. Remove Duplicates from Sorted Array (Easy)
• 1. Linked List Cycle (Easy)
• 1. Linked List Cycle II (Medium)
• 1. Find the Duplicate Number (Medium)
• 1. Happy Number (Easy)

Fixed pitch pointer¶

• 1456.Maximum Number of Vowels in a Substring of Given Length (Medium)

For sliding windows with a fixed window size, please refer to the sliding window topic of the topic article (not yet released)

Other¶

Sometimes you can't be too mind-set, such as 1446. Consecutive Characters This question does not need double pointers or something. Just parse to each character and keep the max counter to be returned.

Another example: 101. Symmetric Tree