Two Pointers

Posted on | In

Two pointers is a powerful weapon of solving problems for data structures such as array and list. A classic example is to find out whether there is a cycle in a linked list.

I will collect some typical problems in this post and provide the solutions using two pointers.

I. Fast Pointer & Slow Pointer

A fast pointer refers to a pointer that moves faster, like taking two steps at a time or taking a few steps ahead, and a slow pointer might take only one step at a time. A fast pointer and a slow pointer are often used to handle problems like a cycle in a linked list.

i. A cycle in a linked list

141. Linked List Cycle: determine if there is a cycle in a linked list.

The idea is to let the slow pointer catch up the fast pointer. This will happen if the linked list contains a cycle.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public boolean hasCycle(ListNode head) {
    if (head == null || head.next == null) {
        return false;
    }

    ListNode slow = head.next;
    ListNode fast = head.next.next;
    while (fast != null && fast.next != null) {
        if (slow == fast) {
            return true;
        }
        slow = slow.next;
        fast = fast.next.next;
    }

    return false;
}

ii. Entry point of a cycle in a linked list

142. Linked List Cycle II: find out the node where the cycle begins in a linked list.

The key to the problem is that if it takes t steps for a slow pointer to walk from the first node to the entry node of the cycle, then the slow pointer can get to entry node starting from the meeting node in t steps, i.e. suppose r is the length of the cycle, m is the distance between the node where the cycle begins and the node where the fast pointer and slow pointer meet, and n is the distance between the first node in the linked list and the start node of the cycle, then we have

1
n + m = r*k s.t. k >= 0

Note that k can be bigger than 1 if n is much larger than r.

How to prove this? Suppose it takes t steps for the slow pointer to meet the fast pointer for the first time, so we have

1
2
3
4
5
6
the slow pointer walks the cycle for k1 times starting from the node they meet
n + m + r*k1 = t
the fast pointer walks the cycle for k2 times starting from the node they meet
n + m + r*k2 = 2*t
and hence
n + m = r*(k2 - 2*k1) = r*k s.t. k >= 0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public ListNode detectCycle(ListNode head) {
    if (head == null || head.next == null) {
        return null;
    }

    ListNode slow = head.next;
    ListNode fast = head.next.next;
    while (fast != null && fast.next != null) {
        if (slow == fast) {
            return findFirstCommonNode(head, slow);
        }
        slow = slow.next;
        fast = fast.next.next;
    }

    return null;
}

private ListNode findFirstCommonNode(ListNode n1, ListNode n2) {
    while (n1 != n2) {
        n1 = n1.next;
        n2 = n2.next;
    }
    return n1;
}

iii. Duplicate number

287. Find the Duplicate Number: find the only one duplicate number in an array containing n + 1 integers where each integer is between 1 and n(inclusive).

The amazing thing about this problem is that it can be converted into the problem of a cycle in a linked list. Here is a thorough explanation on the trick. Simply speaking, the array contains n + 1 integers, so the range of its indices should be between 1 and n, which is exactly the same for each integer, and hence we can use the indices as the link to the next integer.

Here is an example.

index 0 1 2 3 4 5 6 7
number 7 2 3 1 6 2 4 5

linked list with a cycle

The linked list starts from 0, because none of the integers can be 0 which makes sure we can build a linked list from it. Here is an example of why we cannot use other numbers as the start point.

index 0 1 2 3 4 5 6 7
number 7 1 2 3 4 5 6 7 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int findDuplicate(int[] nums) {
    int slow = nums[0];
    int fast = nums[nums[0]];
    while (slow != fast) {
        slow = nums[slow];
        fast = nums[nums[fast]];
    }

    int head = 0;
    while (head != slow) {
        head = nums[head];
        slow = nums[slow];
    }
    return head;
}

Another solution is using binary search.

iv. The Nth node

19. Remove Nth node: remove the Nth node from the end of a linked list.

