Frequency maps and two pointers

Two patterns that solve half the easy problems

Interview problems repeat themselves. Behind fresh wording, a small set of patterns does most of the work, and recognizing one turns a blank stare into a plan.

This lesson drills the two highest-frequency patterns for strings and arrays. Each replaces a naive O(n²) nested loop with an O(n) or O(n log n) idea, which is usually the exact improvement the interviewer is waiting to hear named.

The frequency map, which is lesson 7-2's counting idiom, counts occurrences first and then answers questions in a second pass. First non-repeating character, anagram checks, and most problems phrased as "count the ..." fall to it.

An anagram check is one application: two words are anagrams when sorting their characters gives the same result.

char[] a = s1.toCharArray();
char[] b = s2.toCharArray();
Arrays.sort(a);
Arrays.sort(b);
boolean anagram = Arrays.equals(a, b);

toCharArray() explodes a String into a char array, and java.util.Arrays provides sort, equals, and toString for arrays. Those three static helpers appear in nearly every interview solution you will write.

Note that Arrays.equals compares contents while == on two arrays compares references, the same distinction as with Strings.

A frequency map and an anagram check

The first character of swiss appearing exactly once, then a sort-and-compare on two words.

import java.util.Arrays;
import java.util.HashMap;

public class Main {
  public static void main(String[] args) {
    String s = "swiss";
    HashMap<Character, Integer> counts = new HashMap<>();
    for (int i = 0; i < s.length(); i++) {
      char c = s.charAt(i);
      counts.put(c, counts.getOrDefault(c, 0) + 1);
    }
    for (int i = 0; i < s.length(); i++) {
      if (counts.get(s.charAt(i)) == 1) {
        System.out.println("first unique: " + s.charAt(i));
        break;
      }
    }

    char[] a = "listen".toCharArray();
    char[] b = "silent".toCharArray();
    Arrays.sort(a);
    Arrays.sort(b);
    System.out.println("anagram: " + Arrays.equals(a, b));
  }
}

Output

first unique: w
anagram: true

The two-pass structure is the pattern. The first loop counts every character, and only then can the second loop ask about the first one with a count of 1, because that question needs the totals for characters not yet reached.

Both words sort to eilnst, so Arrays.equals reports true. Sorting costs O(n log n), which is why the frequency-map version of the same check is asymptotically better.

Two pointers

Many array and string tasks compare or move elements from both ends: reversing in place, checking a palindrome without building a copy, finding a pair in sorted data.

The two-pointer pattern keeps one index at each end and walks them toward each other:

int left = 0;
int right = arr.length - 1;
while (left < right) {
  // work with arr[left] and arr[right]: swap, compare, and so on
  left++;
  right--;
}

Each element is visited once, so the whole pass is O(n) with no extra array, and those two properties are what the pattern is prized for.

The condition left < right is the standard stop, meaning the pointers have met or crossed and every pair has been handled. A middle element in an odd-length array is left alone, which is correct for both reversing and palindrome checks.

Forgetting to move a pointer inside the loop produces an infinite loop rather than a wrong answer, so it is the first thing to check when a two-pointer solution hangs.

Reversing an array in place

Two pointers, one temporary variable, and no second array.

import java.util.Arrays;

public class Main {
  public static void main(String[] args) {
    int[] nums = {1, 2, 3, 4, 5};
    int left = 0;
    int right = nums.length - 1;
    while (left < right) {
      int tmp = nums[left];
      nums[left] = nums[right];
      nums[right] = tmp;
      left++;
      right--;
    }
    System.out.println(Arrays.toString(nums));
  }
}

Output

[5, 4, 3, 2, 1]

right starts at nums.length - 1, the last valid index from lesson 3-3. The swap needs the temporary, because assigning nums[left] = nums[right] first would destroy the value that still has to be moved.

With five elements the loop runs twice and stops when both pointers reach index 2, leaving the middle 3 in place, which is exactly right. Arrays.toString is what makes an array print readably instead of showing a type and a hash.