Two Pointers - How to Succeed in Algorithms

How to Succeed in Algorithms Interview Series

---

Types of Two/Multiple Pointers

• One array, head and tail pointers
  • maintain interval, expand head when still meets criteria, shrink tail when not
• Slow and fast pointers
• 一个数组, 从两边向中间移动(对撞型)
• 一个数组, 同时向前移动(前向型)
• 两个数组(并行型)
• Two arrays, both from start or end
  • when element’s value/state is related with afterwards elements
    • use stack
    • or maybe traverse from end

When to use Two/Multiple Pointers

• range related

How

• pre-sort the array
• usually related with greedy
  • LeetCode 881 - Boats to Save People

Multiple arrays (merge)

• LeetCode 826 - Most Profit Assigning Work

public int maxProfitAssignment(int[] difficulty, int[] profit, int[] worker) {
    List<Pair<Integer, Integer>> jobs = new ArrayList<>();
    int N = profit.length, res = 0, i = 0, maxp = 0;
    for (int j = 0; j < N; ++j) jobs.add(new Pair<Integer, Integer>(difficulty[j], profit[j]));
    Collections.sort(jobs, Comparator.comparing(Pair::getKey));
    Arrays.sort(worker);
    for (int ability : worker) {
        while (i < N && ability >= jobs.get(i).getKey())
            maxp = Math.max(jobs.get(i++).getValue(), maxp);
        res += maxp;
    }
    return res;
}

• LeetCode 44 - Wildcard Matching
  • dp: O(m+n)
  • two pointers: O(m+n)

Two/Multiple same direction pointers in one array(尺取法)

• LeetCode 845 - Longest Mountain in Array
  • up + down array
  • two pointers
• LeetCode 844 - Backspace String Compare
• LeetCode 763 - Partition Labels

// start and end of the current window
int left = 0, right = 0;
// current pointer
for (int i = 0; i < S.size(); ++ i) {
    right = max(right, last[S.at(i)]); // maximum index of the current window
    // reach the end of current window
    if (i == right) {
        vResult.push_back(right - left + 1); // size of the current window
        left = i + 1; // move to start of the next window
    }
}

• LeetCode 259 - 3Sum Smaller
  • 3 pointers: i, int lo = i + 1, hi = nums.length - 1;
• [LeetCode 923 - 3Sum With Multiplicity]
  • 3 pointers
  • Map stores pair sum, build map and compute at same time
• LeetCode 838 - Push Dominoes
  • the state of current element, only depend on the shortest distance to ‘L’ and ‘R’.
  • Propose assumption and verify it
• LeetCode 55 - Jump Game
  • track maxReach: we don’t care what positions a[i] can reach, only the maxReach
• LeetCode 45 - Jump Game II: find the minimum number of jumps
  • two pointers to maintain a cover range

Slow and fast pointers

• LeetCode 141 - Linked List Cycle

  • 2(a+b) = a+b+c+b, c = a

  

• String Deduplicate - Google

• LeetCode 287 - Find the Duplicate Number

  • bisection
  • find loop in the linkedlistindex to value mapping

  

  public int findDuplicate(int[] nums) {
      int slow = 0, fast = 0;
      do{
          slow = nums[slow];
          fast = nums[nums[fast]];
      }while(slow != fast);
      slow = 0;
      while(slow != fast){
          slow = nums[slow];
          fast = nums[fast];
      }
      return slow;
  }

Forward and backward pointers

• GEEK - Find Maximum value of abs(i – j) * min(arr[i], arr[j]) in an array arr[]
• LeetCode 42 - Trapping Rain Water
  • If there are two bars higher than this bar on two sides, then we can safely add the min(leftMax, rightMax) - height. We only need to keep one pointer on each side and moves the pointer with lower height each time

  public int trap(int[] height) {
  int left = 0;
  int right = height.length - 1;
  int leftMax = 0;
  int rightMax = 0;
  int volume = 0;
  while (left < right) {
    if (height[left] <= height[right]) {
      if (height[left] >= leftMax) {
        leftMax = height[left];
      } else {
        volume += leftMax - height[left];
      }
      ++left;
    } else {
      if (height[right] >= rightMax) {
        rightMax = height[right];
      } else {
        volume += rightMax - height[right];
      }
      --right;
    }
  }
  
  return volume;
  }

