Coding Patterns: Two Pointers

Overview

This technique uses two pointers to iterate input data. Generally, both pointers move in the opposite direction at a constant interval.
DS Involved: Array, Strings, LinkedList.

Two Pointers

How to identify?

The problem involves sorted arrays (or linked list), a set of pair elements, or a triplet or even a subarray.
There is target value to match or duplicates to be removed.

Leet Code problems

151. Reverse Words in a String (MEDIUM)

Intuition

Using two pointers, starting from the end to the beginning of the string to get each word.
Make use of StringBuilder to append each word.

Solution

class Solution {
    public String reverseWords(String s) {
        StringBuilder reversed = new StringBuilder();
        int n = s.length();
        int j = n;
        for (int i = n - 1; i >= 0; i--) {
            if (s.charAt(i) == ' ') {
                j = i;
            } else if (i == 0 || s.charAt(i - 1) == ' ') {
                if (!reversed.length() == 0) {
                    reserved.append(" ");
                }
                resersed.append(s, i, j);
            }
        }
    }
}

Complexity

Time Complexity: O(N) where N is the length of the string.
Space Complexity: O(N).

Follow-up:

If the string data type is mutable in your language, can you solve it in-place with O(1) extra space?

680. Valid Palindrome II (EASY)

Intuition

Using two pointers with opposite directions to check.
We may face 2 options to skip the left or right element (delete at most one element) -> Using recursion to make the code cleaner.

Solution

class Solution {
    public boolean validPalindrome(String s) {
        if (s == null) {
            return false;
        }
        return checkValidPalindrome(s, 0, s.length() - 1, true);
    }

    public boolean checkValidPalindrome(String s, int i, int j, boolean removable) {
        while (i < j) {
            if (s.charAt(i) != s.charAt(j)) {
                if (!removable) {
                    return false;
                }
                return checkValidPalindrome(s, i+1, j, false) || checkValidPalindrome (s, i, j-1, false);
            }
            i++;
            j--;
        }
        return true;
    }
}

Complexity

Time complexity: O(N)
Space complexity: O(1), although we use recursion the recursion tree has the depth of 1.