Array Problems Solved: Two Pointer & Prefix Sum Techniques for Interviews
Complete array manipulation guide with two-pointer technique and prefix sums in Python. Master subarray problems, Kadane's algorithm, Dutch National Flag, and sliding window for coding interviews
When I Finally "Got" Two Pointers
Arrays seemed simple until interview problems hit. "Find pair summing to target"—easy with nested loops, but O(n²). The interviewer asked: "Can you do better?"
That's when I learned the two-pointer technique, and suddenly O(n) solutions appeared everywhere. Then came prefix sums, and subarray problems that seemed impossible became trivial.
In this guide, I'll share the array patterns that transformed my interview performance. You'll learn when to use two pointers, when to precompute prefix sums, and how to recognize these patterns instantly.
Pattern 1: Two Pointers on Sorted Arrays
The most common array pattern. When array is sorted, two pointers can replace nested loops.
Two Sum in Sorted Array
def two_sum_sorted(arr, target):
"""
Find pair summing to target in sorted array.
Two pointers from both ends.
"""
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 [] # No pair found
Time: O(n), Space: O(1)
Why it works: If sum too small, move left pointer (increases sum). If too large, move right pointer (decreases sum).
Three Sum
LeetCode #15 - 3Sum
def three_sum(nums):
"""
Find all unique triplets summing to zero.
Sort + two pointers for each element.
"""
nums.sort()
result = []
for i in range(len(nums) - 2):
# Skip duplicates for first element
if i > 0 and nums[i] == nums[i - 1]:
continue
# Two pointers for remaining elements
left, right = i + 1, len(nums) - 1
target = -nums[i]
while left < right:
current_sum = nums[left] + nums[right]
if current_sum == target:
result.append([nums[i], nums[left], nums[right]])
# Skip duplicates
while left < right and nums[left] == nums[left + 1]:
left += 1
while left < right and nums[right] == nums[right - 1]:
right -= 1
left += 1
right -= 1
elif current_sum < target:
left += 1
else:
right -= 1
return result
Time: O(n²), Space: O(1)
Pattern: Fix one element, use two pointers for the rest. Extends to 4Sum, KSum!
Pattern 2: Two Pointers - Opposite Directions
Container With Most Water
LeetCode #11 - Container With Most Water
def max_area(height):
"""
Find two lines that form container with most water.
Two pointers: move the shorter line inward.
"""
left, right = 0, len(height) - 1
max_water = 0
while left < right:
# Calculate current area
width = right - left
current_height = min(height[left], height[right])
current_area = width * current_height
max_water = max(max_water, current_area)
# Move pointer at shorter line
if height[left] < height[right]:
left += 1
else:
right -= 1
return max_water
Key insight: Always move the pointer at the shorter line. Moving the taller one can't increase area!
Pattern 3: Two Pointers - Same Direction (Fast & Slow)
Remove Duplicates from Sorted Array
LeetCode #26 - Remove Duplicates from Sorted Array
def remove_duplicates(nums):
"""
Remove duplicates in-place, return new length.
Slow pointer for unique position, fast for scanning.
"""
if not nums:
return 0
slow = 0 # Position for next unique element
for fast in range(1, len(nums)):
if nums[fast] != nums[slow]:
slow += 1
nums[slow] = nums[fast]
return slow + 1 # Length of unique portion
Pattern: Slow pointer marks position to write, fast pointer scans ahead.
Move Zeroes
LeetCode #283 - Move Zeroes
def move_zeroes(nums):
"""
Move all zeros to end, maintain relative order.
Slow pointer for non-zero position.
"""
slow = 0 # Position for next non-zero
for fast in range(len(nums)):
if nums[fast] != 0:
nums[slow], nums[fast] = nums[fast], nums[slow]
slow += 1
Same pattern: Slow pointer tracks where to place next valid element.
Pattern 4: Prefix Sums
Precompute cumulative sums to answer range queries in O(1).
Subarray Sum Equals K
LeetCode #560 - Subarray Sum Equals K
def subarray_sum(nums, k):
"""
Count subarrays with sum equal to k.
Use prefix sum + hash map.
"""
count = 0
prefix_sum = 0
sum_count = {0: 1} # sum -> count
for num in nums:
prefix_sum += num
# Check if (prefix_sum - k) exists
# If yes, found subarray(s) with sum k
if prefix_sum - k in sum_count:
count += sum_count[prefix_sum - k]
# Add current prefix sum to map
sum_count[prefix_sum] = sum_count.get(prefix_sum, 0) + 1
return count
Why it works:sum[i:j] = prefix_sum[j] - prefix_sum[i-1]
If prefix_sum[j] - prefix_sum[i-1] == k, then prefix_sum[i-1] = prefix_sum[j] - k
Time: O(n), Space: O(n)
Range Sum Query
class NumArray:
"""
Precompute prefix sums for O(1) range queries.
"""
def __init__(self, nums):
self.prefix = [0]
for num in nums:
self.prefix.append(self.prefix[-1] + num)
def sumRange(self, left, right):
"""Get sum of elements from index left to right."""
return self.prefix[right + 1] - self.prefix[left]
Pattern: Build prefix sum array once, answer queries in O(1).
Pattern 5: Dutch National Flag (3-Way Partitioning)
Partition array into three sections using three pointers.
Sort Colors
LeetCode #75 - Sort Colors
def sort_colors(nums):
"""
Sort array of 0s, 1s, 2s in-place.
Dutch National Flag algorithm.
"""
low, mid, high = 0, 0, len(nums) - 1
while mid <= high:
if nums[mid] == 0:
# Swap with low, move both forward
nums[low], nums[mid] = nums[mid], nums[low]
low += 1
mid += 1
elif nums[mid] == 1:
# Keep 1 in middle, move mid forward
mid += 1
else: # nums[mid] == 2
# Swap with high, move high back
nums[mid], nums[high] = nums[high], nums[mid]
high -= 1
# Don't move mid (need to check swapped element)
Invariant:
[0, low): all 0s[low, mid): all 1s[mid, high]: unknown(high, end]: all 2s
Time: O(n), Space: O(1)
Pattern 6: Kadane's Algorithm (Maximum Subarray)
Find maximum sum subarray using dynamic programming thinking.
Maximum Subarray
LeetCode #53 - Maximum Subarray
def max_subarray(nums):
"""
Find maximum sum of contiguous subarray.
Kadane's algorithm: track current and global max.
"""
current_max = global_max = nums[0]
for num in nums[1:]:
# Either extend current subarray or start new
current_max = max(num, current_max + num)
global_max = max(global_max, current_max)
return global_max
Key insight: At each position, decide: extend current subarray or start fresh?
Time: O(n), Space: O(1)
Maximum Product Subarray
def max_product(nums):
"""
Maximum product subarray (handles negatives).
Track both max and min (negative * negative = positive).
"""
if not nums:
return 0
max_prod = min_prod = result = nums[0]
for num in nums[1:]:
# Negative flips max and min
if num < 0:
max_prod, min_prod = min_prod, max_prod
max_prod = max(num, max_prod * num)
min_prod = min(num, min_prod * num)
result = max(result, max_prod)
return result
Clever twist: Track both max and min because negatives can flip them!
Pattern 7: In-Place Array Manipulation
Rotate Array
LeetCode #189 - Rotate Array
def rotate(nums, k):
"""
Rotate array right by k steps in-place.
Reverse three times.
"""
n = len(nums)
k = k % n # Handle k > n
# Helper: reverse subarray
def reverse(left, right):
while left < right:
nums[left], nums[right] = nums[right], nums[left]
left += 1
right -= 1
# Reverse entire array
reverse(0, n - 1)
# Reverse first k elements
reverse(0, k - 1)
# Reverse remaining elements
reverse(k, n - 1)
Magic: Three reverses achieve rotation!
[1,2,3,4,5,6,7] rotate 3:
- Reverse all:
[7,6,5,4,3,2,1] - Reverse first 3:
[5,6,7,4,3,2,1] - Reverse last 4:
[5,6,7,1,2,3,4]✓
Pattern 8: Product of Array Except Self
Product Except Self
LeetCode #238 - Product of Array Except Self
def product_except_self(nums):
"""
Product of all elements except self, without division.
Use left and right products.
"""
n = len(nums)
result = [1] * n
# Build left products
left_product = 1
for i in range(n):
result[i] = left_product
left_product *= nums[i]
# Build right products and combine
right_product = 1
for i in range(n - 1, -1, -1):
result[i] *= right_product
right_product *= nums[i]
return result
Insight: result[i] = (product of all left) × (product of all right)
Time: O(n), Space: O(1) excluding output
The Array Pattern Decision Tree
1. Need to find pair/triplet with sum?
- Array sorted → Two pointers
- Array unsorted → Hash map or sort first
2. Need to process subarrays?
- Fixed size → Sliding window
- Variable size conditions → Sliding window
- Sum queries → Prefix sums
- Maximum subarray → Kadane's algorithm
3. Need to partition array?
- Two groups → Two pointers (same direction)
- Three groups → Dutch National Flag
4. Need in-place manipulation?
- Remove elements → Two pointers (fast & slow)
- Rotate/reverse → Multiple reverses
- Swap/rearrange → Multiple passes
Common Array Mistakes
Mistake 1: Not Handling Edge Cases
# Always check:
if not nums: # Empty array
return default_value
if len(nums) == 1: # Single element
return nums[0]
Mistake 2: Index Out of Bounds
# WRONG
for i in range(len(arr)):
if arr[i] == arr[i + 1]: # Crashes at last element!
# RIGHT
for i in range(len(arr) - 1):
if arr[i] == arr[i + 1]:
Mistake 3: Modifying While Iterating
# WRONG: Size changes during iteration
for num in arr:
if condition:
arr.remove(num)
# RIGHT: Use two pointers or create new array
My Practice Strategy
Week 1: Two Pointers
- Master all variations (opposite, same direction, three pointers)
- 20-30 problems
- Focus on sorted vs unsorted
Week 2: Prefix Sums and Subarrays
- Range queries, subarray sums
- Kadane's algorithm variations
- 15-20 problems
Week 3: In-Place Manipulation
- Dutch National Flag, rotations
- Remove duplicates variations
- 15-20 problems
Week 4: Mixed Practice
- 40+ problems across all patterns
- Practice recognizing patterns quickly
- Time yourself
Real Interview Success
I was asked: "Find longest subarray with sum ≤ k."
My approach:
- "Subarray with condition" → Sliding window
- Expand window, contract when sum > k
- Track maximum length
Coded in 10 minutes using sliding window pattern!
Conclusion: Your Array Mastery Roadmap
Arrays aren't just about loops—they're about patterns:
- Two pointers - Replace nested loops with O(n)
- Prefix sums - Answer range queries in O(1)
- Sliding window - Process subarrays efficiently
- Kadane's algorithm - Maximum subarray problems
- In-place manipulation - Save space with clever swaps
Master these patterns, and array problems become pattern matching exercises.
Within 3-4 weeks of focused practice, you'll recognize which pattern to use within seconds of reading a problem.
Remember: arrays are the foundation. Master them, and everything else becomes easier!
Happy coding, and may your arrays always be sorted!
If you found this guide helpful, share it with others learning algorithms. Array patterns are fundamental to interview success. If this guide helped you master array patterns or ace your coding interview, I'd love to hear about it! Connect with me on Twitter or LinkedIn.
Support My Work
If this guide helped you master array patterns, understand two pointers and prefix sums, or ace array interview questions, I'd really appreciate your support! Creating comprehensive, free content like this takes significant time and effort. Your support helps me continue sharing knowledge and creating more helpful resources for students like you.
☕ Buy me a coffee - Every contribution, big or small, means the world to me and keeps me motivated to create more content!
Cover image by Ries Bosch on Unsplash