LeetCode 158 – Read N Characters Given Read4 II – Call Multiple Times

The same API as problem 157, with one sentence changed: read may be called multiple times. That sentence turns a loop into a small piece of state management, and it is one of the cleanest examples on the list of a requirement that changes the design rather than the code.

The problem

Implement read(buf, n) using read4, where read is called repeatedly and must continue from where the previous call stopped.

file = "abc"
read(buf, 1)  -> 1, buf = "a"
read(buf, 2)  -> 2, buf = "bc"
read(buf, 1)  -> 0            file exhausted

file = "abcdefg"
read(buf, 1)  -> 1, buf = "a"      read4 fetched "abcd" -- b, c, d must survive
read(buf, 3)  -> 3, buf = "bcd"    served entirely from the leftover
read(buf, 5)  -> 3, buf = "efg"

That second example is the whole problem. The first call wants one character, but the only primitive available fetches four — and the other three are gone from the file forever.

What breaks

Problem 157's solution consumes up to four characters per read4 and copies out only as many as the caller wanted. In a single call the surplus is harmlessly discarded. Called twice, the discarded characters are lost data:

read(buf, 1) with 157's code:
  read4 -> "abcd"     copies 'a', discards "bcd"

read(buf, 3):
  read4 -> "efg"      returns "efg"

   the caller gets "a" then "efg" -- "bcd" vanished.

Naming that failure before writing anything is the answer. The fix follows immediately: the surplus has to live somewhere that survives between calls.

Three fields

buf4        the 4-character scratch buffer, now instance state
bufCount    how many characters read4 actually put in it
bufPointer  how many of those have been handed to callers

The invariant: buf4[bufPointer .. bufCount) is data that has been read from the file and not yet delivered. When the pointer catches the count, the buffer is spent and it is time to fetch again.

That single comparison replaces problem 157's nested loops. There is no inner copy loop at all — one character moves per iteration, and refilling is just another branch.

Java

class Solution extends Reader4 {
    // buf4[bufPointer .. bufCount) is read from the file but not yet delivered.
    private final char[] buf4 = new char[4];
    private int bufPointer = 0;
    private int bufCount = 0;

    public int read(char[] buf, int n) {
        int total = 0;

        while (total < n) {
            if (bufPointer == bufCount) {     // leftovers exhausted -- refill
                bufCount = read4(buf4);
                bufPointer = 0;

                if (bufCount == 0) break;     // end of file
            }

            buf[total++] = buf4[bufPointer++];
        }

        return total;
    }
}

Resetting bufPointer = 0 immediately after the refill matters. Doing it before the read4, or forgetting it, leaves the pointer past the end of a fresh chunk and the solution silently skips characters.

The end-of-file check must come after the assignment to bufCount, because bufCount == 0 is what identifies it. Checking a stale value is the natural mistake.

One character copied per iteration looks wasteful next to 157's block copy, and it is O(1) either way. Clarity wins; if the interviewer asks, a bulk arraycopy of min(bufCount - bufPointer, n - total) is the optimisation, and it is worth naming rather than writing.

Python

class Solution:
    def __init__(self):
        # buf4[pointer:count] is read from the file but not yet delivered.
        self.buf4 = [""] * 4
        self.pointer = 0
        self.count = 0

    def read(self, buf: list, n: int) -> int:
        total = 0

        while total < n:
            if self.pointer == self.count:        # leftovers exhausted -- refill
                self.count = read4(self.buf4)
                self.pointer = 0

                if self.count == 0:               # end of file
                    break

            buf[total] = self.buf4[self.pointer]
            total += 1
            self.pointer += 1

        return total

The state lives on the instance, so it persists across calls — which is exactly what the problem asks for and exactly what makes this object not safe to share between files or threads. Saying that unprompted is the difference between solving the exercise and understanding it.

Complexity

	Time per call	Space
Buffered read	`O(n)`	`O(1)` — four characters, forever

Across a whole file the total work is linear in its size, and read4 is called ⌈size/4⌉ times — no character is ever read from the file twice, which is the property that failed in the naive version.

What this is really about

This is a buffered reader. BufferedInputStream, BufferedReader and every socket-reading loop you have ever written hold exactly these three fields, usually with a buffer of 8192 rather than 4. The reason they exist is the reason this problem exists: the underlying source delivers on its own terms, and something has to reconcile that with what the caller asked for.

The follow-ups worth having ready: thread safety — this is not safe, and a lock around read is the honest fix; a larger buffer — the same three fields with a bigger array, which is the only change needed; and peeking or pushback, which is why the pointer is separate from the count rather than the buffer being shifted.

What the interviewer is checking

That you identify the lost-leftover bug before writing code.
Three pieces of state, and that they persist across calls.
The refill condition pointer == count.
Resetting the pointer immediately after a refill.
End of file detected from a fresh read4 returning 0, not a stale count.
Many small calls, one large call, and reading past the end.
That you recognise this as a buffered reader, and that it is not thread-safe.