LeetCode Patterns Flashcards: Arrays and Hashing, Frequency Maps, Duplicates

The hash map pattern uses a dictionary or hash table to store values for constant-time lookups, turning brute-force quadratic solutions into linear-time solutions. Use it whenever you need to check if an element exists, count frequencies, or find pairs that satisfy a condition. The classic example is the two-sum problem: instead of checking every pair, store each number in a hash map and check if the complement exists.

The frequency counting pattern builds a hash map where keys are elements and values are their occurrence counts, then uses the counts to answer the question. Walk through the array once to count, then either query the map or iterate it. This solves problems like finding the most frequent element, checking if two strings are anagrams, finding elements that appear more than n divided by k times, or identifying duplicates. Building the frequency map takes O of n time and O of n space.

Insert elements into a hash set as you iterate through the array. Before each insertion, check if the element already exists in the set. If it does, you found a duplicate. This runs in O of n time and O of n space. For the variant "contains duplicate within k distance," use a sliding window hash set of size k, removing elements that fall outside the window. If the problem forbids extra space, sorting the array first in O of n log n time and then checking adjacent elements works. Choose the approach based on constraints: hash set for speed, sorting for space efficiency.

The bucket sort pattern distributes elements into buckets based on value ranges, then processes each bucket separately. It achieves O of n time when the range of values is bounded, bypassing the O of n log n lower bound of comparison-based sorting. Use it when you need the k-th most frequent element: create buckets indexed by frequency, place elements into their frequency bucket, then scan buckets from highest to lowest. It also works for problems with bounded value ranges like sorting colors or ages. Recognize it when frequency or bounded values allow grouping instead of comparing.

The prefix sum pattern precomputes cumulative sums so that any subarray sum can be calculated in constant time. Build an array where each position stores the sum of all elements from the start up to that index. The sum of elements from index i to j equals prefix sum at j minus prefix sum at i minus one. This transforms repeated subarray sum queries from O of n each to O of one each after O of n preprocessing. Use it when the problem asks for subarray sums, range sums, or finding subarrays with a target sum. Combined with a hash map, it solves "subarray sum equals k" in O of n time.

Insert all elements into a hash set for O of one lookups. For each element, check if it is the start of a sequence by verifying that element minus one is not in the set. If it is a start, count consecutive elements by checking element plus one, plus two, and so on until the chain breaks. Track the maximum length found. This runs in O of n time because each element is visited at most twice: once during the outer loop and once during chain extension. The key insight is only starting chains from sequence beginnings, which prevents redundant work and keeps the total operations linear.

The encode and decode pattern converts a list of strings into a single string and back without ambiguity. The standard approach prepends each string with its length followed by a delimiter, so "hello" and "world" become "5#hello5#world." Decoding reads the length number, skips the delimiter, extracts that many characters, and repeats. This handles edge cases like empty strings, strings containing the delimiter, and strings with special characters because the length prefix tells the decoder exactly how many characters to read.

Two strings are anagrams if they contain the same characters with the same frequencies. The optimal approach builds a frequency map for one string, then decrements counts while iterating through the second string. If all counts reach zero, they are anagrams. This runs in O of n time and O of one space since the character set is bounded. Alternatively, if the strings contain only lowercase English letters, use a fixed array of 26 integers instead of a hash map. Sorting both strings and comparing also works in O of n log n time. ---