Arrays and Strings: Core Interview Patterns and Execution Strategy

Arrays and strings are not "easy warm-up topics." They are where interviewers evaluate your core execution signals: pattern recognition speed, communication clarity, edge-case discipline, and complexity derivation under time pressure.

Most first-round coding screens start here because arrays/strings expose whether your process is systematic or ad-hoc. A candidate who cannot clearly reason about index boundaries, duplicates, and invariants in this space is unlikely to handle advanced graph or DP rounds.

High-frequency pattern families in this module:

• Hashing and frequency counting (anagrams, first unique, grouping)
• Two pointers (sorted arrays, partitioning, palindrome checks)
• Sliding window (substring/subarray with constraints)
• Prefix sums and difference logic (range and subarray sums)

The strongest candidates do not memorize 100 solutions. They map each prompt to one of these families quickly, explain why that family fits, and drive BOTIC (Brute force -> Optimize -> Template -> Implement -> Check) with explicit time management.

Hashing template (frequency / membership):

def has_duplicate(nums: list[int]) -> bool:
    seen = set()
    for x in nums:
        if x in seen:
            return True
        seen.add(x)
    return False

Two-pointer template (sorted pair search):

def two_sum_sorted(nums: list[int], target: int) -> list[int]:
    l, r = 0, len(nums) - 1
    while l < r:
        s = nums[l] + nums[r]
        if s == target:
            return [l, r]
        if s < target:
            l += 1
        else:
            r -= 1
    return []

Sliding window template (variable size):

def longest_unique_substring(s: str) -> int:
    count = {}
    left = 0
    best = 0
    for right, ch in enumerate(s):
        count[ch] = count.get(ch, 0) + 1
        while count[ch] > 1:
            count[s[left]] -= 1
            left += 1
        best = max(best, right - left + 1)
    return best

Prefix-sum + map template (subarray sum equals k):

def subarray_sum(nums: list[int], k: int) -> int:
    seen = {0: 1}
    prefix = 0
    ans = 0
    for x in nums:
        prefix += x
        ans += seen.get(prefix - k, 0)
        seen[prefix] = seen.get(prefix, 0) + 1
    return ans

Two pointers exploit directional structure in sorted or sortable inputs to eliminate search space deterministically. The key insight: sorted order lets you rule out half the remaining candidates with each pointer move.

Three primary variants:

1. Converging pointers (opposite ends): Start left at 0, right at n-1, move based on comparison to target. Classic use: pair sum in sorted array, container with most water, trapping rain water. Invariant: all pairs outside [left, right] have been eliminated.

2. Fast-slow pointers (same direction): Both start at 0, fast advances every iteration, slow advances conditionally. Classic use: remove duplicates in-place, partition arrays (Dutch National Flag), Floyd's cycle detection. Invariant: [0...slow) is the valid processed region.

3. Sliding-width pointers: Both move right, distance between them varies based on validity check. Overlaps with sliding window for contiguous ranges. Classic use: substring problems where window expands/contracts.

When to use two pointers vs alternatives:

