Skip to interview prep
Apexed

136. For an array-backed stack, compare growing by doubling with growing by a constant amount.

MediumStacks

Technical
Show model answer

With doubling, a resize copies the current n elements into a 2n array. Over n pushes the copies total 1 + 2 + 4 + ... < 2n, so push is O(1) amortised even though a single push can cost O(n). Unused capacity is at most about n slots.

Growing by a constant c copies after every c pushes, giving c + 2c + 3c + ... which is about n² / (2c) total work, or O(n) amortised per push. So geometric growth is the standard choice; to shrink safely, halve only when the array is a quarter full to avoid thrashing at the boundary.

What interviewers listen for

  • Doubling: O(1) amortised push. Constant growth: O(n) amortised push.
For an array-backed stack, compare growing by doubling with growing by a constant amount. — Data structures & algorithms interview question — Apexed