The solution is to have the fast pointer take n steps ahead of the slow pointer, so when the fast pointer reaches the end of the linst, the slow pointer will be one step before the node being removed.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode fast = head;
    for (int i = 0; i < n; i++) {
        fast = fast.next;
    }

    ListNode slow = null;
    while (fast != null) {
        if (slow == null) {
            slow = head;
        } else {
            slow = slow.next;
        }
        fast = fast.next;
    }

    if (slow == null) {
        head = head.next;
    } else {
        slow.next = slow.next.next;
    }
    return head;
}

v. Lowest Common Ancestor

Find the lowest common ancestor of two nodes in a binary tree, where each node has a link to its parent.

Actually this is a problem about finding the node at which the intersection of two linked lists begins.

  1. Get the length of each list (from the specific node to the root)
  2. Suppose the length of ListA is lenA and the length of ListB is lenB, and lenA is larger than lenB, put the fast pointer in ListA and take lenA - lenB steps ahead, and put the slow pointer in ListB
  3. The LCA is the node at which the fast pointer and slow pointer first meet

II. Sliding Window

The problems in this part can be solved by using a sliding window over an array or list. To represent a sliding window, we can use two pointers, one at the leftmost edge of the window, and the other at the rightmost edge.

i. Substring

76. Minimum Window Substring: given a string S and a String T, find the minimum window in S which contains all the characters in T.

The idea is to have the sliding window move over the array and make sure that it covers all the required characters. The questions are how to move the left pointer and right pointer, and how to know if the window contains all the required characters.

Time complexity is O(t.len + s.len).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
public String minWindow(String s, String t) {
    if (s == null || s.length() == 0 || t == null || t.length() == 0) {
        return "";
    }

    // keep track of the characters in t
    Map<Character, Integer> mark = new HashMap<>();
    for (int i = 0; i < t.length(); i++) {
        char ch = t.charAt(i);
        if (mark.containsKey(ch)) {
            mark.put(ch, mark.get(ch) + 1);
        } else {
            mark.put(ch, 1);
        }
    }

    String min = "";
    int count = t.length();
    int left = 0， right = 0;
    while (left <= right && left < s.length()) {
        // move the right pointer until the window contains all the required characters
        while (count > 0 && right < s.length()) {
            char chR = s.charAt(right);
            Integer cntR = mark.get(chR);
            if (cntR != null) {
                if (cntR > 0) {
                    count--;
                }
                mark.put(chR, cntR - 1);
            }
            right++;
        }

        if (count > 0) {
            break;
        }

        if (min.length() == 0 || min.length() > right - left) {
            min = s.substring(left, right);
        }

        // move the left pointer to minimize the window
        char chL = s.charAt(left);
        Integer cntL = mark.get(chL);
        if (cntL != null) {
            if (cntL >= 0) {
                count++;
            }
            mark.put(chL, cntL + 1);
        }
        left++;
    }

    return min;
}

ii. Subarray

209. Minimum Size Subarray Sum: given an array of n positive integers and a positive inter s, find the minimal length of a contiguous subarray of which the sum >= s.

For this problem, the sliding window is a contiguous subarray of which the sum is larger than s.

  • Move the right pointer, until the sum of the window is larger than s
  • Compare the window to the minimum size subarray
  • Move the left pointer one step at a time

Time complexity: O(n).

iii. Substring

567. Permutation in String: given two strings s1 and s2, check if s2 contains the permutation of s1.

It is similar to Problem i, the difference is that the sliding window can only contain characters of s2. Note that always move the right pointer first and then adjust the left pointer.

