BL
U

20. Dynamic Array with Automatic Capacity Doubling

Easy

Problem Description

Extend dynamic array to support automatic doubling when capacity is exhausted. Initial capacity is 2.

Support QQ operations:

  • •push x: If size equals capacity, double capacity (C←2CC \leftarrow 2C) and print RESIZE {new_cap}. Then append xx.
  • •capacity: Print current capacity.
  • •size: Print current size.
  • •print: Print all elements, or EMPTY if empty.

Input Format

  • •Line 1: An integer QQ (1≤Q≤1041 \le Q \le 10^4).
  • •Next QQ lines: Operations.

Output Format

Print query outputs and resize notifications on separate lines.

Example 1:
Input:
6
push 10
push 20
capacity
push 30
capacity
size
Output:
2
RESIZE 4
4
3
Explanation: Capacity reaches 2, pushing 30 triggers resize to 4.
Example 2:
Input:
3
capacity
size
print
Output:
2
0
EMPTY
Explanation: Initial state: capacity 2, size 0, EMPTY.
Example 3:
Input:
5
push 1
push 2
push 3
push 4
push 5
Output:
RESIZE 4
RESIZE 8
Explanation: Resizes trigger at 3rd element (cap 4) and 5th element (cap 8).
Constraints:
  • Standard integer bounds: 32-bit signed integer or input range [1, 10^5].
  • Time complexity target: O(N) or O(N log N) where applicable.
  • Auxiliary space target: O(1) or minimal auxiliary memory.
Follow up:Can this algorithm be adapted to an online streaming setting where the entire input cannot be held in memory simultaneously?
1,180 Online