Membership, frequency and earliest-position questions where repeated searching is the bottleneck.
- have we seen this before
- count occurrences
- find a matching earlier state
The map contains exactly the historical facts needed to answer the current step.
Usually O(n) expected time. Typical auxiliary space: Usually O(n).
JAVA STARTING POINT
A template to adapt, not memorize.
Map<Integer, Integer> firstIndex = new HashMap<>();
for (int index = 0; index < values.length; index++) {
firstIndex.putIfAbsent(values[index], index);
}Common mistakes
- Overwriting the earliest index
- Assuming worst-case O(1) lookup
- Using a map when a small fixed array is clearer
PUBLISHED / 06
Learn in this order.
Available articles always appear before the publishing plan.
Word Pattern II in Java: Backtrack a Two-Way Mapping
Understand bijection, two string indices, candidate substrings, successful short-circuiting and undo with a beginner-friendly Word Pattern II solution.
Read article →Prefix Sum in Java: A Beginner's Guide to Range Sums and Subarray Patterns
Learn prefix sums from scratch with visual examples, Java code, recognition clues, common subarray patterns, and mistakes to avoid.
Read article →Subarray Sum Equals K in Java: From Brute Force to Prefix Sum
Count subarrays with sum K using a prefix sum and frequency map, with beginner-friendly diagrams, a dry run, Java solutions, and common mistakes.
Read article →Next Closest Time in Java: Check the Next Minute, Not the Smallest Clock
Find the next time by bounded minute simulation, correctly handle midnight and unlimited digit reuse, and compare a recursive candidate generator.
Read article →Longest Subarray with Sum K
Use prefix sums and earliest indexes to handle positive and negative values in linear time.
Read article →Palindrome Permutation II in Java: Build Half, Then Mirror
Understand odd frequencies, duplicate-free half permutations, shared state restoration, and a step-through recursion tree with fully commented Java.
Read article →PLANNED PRACTICE
What comes after the published lessons.
- Two sumPlanned, not yet published
- Subarray sum equals kPlanned, not yet published
