Arrays — the workhorse of DSA

In Python "array" usually means list. It's a dynamic contiguous buffer — index is O(1), append is amortized O(1), insert in the middle is O(n) (everything after shifts).

Patterns to have in your muscle memory

Prefix sum

Precompute cumulative sums once. Then any range sum is a subtraction. Turns O(n) range queries into O(1).

In-place two-pointer

Modify from both ends. Reverses, palindromes, partitioning without extra space.

Kadane's algorithm

Max subarray sum in O(n). Keep a running sum, reset to zero if it goes negative.

Common bugs to avoid

• Off-by-one on the end index. range(n) is 0..n-1, not 0..n.
• Modifying a list while iterating. Use for x in list(seq): or build a new list.
• Confusing .copy() with slicing. a[:] is a shallow copy. Nested lists still share inner lists.
• list.remove(x) is O(n) and only removes the first match. Prefer del a[i] or list comprehension.

When a list is the wrong choice

• Frequent pop-from-front → use collections.deque (O(1) both ends).
• Fast membership check → use set (O(1) avg).
• Sorted numeric operations → use sortedcontainers.SortedList.

Try it

1. Given nums = [3, 1, 4, 1, 5, 9, 2, 6], find the max subarray sum using Kadane's algorithm.
2. Write a function that returns the running average (each element = mean of it and everything before).