Two Pointers

Two Pointers

1. Two Pointers start at two ends

(1) Mostly used in sorted array, typical example is K Sum problem

2. Two Pointers start at the same end

(1) Cycle Detection algorithm (pointers move at different paces)

Idea: Define two pointers: fast pointer and slow pointer. if the cycle exists, find the place they meet in the first time. Then move slow pointer to the place it was in the beginning, and both pointer move at the same pace. The cycle starts at the place where these two pointers meet again(How to prove it?). Example: Find the Duplicate Number

public int findDuplicate(int[] nums) {    
        int fast = 0, slow = 0;

        do {
            fast = nums[nums[fast]];
            slow = nums[slow];
        }
        while (fast != slow);

        // Move slow pointer to the beginning
        slow = 0;

        while (fast != slow) {
            fast = nums[fast];
            slow = nums[slow];
        }
        // Cycle starts at the place where two pointers meet
        return slow;
}

(2) Sliding Window (update start pointer when constraints is violated)

Idea: HashTable + Two Pointers

1. Find the window that contains all character in a substring. Example: Find All Anagrams in a String

// Find All Anagrams in a String
public List<Integer> findAnagrams(String s, String p) {
        List<Integer> res = new ArrayList<>();

        if (s == null || s.length() == 0 || p == null || p.length() == 0) {
            return res;
        }

        int start = 0, end = 0;
        int count = p.length();

        int[] map = new int[256];
        // Put all characters in p into map
        for (char c : p.toCharArray()) {
            map[c]++;
        }

        while (end < s.length()) {
            // When current character is in the map, decrease the count by 1
            if (map[s.charAt(end)] > 0) {
                --count;
            }
            --map[s.charAt(end)];
            ++end;

            // When the size of window is equal to p.length(), update the start pointer
            if (end - start - 1 == p.length()) {
                // if current character pointed by start pointer is in p, increase count by 1
                if (map[s.charAt(start)] >= 0) {
                    ++count;
                }
                ++map[s.charAt(start)];
                ++start;
            }

            // When count is 0, we find an answer
            if (count == 0) {
                res.add(start);
            }
        }
        return res;
}

// Minimum Window Substring
public String minWindow(String s, String t) {
        int[] map = new int[256];
        int start = 0, end = 0, minStart = 0, minEnd = 0;
        int count = t.length();
        int minLen = Integer.MAX_VALUE;

        for (char c : t.toCharArray()) {
            ++map[c];
        }

        while (end < s.length()) {
            if (map[s.charAt(end)] > 0) {
                --count;
            }
            --map[s.charAt(end)];
            ++end;

            while (count == 0) {
                if (end - start < minLen) {
                    minStart = start;
                    minEnd = end;
                    minLen = end - start;
                }

                if (map[s.charAt(start)] >= 0) {
                    ++count;
                }
                ++map[s.charAt(start)];
                ++start;
            }
        }
        return minLen == Integer.MAX_VALUE ? "" : s.substring(minStart, minEnd);
}

1. Window that contains at most K distinct character. Example: Longest Substring with At Most K Distinct Characters

// Longest Substring with At Most K Distinct Characters
public int lengthOfLongestSubstringKDistinct(String s, int k) {
        if (s.length() <= k) {
            return s.length();
        }

        int maxLen = 0;
        int[] map = new int[256];
        int start = 0, end = 0, count = 0;

        while (end < s.length()) {
            if (map[s.charAt(end)] == 0) {
                ++count;
            }
            ++map[s.charAt(end)];
            ++end;

            while (count > k) {
                if (map[s.charAt(start)] == 1) {
                    --count;
                }
                --map[s.charAt(start)];
                ++start;
            }
            maxLen = Math.max(maxLen, end - start);
        }
        return maxLen;
}

// Longest Substring Without Repeating Characters
public int lengthOfLongestSubstring(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }

        int maxLen = 0;
        int[] map = new int[256];
        int start = 0, end = 0, count = 0;

        while (end < s.length()) {
            if (map[s.charAt(end)] > 0) {
                ++count;
            }
            ++map[s.charAt(end)];
            ++end;

            while (count > 0) {
                if (map[s.charAt(start)] > 1) {
                    --count;
                }
                --map[s.charAt(start)];
                ++start;
            }
            maxLen = Math.max(maxLen, end - start);
        }
        return maxLen;
}

3. Questions Category

• Cycle Detection: Find the Duplicate Number

• Sliding window: Longest Substring Without Repeating Characters,