Arrays & Strings

Use when you see: “sorted array,” “pair that sums to,” “remove duplicates in-place,” “reverse a string,” “palindrome,” “container with most water.”

Two flavors: opposite direction (left=0, right=end, move inward) for sorted arrays and palindromes. Same direction (slow/fast) for removing duplicates, partitioning, and cycle detection.

Reduces O(n²) brute force to O(n). No extra space needed.

# Python two-pointer template (opposite ends)
def two_pointer(nums, target):
    left, right = 0, len(nums) - 1
    while left < right:
        total = nums[left] + nums[right]
        if total == target: return [left, right]
        elif total < target: left += 1
        else: right -= 1

Use when you see: “contiguous subarray,” “substring of length k,” “maximum sum subarray of size k,” “longest substring without repeating characters,” “minimum window substring.”

Fixed window: expand to size k, then slide by adding the right element and removing the left. Dynamic window: expand right until condition breaks, then shrink left until it holds again.

Turns O(n*k) brute force into O(n). The trick is maintaining your window state efficiently.

# Python dynamic sliding window template
def max_subarray_of_size_k(nums, k):
    window_sum, max_sum = 0, 0
    for right in range(len(nums)):
        window_sum += nums[right]
        if right >= k:
            window_sum -= nums[right - k]  # Shrink left
        if right >= k - 1:
            max_sum = max(max_sum, window_sum)
    return max_sum

Use when you see: “subarray sum equals k,” “range sum query,” “maximum subarray,” “number of subarrays with sum,” “equilibrium index.”

Prefix sum precomputes cumulative sums so any range sum is O(1). Combine with a hash map for “subarray sum equals k.” Kadane's finds the maximum subarray sum in a single pass with O(1) space.

Prefix sums: O(n) precomputation, O(1) per query. Kadane's: O(n) time, O(1) space.

# Python Kadane's algorithm template
def max_subarray(nums):
    best = current = nums[0]
    for num in nums[1:]:
        current = max(num, current + num)  # Extend or restart
        best = max(best, current)
    return best

Use when you see: “find all triplets,” “closest pair,” “merge intervals,” “meeting rooms,” “group anagrams.”

Sorting the array first (O(n log n)) often makes the actual problem trivial. After sorting, duplicates are adjacent, two pointers work, and binary search becomes available.

Total complexity: O(n log n) — dominated by the sort. Often better than O(n²) brute force.

# Python merge intervals template
def merge(intervals):
    intervals.sort(key=lambda x: x[0])
    merged = [intervals[0]]
    for start, end in intervals[1:]:
        if start <= merged[-1][1]:        # Overlap
            merged[-1][1] = max(merged[-1][1], end)
        else:
            merged.append([start, end])
    return merged

• Can you identify the right technique in under 2 minutes? When given an array problem, interviewers watch how quickly you recognize whether it needs two pointers, sliding window, hash map, or sorting. Hesitating for 10 minutes before starting code is a red flag.
• Do you handle edge cases proactively? Before writing code, say out loud: “Let me consider edge cases — empty array, single element, all duplicates, all negative numbers.” This shows maturity.
• Can you articulate the time-space tradeoff? Always mention alternatives: “I could use a hash map for O(n) time but O(n) space, or sort first for O(n log n) time but O(1) extra space. Which would you prefer?”
• Do you start with brute force, then optimize? The best candidates say: “The brute force is O(n^2) nested loops. But I notice the array is sorted, so I can use two pointers for O(n).” This structured thinking is exactly what gets a “Strong Hire.”

Use when you see: “valid palindrome,” “longest palindromic substring,” “palindrome partitioning.”

Technique: Two pointers from both ends moving inward. For longest palindromic substring, use “expand around center” — try each character (and each pair of characters) as the center and expand outward while characters match.

Valid palindrome: O(n). Longest palindromic substring: O(n²) expand-around-center or O(n) with Manacher's.

# Python expand-around-center template
def longest_palindrome(s):
    def expand(l, r):
        while l >= 0 and r < len(s) and s[l] == s[r]:
            l -= 1; r += 1
        return s[l+1:r]
    best = ""
    for i in range(len(s)):
        odd = expand(i, i)        # Odd-length palindrome
        even = expand(i, i + 1)   # Even-length palindrome
        best = max(best, odd, even, key=len)
    return best

Use when you see: “valid anagram,” “group anagrams,” “find all anagrams in a string.”

Technique: Frequency counting with a hash map or 26-element array. Two strings are anagrams if and only if they have the same character frequencies. For “find all anagrams,” use a sliding window with a frequency map.

Valid anagram: O(n). Group anagrams: O(n * k) where k = max string length. Find all anagrams: O(n) sliding window.

Use when you see: “longest substring without repeating characters,” “minimum window substring,” “substring with concatenation of all words.”

Technique: Dynamic sliding window with a hash map tracking character counts. Expand the right pointer to include characters; shrink the left pointer when a constraint is violated. The window state (hash map) updates in O(1) per step.

Longest substring without repeats: O(n). Minimum window substring: O(n).

Use when you see: “reverse words in a string,” “string compression,” “encode/decode strings.”

Technique: Convert the string to a list/array of characters (since strings are immutable), perform in-place modifications, then join back. In Java, use StringBuilder. In Python, collect parts in a list and "".join() at the end. Never concatenate strings in a loop — that is the O(n²) trap.

String building with join: O(n). Loop concatenation: O(n²) — avoid this!