LeetCode 158: Read N Characters Given read4 II - Call Multiple Times

Problem Restatement

We are given a file, but we cannot read from it directly.

The only available API is:

read4(buf4)

This reads up to 4 characters from the file into buf4, then returns how many characters were actually read.

We need to implement:

read(buf, n)

It should read up to n characters, write them into buf, and return the number of characters actually read.

The difference from LeetCode 157 is important: read may be called multiple times. Any extra characters read by read4 during one call must be saved for the next call. LeetCode’s statement says read4 owns the file pointer, buf is a destination buffer, and read may be called multiple times.

Input and Output

Example method shape:

def read(self, buf: List[str], n: int) -> int:
    ...

Examples

Example 1:

file = "abc"

Calls:

read(buf, 1)
read(buf, 2)
read(buf, 1)

The first call reads:

"a"

and returns:

1

The second call reads:

"bc"

and returns:

2

The third call reaches the end of the file and returns:

0

Example 2:

file = "abc"

Call:

read(buf, 4)

The file only has 3 characters, so it reads:

"abc"

and returns:

3

A later call:

read(buf, 1)

returns:

0

First Thought: Reuse the LeetCode 157 Solution

For LeetCode 157, read is called only once.

So we could do this:

buf4 = [""] * 4
count = read4(buf4)

Then copy only the needed characters into buf.

That breaks when read is called multiple times.

Consider:

file = "abcdef"

First call:

read(buf, 1)

If we call read4, it reads:

"abcd"

But we only need:

"a"

The leftover characters:

"bcd"

must be used by future calls.

So the solution needs persistent state inside the class.

Key Insight

We keep a small internal buffer.

This buffer stores characters read by read4 but not yet consumed by read.

We need three instance variables:

When:

self.i4 < self.n4

there are leftover characters available.

When:

self.i4 == self.n4

the internal buffer is empty, so we call read4 again.

Algorithm

Initialize the internal state in the constructor:

self.buf4 = [""] * 4
self.i4 = 0
self.n4 = 0

For each call to read(buf, n):

1. Set i = 0, the number of characters copied into buf.
2. While i < n:
   • If the internal buffer is empty, refill it using read4.
   • If read4 returns 0, stop because the file ended.
   • Copy one character from self.buf4[self.i4] into buf[i].
   • Increment both i and self.i4.
3. Return i.

This copies leftover characters first before reading new characters from the file.

Walkthrough

Use:

file = "abcdef"

Call 1:

read(buf, 1)

Internal buffer is empty, so we call read4.

self.buf4 becomes:

"abcd"

and:

self.n4 = 4
self.i4 = 0

We only need one character.

Copy:

"a"

Now:

self.i4 = 1

Return:

1

The internal buffer still has:

"bcd"

Call 2:

read(buf, 3)

Now:

self.i4 = 1
self.n4 = 4

So we copy from the old buffer first:

"bcd"

Now:

self.i4 = 4

Return:

3

Call 3:

read(buf, 2)

Internal buffer is empty, so we call read4.

It reads:

"ef"

and returns:

2

We copy both characters and return:

2

Correctness

The internal buffer stores exactly the characters that were returned by read4 but not yet copied into a user-provided buf.

At the start of each loop iteration, if self.i4 < self.n4, then self.buf4[self.i4] is the next unread character in file order. Copying it into buf preserves the order of the stream.

If self.i4 == self.n4, all buffered characters have already been consumed. The algorithm then calls read4, which reads the next consecutive characters from the file pointer. Resetting self.i4 to 0 makes the first newly read character the next one to copy.

The loop stops only when either n characters have been copied or read4 returns 0, meaning the file has ended.

Therefore, each call to read returns exactly the next n available characters, or fewer if the file ends. Characters fetched but not requested are saved for later calls.

Complexity

Let k be the number of characters returned by one call to read.

Implementation

# The read4 API is already defined for you.
# def read4(buf4: List[str]) -> int:

class Solution:
    def __init__(self):
        self.buf4 = [""] * 4
        self.i4 = 0
        self.n4 = 0

    def read(self, buf: List[str], n: int) -> int:
        i = 0

        while i < n:
            if self.i4 == self.n4:
                self.i4 = 0
                self.n4 = read4(self.buf4)

                if self.n4 == 0:
                    break

            buf[i] = self.buf4[self.i4]
            i += 1
            self.i4 += 1

        return i

Code Explanation

The constructor creates persistent state:

self.buf4 = [""] * 4
self.i4 = 0
self.n4 = 0

This state survives across calls to read.

Inside read, i counts how many characters have been copied into the current output buffer:

i = 0

When the internal buffer has no available characters:

if self.i4 == self.n4:

we refill it:

self.i4 = 0
self.n4 = read4(self.buf4)

If no characters were read:

if self.n4 == 0:
    break

the file has ended.

Otherwise, we copy one character:

buf[i] = self.buf4[self.i4]

Then we advance both pointers:

i += 1
self.i4 += 1

Finally:

return i

returns how many characters were copied during this call.

Testing

LeetCode provides read4, but we can simulate it locally.

from typing import List

class Reader4:
    def __init__(self, file: str):
        self.file = file
        self.ptr = 0

    def read4(self, buf4: List[str]) -> int:
        count = 0

        while count < 4 and self.ptr < len(self.file):
            buf4[count] = self.file[self.ptr]
            self.ptr += 1
            count += 1

        return count

class Solution(Reader4):
    def __init__(self, file: str):
        super().__init__(file)
        self.buf4 = [""] * 4
        self.i4 = 0
        self.n4 = 0

    def read(self, buf: List[str], n: int) -> int:
        i = 0

        while i < n:
            if self.i4 == self.n4:
                self.i4 = 0
                self.n4 = self.read4(self.buf4)

                if self.n4 == 0:
                    break

            buf[i] = self.buf4[self.i4]
            i += 1
            self.i4 += 1

        return i

def read_string(sol: Solution, n: int) -> str:
    buf = [""] * n
    count = sol.read(buf, n)
    return "".join(buf[:count])

def run_tests():
    sol = Solution("abc")
    assert read_string(sol, 1) == "a"
    assert read_string(sol, 2) == "bc"
    assert read_string(sol, 1) == ""

    sol = Solution("abc")
    assert read_string(sol, 4) == "abc"
    assert read_string(sol, 1) == ""

    sol = Solution("abcdef")
    assert read_string(sol, 1) == "a"
    assert read_string(sol, 3) == "bcd"
    assert read_string(sol, 2) == "ef"
    assert read_string(sol, 1) == ""

    sol = Solution("abcdefghijk")
    assert read_string(sol, 4) == "abcd"
    assert read_string(sol, 4) == "efgh"
    assert read_string(sol, 4) == "ijk"

    print("all tests passed")

run_tests()