• LeetCode 67 - Minimum Window Substring
  • expand (end pointer) the window until it meets the criteria
  • shrink (start pointer) to make it smallest
• LeetCode 340 - Longest Substring with At Most K Distinct Characters
• LeetCode 360 - Sort Transformed Array
• LeetCode 632 - Smallest Range

Sliding Window

When to use

• window of size k
• Shortest/longest Subarray with xxx

How

• expand (end pointer) the window until it meets the criteria
• reset value when it violates
• shrink (start pointer) to make it smallest
• maintain states when expand and shrink: put in a map/set
• use together with queue or monotone queue

Implementation

• ans += right - left + 1;

use together with queue or monotone queue

• LeetCode 239 - Sliding Window Maximum
• LeetCode 862 - Shortest Subarray with Sum at Least K

public int shortestSubarray(int[] A, int K) {
    int N = A.length;
    long[] P = new long[N+1];
    for (int i = 0; i < N; ++i)
        P[i+1] = P[i] + (long) A[i];

    // Want smallest y-x with P[y] - P[x] >= K
    int ans = N+1; // N+1 is impossible
    Deque<Integer> monoq = new LinkedList(); //opt(y) candidates, as indices of P

    for (int y = 0; y < P.length; ++y) {
        // Want opt(y) = largest x with P[x] <= P[y] - K;
        while (!monoq.isEmpty() && P[y] <= P[monoq.getLast()])
            monoq.removeLast();
        while (!monoq.isEmpty() && P[y] >= P[monoq.getFirst()] + K)
            ans = Math.min(ans, y - monoq.removeFirst());

        monoq.addLast(y);
    }

    return ans < N+1 ? ans : -1;
}

• LeetCode 3 - Longest Substring Without Repeating Characters

public int lengthOfLongestSubstring(String s) {
     if (s.length()==0) return 0;
     HashMap<Character, Integer> map = new HashMap<Character, Integer>();
     int max=0;
     for (int i=0, j=0; i<s.length(); ++i){
         if (map.containsKey(s.charAt(i))){
             j = Math.max(j,map.get(s.charAt(i))+1);
         }
         map.put(s.charAt(i),i);
         max = Math.max(max,i-j+1);
     }
     return max;
 }

• Find zeroes to be flipped so that number of consecutive 1’s is maximized
  • follow up

  public int lengthOfLongestSubstringKDistinct(String str, int k) {
    if (str == null || str.isEmpty() || k == 0) {
        return 0;
    }
    TreeMap<Integer, Character> lastOccurrence = new TreeMap<>();
    Map<Character, Integer> inWindow = new HashMap<>();
    int j = 0;
    int max = 1;
    for (int i = 0; i < str.length(); i++) {
        char in = str.charAt(i);
        while (inWindow.size() == k && !inWindow.containsKey(in)) {
            int first = lastOccurrence.firstKey();
            char out = lastOccurrence.get(first);
            inWindow.remove(out);
            lastOccurrence.remove(first);
            j = first + 1;
        }
        //update or add in's position in both maps
        if (inWindow.containsKey(in)) {
            lastOccurrence.remove(inWindow.get(in));
        }
        inWindow.put(in, i);
        lastOccurrence.put(i, in);
        max = Math.max(max, i - j + 1);
    }
    return max;
  }

• LeetCode 340 - Longest Substring with At Most K Distinct Characters
• Sum of minimum and maximum elements of all subarrays of size k
  • remove numbers out of range k
  • remove numbers in k range as they are useless
• LeetCode 424 - Longest Repeating Character Replacement
• HARD: LeetCode 30 - Substring with Concatenation of All Words
  • for (int i = 0; i < L[0].length(); i++)
• leetCode 475 - Heaters
  • presort + two pointers
  • TreeSet
  • binary search