Arrays, strings and hashing

Hash maps: trade memory for speed

Two Sum: return indices of two numbers that add to a target.

def two_sum(nums, target):
    seen = {}                      # value -> index
    for i, x in enumerate(nums):
        if target - x in seen:
            return [seen[target - x], i]
        seen[x] = i
    return []

Brute force is O(n²); the hash map makes it O(n) time, O(n) space.

Group anagrams: key each word by its sorted letters (or a 26-count tuple).

from collections import defaultdict
def group_anagrams(words):
    groups = defaultdict(list)
    for w in words:
        groups["".join(sorted(w))].append(w)
    return list(groups.values())

Prefix sums

Precompute running totals so any range sum is O(1): sum(i..j) = prefix[j+1] - prefix[i].

Subarray sum equals k (works with negatives):

def subarray_sum(nums, k):
    count, running = 0, 0
    seen = {0: 1}                  # prefix sum -> how many times
    for x in nums:
        running += x
        count += seen.get(running - k, 0)
        seen[running] = seen.get(running, 0) + 1
    return count

Kadane's algorithm: maximum subarray

def max_subarray(nums):
    best = cur = nums[0]
    for x in nums[1:]:
        cur = max(x, cur + x)      # extend, or start fresh here
        best = max(best, cur)
    return best

Strings

• Strings are immutable in Java and Python: building with += in a loop is O(n²). Use a list and "".join (Python) or StringBuilder (Java).
• Palindrome checks: two pointers from both ends.
• Character counts: an array of 26 for lowercase letters is faster than a map.

Problems to practise

Two Sum, Contains Duplicate, Valid Anagram, Group Anagrams, Top K Frequent Elements, Product of Array Except Self, Longest Consecutive Sequence, Subarray Sum Equals K, Maximum Subarray, Merge Intervals.