• Use over nested loops when sorted order provides directional elimination (reduces O(n²) → O(n))
• Use over hash map when O(1) space is required or when sorted structure is already given
• Avoid when order is semantically meaningless (e.g., grouping anagrams where letter order doesn't map to value order)

Common implementation mistakes:

• Moving both pointers simultaneously when only one should move based on comparison
• Not handling equal-value runs correctly in duplicate-heavy inputs
• Off-by-one errors when pointers can cross vs when they should stop at left < right
• Forgetting to advance slow pointer in fast-slow variants, causing infinite loops

Sliding window optimizes problems involving contiguous subarrays or substrings with constraints. The pattern avoids redundant recomputation by maintaining state as the window slides.

Two core variants:

1. Fixed-size window: Window width k is given. Slide right by 1, add new element, remove leftmost element. Classic use: maximum sum of k consecutive elements, average of subarrays of size k. Complexity: O(n) with O(k) space for state.

2. Variable-size window: Window expands until constraint is violated, then contracts from left until valid again. Classic use: longest substring without repeating characters, minimum window substring, subarrays with sum ≤ k. Complexity: O(n) amortized because each element is added once and removed at most once.

Key requirements for sliding window validity:

• Monotonic contribution: adding elements to the right must change the metric predictably (sum increases, unique count changes, etc.)
• Contractible restoration: removing from left must restore validity when violated
• Contiguity requirement: problem explicitly asks for substring/subarray, not subsequence

When sliding window FAILS:

• Negative numbers in sum-based constraints break monotonicity → use prefix sums instead
• Non-contiguous selections allowed → use DP or greedy instead
• Window validity depends on global state outside window → need different structure

State management patterns:

• Hash map for frequency counts (char counts, element counts)
• Running sum for aggregate metrics
• Max/min tracking with deque for range queries within window
• Boolean flags for constraint satisfaction

Prefix sums transform range-sum queries from O(n) per query to O(1) after O(n) preprocessing. The core identity: sum(i, j) = prefix[j] - prefix[i-1].

When to use prefix sums:

• Multiple range-sum queries on a static array
• Subarray-sum problems where algebraic transformation is possible
• 2D matrix range queries (2D prefix sums)

Prefix sum + hash map pattern (subarray sum equals k):

Key insight: if prefix[j] - prefix[i] = k, then subarray [i+1...j] has sum k. Rearranging: prefix[j] - k = prefix[i]. So for each position j, check if prefix[j] - k has been seen before.

Why this pattern is powerful:

• Works with negative numbers (sliding window fails here)
• Counts all valid subarrays, not just one
• Handles duplicate prefix sums correctly via frequency map

Implementation subtleties:

• Initialize map with {0: 1} to handle subarrays starting at index 0
• Update answer before incrementing current prefix count (avoids zero-length subarrays)
• Map stores prefix → frequency, not prefix → index (for counting, not finding positions)

Failure modes to avoid:

• Reversing update order causes double-counting when k=0
• Forgetting {0: 1} initialization misses prefix[j]=k cases
• Confusing this with sliding window (prefix+map works with negatives, sliding window doesn't)

Extensions:

• Subarray sum divisible by k: use prefix % k as key
• Count subarrays with sum in range [L, R]: count(≤R) - count(≤L-1)
• 2D matrix subarray sum: combine 1D prefix sums with column compression

The following problems represent the highest-frequency array/string patterns at FAANG. For each, we show: pattern classification, invariant, implementation approach, and edge-case discipline.

Problem selection rationale: these cover all four core patterns (two pointers, sliding window, hashing, prefix sums) and expose the most common failure modes (off-by-one, incorrect complexity reasoning, missing edge cases).

How to use these in practice: before each interview, pick 2-3 from different pattern families and verbalize the full BOTIC walkthrough including complexity proof and edge-case testing. This builds the muscle memory for interview conditions.

Why complexity reasoning matters in interviews:

Interviewers distinguish between candidates who state "O(n) because single loop" vs candidates who derive complexity rigorously. The latter demonstrates analytical depth and transferable problem-solving skills.

Amortized analysis for sliding window:

Common confusion: variable-size sliding window has a for loop with a nested while loop. Looks like O(n²), but is actually O(n). Why?

Accounting argument: Right pointer advances exactly n times (outer loop). Left pointer only moves forward, never resets. Each element is added to window once and removed at most once. Total pointer movements: ≤ 2n. Each movement does O(1) work (hash map update). Therefore total O(n).

What to say in interviews: "Right pointer visits each index once for n total moves. Left pointer also moves only forward and visits each index at most once, so at most n moves total. Combined 2n pointer movements with O(1) work per movement gives O(n) overall."

Prefix sum + map complexity:

Single pass builds prefix sums and populates map. Each insertion and lookup is O(1) average. Total O(n) time. Space is O(n) worst case if all prefix sums are unique.

Hashing complexity subtleties:

Hash map operations are O(1) average case, but O(n) worst case with poor hash function or adversarial input. In interview settings, assume average case unless interviewer asks about worst case. Then mention: "In practice O(1) average with good hash functions; worst-case O(n) with hash collisions, but Python's dict uses robust hashing."

Two-pointer complexity:

Most two-pointer solutions are O(n) because each pointer moves at most n times and doesn't reset. Exception: nested two-pointer variants (e.g., 3Sum with outer loop and inner two-pointer) are O(n²) because of the outer loop multiplier.

Space complexity accounting:

• Input-only structures don't count toward extra space
• Output array often doesn't count (problem specifies)
• Hash maps: count number of unique keys stored (worst case O(n), often O(k) for k unique elements)
• Prefix arrays: O(n) if stored explicitly, O(1) if computed on-the-fly