Arrays and Lists
An array stores elements in contiguous memory so any index can be reached in constant time. In Python the built-in list is a dynamic array.
| Operation | Time |
|---|---|
Access a[i] | O(1) |
| Append | O(1) amortised |
| Insert / delete in the middle | O(n) |
| Search (unsorted) | O(n) |
Two pointers
two_pointers.py
def is_palindrome(s: str) -> bool:
i, j = 0, len(s) - 1
while i < j:
if s[i] != s[j]:
return False
i += 1
j -= 1
return True
Sliding window
sliding_window.py
def max_sum_subarray(nums, k):
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 # O(n) time, O(1) space
Prefix sums
prefix_sums.py
from itertools import accumulate
nums = [3, 1, 4, 1, 5]
prefix = [0, *accumulate(nums)] # [0, 3, 4, 8, 9, 14]
range_sum = prefix[4] - prefix[1] # sum of nums[1:4] = 6
TIP
Many array problems reduce to a single pass with extra state (a window, a pointer, or a running sum). Try that before reaching for nested loops.
Loading Comments...