Dynamic Arrays & Amortized Analysis: Java, C++ and Competitive Programming Patterns
From append and capacity growth to two pointers, prefix sums, in-place algorithms and O(1) data-structure design
Dynamic Arrays: A Foundation for DSA
A dynamic array is a contiguous, indexable collection that grows when its backing storage fills up. In Java, the standard example is ArrayList<T>; in C++, it is std::vector<T>. Understanding this structure builds intuition for time complexity, two pointers, prefix sums, and data-structure design.
1. Size vs. capacity
Size counts existing elements. Capacity counts available allocated slots. The key invariant is 0 ≤ size ≤ capacity. In C++, reserve(n) increases capacity without adding elements, while resize(n) changes size. Java's ArrayList.ensureCapacity(n) similarly reserves storage without adding elements.
2. Why append is amortized O(1)
Appending usually costs O(1). If storage is full, a larger backing array must be allocated and existing elements moved or copied, costing O(n). With doubling growth, the number of copied elements across n appends follows a geometric series: 1 + 2 + 4 + ... < 2n. Together with n appends, total work is O(n), hence O(1) amortized per append. Amortized is a guarantee across a sequence of operations, not a claim that every individual append takes constant time.
Growing by one slot each time instead would cost O(n²) across n appends. Geometric growth trades some unused space for dramatically fewer reallocations. In Java, ArrayList growth policy is an implementation detail; C++ vector likewise does not promise a specific growth factor.
3. Operations and their costs
- Index access: O(1) using address arithmetic.
- Append: O(1) amortized; O(n) when reallocation occurs.
- Insert or delete in the middle: O(n) because elements shift.
- Delete last element: O(1) for ordinary element types.
- Search an unsorted dynamic array: O(n).
4. Java and C++ essentials
// Java
ArrayList<Integer> a = new ArrayList<>(2);
a.add(10); a.add(20); a.add(30);
a.ensureCapacity(100); // more space, not more elements
// C++
vector<int> v;
v.reserve(2); // size is still 0
v.push_back(10);
v.push_back(20);
v.push_back(30); // may trigger growth
Java's ArrayList stores object references, so ArrayList<Integer> has boxing overhead. A C++ vector<int> stores integer values contiguously. Reallocation of a C++ vector can invalidate pointers, references, and iterators into its elements.
5. Train the pattern-recognition muscle
Problem A: Remove Element (LeetCode 27)
Clue: “Remove in-place and return a new length.” Insight: Do not repeatedly delete and shift. Use a read pointer to scan and a write pointer to compact values worth keeping. Invariant: positions [0, write) hold exactly the retained values from the scanned prefix.
// Java
int removeElement(int[] nums, int val) {
int write = 0;
for (int read = 0; read < nums.length; read++) {
if (nums[read] != val) nums[write++] = nums[read];
}
return write;
}
Time O(n), auxiliary space O(1).
Problem B: Move Zeroes (LeetCode 283)
Clue: preserve relative order while moving unwanted values. Insight: compact the nonzero values first; overwrite the remaining suffix with zeroes. The invariant is the same as Remove Element.
// C++
void moveZeroes(vector<int>& nums) {
int write = 0;
for (int read = 0; read < (int)nums.size(); ++read)
if (nums[read] != 0) nums[write++] = nums[read];
while (write < (int)nums.size()) nums[write++] = 0;
}
Problem C: Merge Sorted Array (LeetCode 88)
Clue: sorted arrays, extra space at the end. Insight: fill from the back so you do not overwrite unread values. Invariant: everything to the right of the destination pointer is already correct.
// Java
void merge(int[] a, int m, int[] b, int n) {
int i = m - 1, j = n - 1, k = m + n - 1;
while (j >= 0) {
if (i >= 0 && a[i] > b[j]) a[k--] = a[i--];
else a[k--] = b[j--];
}
}
Problem D: Rotate Array (LeetCode 189)
Clue: rotate in-place. Insight: map each index to (i + k) % n, then implement the rotation using three reversals: reverse all, reverse the first k, reverse the rest. Time O(n), extra space O(1).
Problem E: Range Sum Query (LeetCode 303)
Clue: many repeated queries on the same unchanged array. Insight: preprocess prefix sums, with prefix[i+1] = prefix[i] + nums[i], then compute sum(l,r) = prefix[r+1] - prefix[l]. Preprocessing O(n), each query O(1), extra space O(n).
Problem F: Insert Delete GetRandom O(1) (LeetCode 380)
Clue: fast lookup, fast random indexing, and removal without a required order. Insight: combine a dynamic array of values with a hash map from value to index. To remove a value, replace it with the last element, update the last element's index in the map, and pop the tail. No O(n) shifting. Invariant: for every stored value, index[value] equals its current position. Operations are expected/amortized O(1).
6. How competitive programmers approach a new problem
- Read constraints first: O(n²) is usually implausible for n = 100,000.
- Find the bottleneck: repeated scanning, shifting, or recomputation.
- Extract wording clues: “in-place,” “sorted,” “range queries,” “order irrelevant,” “extra space.”
- State the invariant before coding: what is guaranteed after each iteration?
- Optimize the waste: compact instead of deleting, go backwards instead of shifting, precompute instead of rescanning, or combine structures.
- Prove complexity and test edges: empty inputs, one element, duplicates, capacity boundaries, and overflow.
7. Seven-day practice ladder
Day 1: implement dynamic array from scratch. Day 2: prove amortized append and compare growth strategies. Day 3: Remove Element, Move Zeroes, Remove Duplicates. Day 4: Merge Sorted Array, Two Sum II. Day 5: Rotate Array, Sort Colors. Day 6: Range Sum Query, Product of Array Except Self. Day 7: Insert Delete GetRandom O(1), then redo the toughest problems from memory.
The mental tattoo: For any array problem, ask whether you are searching, shifting, rearranging, maintaining a range, or exploiting sorted order. That question points you toward the right pattern.