Advanced Array Techniques

These powerful techniques help solve complex array problems efficiently. They're frequently asked in coding interviews and competitive programming.

Prefix Sum Technique

Prefix sum Pre-computes cumulative sums to answer range sum queries in O(1) time.

Concept

arr    = [1, 2, 3, 4, 5]
prefix = [1, 3, 6, 10, 15]
        #  1  1+2  1+2+3  1+2+3+4  1+2+3+4+5

# Sum of range [L, R] = prefix[R] - prefix[L-1]
# Sum of [1, 3] = prefix[3] - prefix[0] = 10 - 1 = 9  ✓
#               = 2 + 3 + 4 = 9  ✓

Implementation

def build_prefix_sum(arr):
    n = len(arr)
    prefix = [0] * n
    prefix[0] = arr[0]
    
    for i in range(1, n):
        prefix[i] = prefix[i-1] + arr[i]
    
    return prefix

def range_sum(prefix, left, right):
    if left == 0:
        return prefix[right]
    return prefix[right] - prefix[left-1]

Time Complexity:

• Build: O(n)
• Query: O(1)

Sliding Window Technique

Sliding window maintains a "window" of elements and slides it across the array, useful for subarray problems.

Fixed-Size Window

Find maximum sum of k consecutive elements.

def max_sum_subarray(arr, k):
    # Calculate first window sum
    window_sum = sum(arr[:k])
    max_sum = window_sum
    
    # Slide window
    for i in range(k, len(arr)):
        window_sum += arr[i] - arr[i-k]  # Add new, remove old
        max_sum = max(max_sum, window_sum)
    
    return max_sum

Time: O(n) instead of O(n×k) brute force

Variable-Size Window

Find smallest subarray with sum ≥ target.

def min_subarray_len(arr, target):
    left = 0
    current_sum = 0
    min_len = float('inf')
    
    for right in range(len(arr)):
        current_sum += arr[right]
        
        while current_sum >= target:
            min_len = min(min_len, right - left + 1)
            current_sum -= arr[left]
            left += 1
    
    return min_len if min_len != float('inf') else 0

Two-Pointer Technique

Two pointers use two indices to traverse the array, often from opposite ends or at different speeds.

Pattern 1: Opposite Ends

Find pair with given sum in sorted array.

def two_sum_sorted(arr, target):
    left, right = 0, len(arr) - 1
    
    while left < right:
        current_sum = arr[left] + arr[right]
        
        if current_sum == target:
            return (left, right)
        elif current_sum < target:
            left += 1  # Need larger sum
        else:
            right -= 1  # Need smaller sum
    
    return None

Time: O(n) instead of O(n²) brute force

Pattern 2: Remove Duplicates

Remove duplicates from sorted array in-place.

def remove_duplicates(arr):
    if not arr:
        return 0
    
    write_idx = 1  # Where to write next unique element
    
    for i in range(1, len(arr)):
        if arr[i] != arr[i-1]:  # Found unique
            arr[write_idx] = arr[i]
            write_idx += 1
    
    return write_idx  # New length

Pattern 3: Fast & Slow Pointers

Detect cycles or find middle element.

def find_middle(arr):
    slow = fast = 0
    
    while fast < len(arr) - 1 and fast + 1 < len(arr):
        slow += 1
        fast += 2
    
    return arr[slow]

Problem: Maximum Subarray Sum (Kadane's Algorithm)

Find contiguous subarray with largest sum.

def max_subarray_sum(arr):
    current_sum = max_sum = arr[0]
    
    for i in range(1, len(arr)):
        current_sum = max(arr[i], current_sum + arr[i])
        max_sum = max(max_sum, current_sum)
    
    return max_sum

Example: [-2, 1, -3, 4, -1, 2, 1, -5, 4] → 6 (subarray [4, -1, 2, 1])

Quiz

Key Takeaways

✅ Prefix sum enables O(1) range queries after O(n) preprocessing
✅ Sliding window optimizes subarray problems from O(n²) to O(n)
✅ Two pointers efficiently solve pair-finding and partitioning problems
✅ Kadane's algorithm finds maximum subarray sum in O(n)
✅ Master these patterns - they appear in 50%+ of array interview questions!

These techniques are essential for competitive programming and interviews! 🚀