Problem statement

https://leetcode.com/problems/read-n-characters-given-read4-ii-call-multiple-times/

Solution

This problem is extension of problem 0157. The difference here is that we need to keep global self.buf, because on the next call we still can have unused symbols inside. So, we have:

  1. self.buf is buffer with 4 elements.
  2. self.curr is variable that indicates on which index in self.buf we currently on.
  3. self.size is total number of elements in buffer we have.

Let us consider function read now:

  1. We start with pl = 0.
  2. Iterate until we have pl < n and do the following steps:
  3. If we do not have any more elements in buffer to use, we need to update buffer, using function read4.
  4. If we have size of buffer equal to 0, we break immedietly and return pl.
  5. Next, we check how many elements we can take from buffer: no more than self.size - self.curr and also no more than n - pl, so we take minimum of them.
  6. Update buf with corresponding elements from self.buf, update pl and self.curr.
  7. Check if self.curr becomes equal to self.size: it means that we need to update buffer, so put self.curr = 0.

Complexity

Time complexity is $\mathcal{O}(m)$, where $m = n_1 + \dots + n_k$, sizes of queries. Space complexity is $\mathcal{O}(1)$.

Code

class Solution:
    def __init__(self):
        self.buf = [""] * 4
        self.curr = 0
        self.size = 0
    
    def read(self, buf, n):
        pl = 0
        while pl < n:
            if self.curr == 0: self.size = read4(self.buf)
            
            if self.size == 0: break
            k = min(n - pl, self.size - self.curr)
            buf[pl:pl+k] = self.buf[self.curr: self.curr + k]
            pl += k
            self.curr += k
           
            if self.curr == self.size: self.curr = 0
                
        return pl