Time complexity: O(s1.len + s2.len * 2).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
public boolean checkInclusion(String s1, String s2) {
    int[] letters = new int[26];
    for (int i = 0; i < s1.length(); i++) {
        int k = s1.charAt(i) - 'a';
        letters[k]++;
    }
    for (int i = 0; i < letters.length; i++) {
        if (letters[i] == 0) {
            letters[i] = -1;
        }
    }

    int count = s1.length();
    int left = 0;
    int right = 0;
    while (right < s2.length()) {
        int i = s2.charAt(right) - 'a';
        if (letters[i] > 0) {
            letters[i]--;
            count--;
            right++;
            continue;
        }

        if (count == 0) {
            return true;
        }

        if (letters[i] < 0) {
            while (left <= right) {
                int j = s2.charAt(left) - 'a';
                left++;
                if (letters[j] >= 0) {
                    letters[j]++;
                    count++;
                }
            }
            right++;
        } else {
            while (left <= right) {
                int j = s2.charAt(left) - 'a';
                left++;
                if (letters[j] >= 0) {
                    letters[j]++;
                    count++;
                    break;
                }
            }
        }
    }

    return (count == 0);
}

iv. Substring

30. Substring with Concatenation of All Words: find all starting indices of substring(s) in s that is a concatenation of each word in words exactly once and without any intervening characters.

It is similar to Problem iii, but instead of finding substrings that contain the required characters, it needs to find the substrings that contain the required words, so we need a way to verify if an index is a start index of a word. To solve this issue, we can build an index for each. Note that all the words are of the same length, so no word can be a prefix of other words. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> substringIndices = new ArrayList<>();
        if (s == null || s.length() == 0 || words == null || words.length == 0) {
            return substringIndices;
        }

        Map<String, Integer> wordCounter = countWords(words);
        String[] wordIndices = getWordIndex(s, wordCounter.keySet());

        int count = words.length;
        int len = words[0].length();
        int left = 0;
        int right = 0;
        while (left <= right && right < s.length()) {
            String word = wordIndices[right];
            if (word != null) {
                Integer cnt = wordCounter.get(word);
                if (cnt > 0) {
                    wordCounter.put(word, wordCounter.get(word) - 1);
                    count--;
                    right += len;
                    continue;
                }
            }

            if (count == 0) {
                substringIndices.add(left);
            }

            for (int i = left; i < right; i += len) {
                word = wordIndices[i];
                if (word != null) {
                    wordCounter.put(word, wordCounter.get(word) + 1);
                    count++;
                }
            }
            left++;
            right = left;
        }
        if (count == 0) {
            substringIndices.add(left);
        }

        return substringIndices;
    }

    private String[] getWordIndex(String s, Set<String> words) {
        String[] indices = new String[s.length()];
        for (int i = 0; i < indices.length; i++) {
            indices[i] = null;
        }
        for (String w : words) {
            int j = 0;
            while (j < s.length()) {
                j = s.indexOf(w, j);
                if (j == -1) {
                    break;
                }
                indices[j] = w;
                j++;
            }
        }
        return indices;
    }

    private Map<String, Integer> countWords(String[] words) {
        Map<String, Integer> counter = new HashMap<>();
        for (int i = 0; i < words.length; i++) {
            Integer cnt = counter.get(words[i]);
            if (cnt == null) {
                counter.put(words[i], 1);
            } else {
                counter.put(words[i], cnt + 1);
            }
        }
        return counter;
    }

Time complexity for this solution is: O(words.len + s.len * s.len).

v. Substring

3. Longest Substring Without Repeating Characters: given a string, find the length of the longest substring without repeating characters.

The idea is that the sliding window should contain non-repeating characters, and the rest is the same as above.

III. Others

i. Two sum

167. Two Sum: given an array of integers which are in ascending order, return indicies of the numbers such that they add up to a specific target.

The idea is to have the left pointer move from the leftmost side and have the right pointer move from the rightmost side. Because the array is sorted, it is easy to decide whether to move the left pointer or the right pointer by comparing the sum to the target.

Time complexity: O(nums.len).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public int[] twoSum(int[] nums, int target) {
    if (nums == null || nums.length == 0) {
        return null;
    }

    int[] two = new int[2];
    int left = 0;
    int right = nums.length - 1;
    while (left < right) {
        int sum = nums[left] + nums[right];
        if (sum == target) {
            two[0] = left;
            two[1] = right;
            break;
        }
        if (sum < target) {
            left++;
        } else {
            right--;
        }
    }

    return two;
}