DSA · Chapter 4 of 40
Arrays
An array stores elements in contiguous memory, so any element can be read by index in O(1) time. In Python the built-in list behaves like a dynamic array that grows automatically.
Arrays are the most common structure in interviews because they support fast reads and simple iteration, but inserting or deleting in the middle costs O(n) because later elements must shift.
Costs
Access by index O(1), search O(n), insert/delete at the end O(1) amortised, insert/delete in the middle O(n).
Dynamic arrays
When a dynamic array runs out of capacity it allocates a bigger block and copies everything, which is why appends are amortised rather than always O(1).
Example 1 (python)
nums = [10, 20, 30]
print(nums[1]) # O(1) access
nums.append(40) # amortised O(1)
nums.insert(0, 5) # O(n) shift
print(nums)Output
20
[5, 10, 20, 30, 40]Reads are instant; inserting at the front shifts every element.
Example 2 (python)
# find the maximum in one pass
nums = [3, 9, 2, 7]
best = nums[0]
for n in nums[1:]:
if n > best:
best = n
print(best)Output
9A single O(n) scan is enough for max/min problems.
Key points
- Array access by index is O(1).
- Inserting or deleting in the middle is O(n).
- Python lists are dynamic arrays.
- Most interview problems start with an array.
💡 Note: If a problem gives you a sorted array, think two pointers or binary search.