Arrays & Two Pointers

Concept

An array stores elements in contiguous memory, so reading any index is O(1). Inserting or deleting in the middle needs shifting, which is O(n).

Two pointers: keep one pointer at each end (or both moving forward) to avoid nested loops on sorted data.

Sliding window: maintain a window [left, right] and expand/shrink it to track sums or unique characters in O(n).

Complexity

Code (Python)

def max_sum_subarray(nums, k):
    # Sliding window: O(n)
    window = sum(nums[:k])
    best = window
    for i in range(k, len(nums)):
        window += nums[i] - nums[i - k]
        best = max(best, window)
    return best

def is_palindrome(s):
    # Two pointers: O(n)
    l, r = 0, len(s) - 1
    while l < r:
        if s[l] != s[r]:
            return False
        l, r = l + 1, r - 1
    return True

Remember

• Sorted array → think two pointers or binary search.
• Subarray / substring → think sliding window.
• Prefix sums answer range-sum queries in O(1).