Static Arrays vs Dynamic Arrays: What is the Difference?
Understand the difference between static and dynamic arrays, how resizing works, and why append is O(1) amortized.
Expected Interview Answer
A static array has a fixed size decided at creation time and cannot grow or shrink, giving O(1) indexed access with minimal overhead, while a dynamic array (like Python's list or Java's ArrayList) automatically resizes by allocating a new, larger underlying static array and copying elements over when it runs out of room.
Static arrays are typically stack-allocated or fixed-size heap blocks, so their size must be known up front, and inserting beyond capacity is simply impossible without creating a new array yourself. Dynamic arrays hide that resizing behind a simple `append` or `push` interface: internally they track a length and a larger capacity, and only reallocate — usually doubling capacity — when length reaches capacity, which is why amortized append is O(1) even though any single resize is O(n). Both give O(1) random access by index because the underlying memory is still contiguous; the difference is entirely in whether growth is your responsibility or the structure's. This growth strategy is also why appending n elements to a dynamic array costs O(n) total, not O(n²), despite occasional expensive resizes.
- Static arrays have zero resize overhead and predictable memory footprint
- Dynamic arrays grow automatically without manual reallocation code
- Both give O(1) random access via contiguous memory
- Dynamic array append is O(1) amortized despite occasional O(n) resizes
AI Mentor Explanation
A static array is like a stadium built with a fixed number of seats decided before construction — once full, no more spectators can be admitted without building an entirely new stadium. A dynamic array is like a venue that starts with a modest seating block but, as soon as it fills up, automatically constructs a new, larger stadium nearby, moves every seated spectator over, and lets ticket sales continue. Most matches just fill seats one by one with no extra cost, but occasionally the whole crowd has to be relocated to a bigger venue. Averaged across a whole season of growing attendance, each spectator still only gets “moved” a small constant number of times.
Step-by-Step Explanation
Step 1
Static array: fix the size upfront
Capacity is set at creation and never changes; inserting beyond it is not possible in place.
Step 2
Dynamic array: track length vs capacity
The structure keeps an internal capacity larger than or equal to the current length.
Step 3
Dynamic array: append within capacity
If length < capacity, write directly at the next free slot in O(1).
Step 4
Dynamic array: grow when full
If length == capacity, allocate a new (usually 2x) block, copy all elements over (O(n)), then append.
What Interviewer Expects
- State that static arrays have fixed size and dynamic arrays resize automatically
- Explain the doubling (or similar growth factor) strategy behind dynamic arrays
- Justify why amortized append is O(1) despite an occasional O(n) resize
- Name real examples: Python list, Java ArrayList/Vector, C++ std::vector vs a raw C array
Common Mistakes
- Claiming dynamic array append is always O(1), ignoring the occasional O(n) resize
- Confusing a dynamic array with a linked list (both are contiguous, unlike linked lists)
- Forgetting resizing involves copying every existing element to new memory
- Assuming a static array can be resized in place without new allocation
Best Answer (HR Friendly)
“A static array has a fixed size I have to decide upfront and can never change, while a dynamic array like a Python list quietly grows on its own by allocating a bigger block and copying everything over whenever it runs out of room. Most of the time adding an item to a dynamic array is instant, and only occasionally does that bigger resize happen, which is why on average it still feels constant-time.”
Code Example
class DynamicArray:
def __init__(self):
self._capacity = 1
self._length = 0
self._data = [None] * self._capacity
def append(self, value):
if self._length == self._capacity:
self._resize(self._capacity * 2) # O(n) when it happens
self._data[self._length] = value
self._length += 1
def _resize(self, new_capacity):
new_data = [None] * new_capacity
for i in range(self._length):
new_data[i] = self._data[i] # copy every existing element
self._data = new_data
self._capacity = new_capacity
def __getitem__(self, index):
if index >= self._length:
raise IndexError("index out of range")
return self._data[index] # O(1), contiguous memoryFollow-up Questions
- Why does doubling capacity (rather than adding a fixed amount) keep append amortized O(1)?
- What happens to indexed access performance right after a resize?
- How would you implement removing from the front of a dynamic array efficiently?
- How does a dynamic array differ from a linked list in terms of insertion cost?
MCQ Practice
1. What triggers a dynamic array to reallocate its underlying storage?
A dynamic array reallocates and copies elements only when it has run out of spare capacity, typically doubling in size.
2. What is the amortized time complexity of appending to a dynamic array?
Although any single append may trigger an O(n) resize, the cost averaged over many appends is O(1) amortized.
3. What do a static array and a dynamic array have in common?
Both are backed by contiguous memory, which is why indexing by position is O(1) for either.
Flash Cards
What is the key limitation of a static array? — Its size is fixed at creation and cannot grow or shrink in place.
How does a dynamic array grow when full? — It allocates a new, larger block (commonly double the capacity) and copies all existing elements over.
Why is dynamic array append considered O(1) amortized? — Because expensive O(n) resizes happen rarely enough that the average cost per append stays constant.
Name a real-world dynamic array implementation. — Python's list, Java's ArrayList, or C++'s std::vector.