Common Array and String Problems

Analogy categoryAnalogies

Introduction

Most array and string interview questions reduce to a handful of reusable patterns. Two of the most important are the two-pointer technique, which uses two indices moving through a sequence to avoid nested loops, and the sliding window technique, which maintains a contiguous range that expands and contracts to track a running property like sum or count.

🏏

Cricket analogy: The two-pointer technique is like a scorer tracking both the striker's and non-striker's positions simultaneously to spot a quick single, while the sliding window is like tracking a bowler's rolling economy rate over the last 4 overs.

Explanation

The two-pointer pattern typically places one pointer at each end of a sorted array (or string) and moves them toward each other based on a comparison, turning an O(n^2) brute-force search into O(n). It is ideal for problems like finding a pair that sums to a target in a sorted array, reversing an array in place, or checking palindromes. The sliding window pattern maintains a window defined by a left and right index over a contiguous subarray or substring; the right pointer expands the window to include new elements, and the left pointer contracts it when a constraint is violated, avoiding recomputation from scratch for every window and reducing an O(n^2) or O(n*k) brute force to O(n). It is ideal for problems like maximum sum subarray of fixed size k, longest substring without repeating characters, or smallest subarray with a sum at least a target.

🏏

Cricket analogy: Finding a pair summing to a target with two pointers from opposite ends of a sorted run-list is like a stats analyst starting from the highest and lowest scoring overs and moving inward until two overs sum to exactly 20 runs, in O(n) instead of checking every pair.

Example

python

# Two-pointer: find a pair in a SORTED array that sums to target -> O(n)
def two_sum_sorted(arr, target):
    left, right = 0, len(arr) - 1
    while left < right:
        current = arr[left] + arr[right]
        if current == target:
            return (left, right)
        elif current < target:
            left += 1
        else:
            right -= 1
    return None

print(two_sum_sorted([1, 3, 5, 7, 9, 11], 12))  # (1, 4) -> 3 + 9

# Sliding window: longest substring without repeating characters -> O(n)
def longest_unique_substring(s):
    seen = {}
    left = 0
    best = 0
    for right, ch in enumerate(s):
        if ch in seen and seen[ch] >= left:
            left = seen[ch] + 1
        seen[ch] = right
        best = max(best, right - left + 1)
    return best

print(longest_unique_substring("abcabcbb"))  # 3 ('abc')

# Sliding window: max sum of any subarray of fixed size k -> O(n)
def max_sum_fixed_window(arr, k):
    window_sum = sum(arr[:k])
    best = window_sum
    for right in range(k, len(arr)):
        window_sum += arr[right] - arr[right - k]
        best = max(best, window_sum)
    return best

print(max_sum_fixed_window([2, 1, 5, 1, 3, 2], 3))  # 9 (5+1+3)

Complexity

two_sum_sorted runs in O(n) time and O(1) extra space because each pointer moves at most n steps total, replacing the brute-force O(n^2) nested loop. longest_unique_substring runs in O(n) time and O(min(n, alphabet size)) space because each character is visited by the right pointer once, and the left pointer only moves forward, so total pointer movement is bounded by 2n. max_sum_fixed_window runs in O(n) time and O(1) extra space because it reuses the previous window's sum instead of recomputing a sum of k elements at every position, avoiding the O(n*k) brute-force cost.

🏏

Cricket analogy: two_sum_sorted's O(n) time is like a match analyst finding two overs whose run totals add to a target by walking from both ends of a sorted over-list just once, never rechecking a pair twice — no wasted O(n^2) nested scans.

Key Takeaways

Two-pointer technique converts many O(n^2) brute-force array/string problems into O(n) by moving indices inward based on comparisons.
Sliding window maintains a running contiguous range and updates it incrementally instead of recomputing from scratch, turning O(n*k) or O(n^2) into O(n).
Two-pointer typically requires sorted input or a symmetric structure (like palindrome checks); sliding window works on any sequence with a size or property constraint.
Always identify whether a brute-force solution has redundant recomputation across overlapping ranges — that redundancy is the signal to reach for two-pointer or sliding window.

Practice what you learned

1. What is the time complexity of finding a pair summing to a target in a sorted array using the two-pointer technique?

2. In the sliding window technique for a fixed-size window of length k, how is the window sum typically updated when moving to the next position?

3. Which precondition is typically required for the classic two-pointer 'pair sum' pattern to work correctly?

4. What is the time complexity of the longest-substring-without-repeating-characters sliding window solution?

Was this page helpful?

Strings as Data Structures

Topics covered

#Python#DataStructuresStudyNotes#DataStructures#CommonArrayAndStringProblems#Common#Array#String#Problems#StudyNotes#SkillVeris