Dynamic Ranges

Queue with Dynamic Range

Problem Statement

Given a queue (dynamic array) of size N (where N is between 1 and 64), each element at index i must have a value in the range 0, i.

For example:

• Element at index 0 can be in range 0, 0 → must be 0
• Element at index 1 can be in range 0, 1 → can be 0 or 1
• Element at index 2 can be in range 0, 2 → can be 0, 1, or 2
• Element at index i can be in range 0, i → can be any value from 0 to i

Constraints

• Queue size: 1 ≤ N ≤ 64
• Element at index i: 0 ≤ queuei ≤ i
• Each element's range grows with its index

Examples

Example 1:

Queue size = 4
[0, 1, 2, 3]
Explanation:
- queue[0] ∈ [0,0] → 0
- queue[1] ∈ [0,1] → 1
- queue[2] ∈ [0,2] → 2
- queue[3] ∈ [0,3] → 3

Example 2:

Queue size = 4
[0, 0, 1, 3]
Explanation:
- queue[0] ∈ [0,0] → 0 ✓
- queue[1] ∈ [0,1] → 0 ✓
- queue[2] ∈ [0,2] → 1 ✓
- queue[3] ∈ [0,3] → 3 ✓

Example 3:

[0, 1, 3, 2] with size = 4
Valid
Explanation: All elements satisfy their range constraints

Example 4:

[0, 2, 2, 2] with size = 4
Invalid
Explanation: queue[1] = 2, but it must be in [0,1], so 2 is invalid

Example 5:

Queue size = 1
[0]
Explanation: Only element can be in [0,0], so it must always be 0