Solution
Approach 1: Store Exhausted Position and Quantity
Intuition
We can store an index i
and quantity q
which represents that q
elements of A[i]
(repeated A[i+1]
times) are exhausted.
For example, if we have A = [1,2,3,4]
(mapping to the sequence [2,4,4,4]
) then i = 0, q = 0
represents that nothing is exhausted; i = 0, q = 1
represents that [2]
is exhausted, i = 2, q = 1
will represent that we have currently exhausted [2, 4]
, and so on.
Algorithm
Say we want to exhaust n
more elements. There are currently D = A[i] - q
elements left to exhaust (of value A[i+1]
).
If n > D
, then we should exhaust all of them and continue: n -= D; i += 2; q = 0
.
Otherwise, we should exhaust some of them and return the current element's value: q += D; return A[i+1]
.
Complexity Analysis
-
Time Complexity: , where is the length of
A
, and is the number of calls toRLEIterator.next
. -
Space Complexity: .
Analysis written by: @awice.