Arrays
An array stores elements in contiguous memory, allowing O(1) access by index.
# Python list as array
arr = [10, 20, 30, 40, 50]
# Access: O(1)
print(arr[0]) # 10
print(arr[-1]) # 50
print(arr[2]) # 30
# Modification: O(1)
arr[2] = 99
print(arr) # [10, 20, 99, 40, 50]
# Append to end: O(1) amortized
arr.append(60)
# Insert in middle: O(n) — shifts elements
arr.insert(2, 25)
# Delete by index: O(n) — shifts elements
arr.pop(2)
Two-Pointer Technique
Use two pointers to reduce O(n²) to O(n).
Two Sum (Sorted Array)
def two_sum_sorted(arr, target):
"""Find two numbers that sum to target in sorted array"""
left, right = 0, len(arr) - 1
while left < right:
total = arr[left] + arr[right]
if total == target:
return left, right
elif total < target:
left += 1
else:
right -= 1
return None
print(two_sum_sorted([1, 3, 5, 7, 9], 12)) # (2, 4) → 5+7=12
Remove Duplicates (In-Place)
def remove_duplicates(arr):
"""Remove duplicates from sorted array in-place, return new length"""
if not arr:
return 0
slow = 0
for fast in range(1, len(arr)):
if arr[fast] != arr[slow]:
slow += 1
arr[slow] = arr[fast]
return slow + 1
arr = [1, 1, 2, 3, 3, 4]
length = remove_duplicates(arr)
print(arr[:length]) # [1, 2, 3, 4]
Valid Palindrome
def is_palindrome(s):
"""Check if string is a palindrome, ignoring non-alphanumeric chars"""
left, right = 0, len(s) - 1
while left < right:
while left < right and not s[left].isalnum():
left += 1
while left < right and not s[right].isalnum():
right -= 1
if s[left].lower() != s[right].lower():
return False
left += 1
right -= 1
return True
print(is_palindrome("A man, a plan, a canal: Panama")) # True
Sliding Window Technique
Efficiently process subarrays/substrings of a given size.
Maximum Sum Subarray of Size K
def max_sum_subarray(arr, k):
"""Fixed window: find max sum of any k consecutive elements"""
n = len(arr)
if n < k:
return None
# Initial window
window_sum = sum(arr[:k])
max_sum = window_sum
# Slide window: add right element, remove left element
for i in range(k, n):
window_sum += arr[i] - arr[i - k]
max_sum = max(max_sum, window_sum)
return max_sum
print(max_sum_subarray([2, 1, 5, 1, 3, 2], 3)) # 9 (5+1+3)
Longest Substring Without Repeating Characters
def length_of_longest_substring(s):
"""Variable window: expand right, shrink left on duplicate"""
char_index = {}
max_len = 0
left = 0
for right, char in enumerate(s):
if char in char_index and char_index[char] >= left:
left = char_index[char] + 1
char_index[char] = right
max_len = max(max_len, right - left + 1)
return max_len
print(length_of_longest_substring("abcabcbb")) # 3 (abc)
print(length_of_longest_substring("pwwkew")) # 3 (wke)
Minimum Size Subarray Sum
def min_subarray_len(target, arr):
"""Find minimum length subarray with sum >= target"""
left = 0
window_sum = 0
min_len = float('inf')
for right in range(len(arr)):
window_sum += arr[right]
while window_sum >= target:
min_len = min(min_len, right - left + 1)
window_sum -= arr[left]
left += 1
return min_len if min_len != float('inf') else 0
print(min_subarray_len(7, [2, 3, 1, 2, 4, 3])) # 2 (4+3)
Prefix Sums
Precompute cumulative sums for O(1) range queries.
def build_prefix(arr):
prefix = [0] * (len(arr) + 1)
for i, val in enumerate(arr):
prefix[i + 1] = prefix[i] + val
return prefix
def range_sum(prefix, left, right):
"""Sum of arr[left:right+1] in O(1)"""
return prefix[right + 1] - prefix[left]
arr = [1, 2, 3, 4, 5]
prefix = build_prefix(arr)
print(range_sum(prefix, 1, 3)) # 9 (2+3+4)
print(range_sum(prefix, 0, 4)) # 15 (sum of all)
# 2D prefix sum for matrix:
def build_2d_prefix(matrix):
rows, cols = len(matrix), len(matrix[0])
P = [[0] * (cols + 1) for _ in range(rows + 1)]
for r in range(rows):
for c in range(cols):
P[r+1][c+1] = (P[r][c+1] + P[r+1][c]
- P[r][c] + matrix[r][c])
return P
def region_sum(P, r1, c1, r2, c2):
return P[r2+1][c2+1] - P[r1][c2+1] - P[r2+1][c1] + P[r1][c1]
Exercises
Exercise 1: Container With Most Water
Given heights, find two lines that form a container holding the most water.
Solution:
def max_water(heights):
left, right = 0, len(heights) - 1
max_vol = 0
while left < right:
width = right - left
height = min(heights[left], heights[right])
max_vol = max(max_vol, width * height)
if heights[left] < heights[right]:
left += 1
else:
right -= 1
return max_vol
print(max_water([1, 8, 6, 2, 5, 4, 8, 3, 7])) # 49
Exercise 2: Subarray Sum Equals K
Count subarrays that sum to exactly k.
Solution:
def subarray_sum(nums, k):
count = 0
prefix_sum = 0
seen = {0: 1} # prefix_sum: count
for num in nums:
prefix_sum += num
# If (prefix_sum - k) was seen, there's a subarray summing to k
count += seen.get(prefix_sum - k, 0)
seen[prefix_sum] = seen.get(prefix_sum, 0) + 1
return count
print(subarray_sum([1, 1, 1], 2)) # 2
print(subarray_sum([1, 2, 3], 3)) # 2
Exercise 3: Sliding Window Maximum
Find the maximum value in each window of size k.
Solution:
from collections import deque
def sliding_window_max(arr, k):
"""Uses monotonic deque for O(n) solution"""
dq = deque() # stores indices, decreasing values
result = []
for i, val in enumerate(arr):
# Remove indices outside window
while dq and dq[0] < i - k + 1:
dq.popleft()
# Remove smaller elements from back
while dq and arr[dq[-1]] < val:
dq.pop()
dq.append(i)
if i >= k - 1:
result.append(arr[dq[0]])
return result
print(sliding_window_max([1, 3, -1, -3, 5, 3, 6, 7], 3))
# [3, 3, 5, 5, 6, 7]