LeetCode 157: Read N Characters Given Read4

Problem Restatement

We are given a file, but we cannot access the file directly.

The only way to read from the file is through a provided API:

read4(buf4)

This function reads up to 4 characters from the file and writes them into buf4.

It returns the actual number of characters read.

We need to implement:

read(buf, n)

This function should read up to n characters from the file, write them into buf, and return the number of characters actually read.

The file may contain fewer than n characters.

LeetCode states that read4 has its own file pointer, buf4 is a destination buffer, and read will be called only once for each test case. The destination buffer buf has enough space for n characters.

Input and Output

Example method shape:

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

Examples

Example 1:

file = "abc"
n = 4

We ask for 4 characters, but the file contains only 3.

So buf should contain:

"abc"

The function returns:

3

Example 2:

file = "abcde"
n = 5

We need all 5 characters.

One call to read4 reads:

"abcd"

The second call reads:

"e"

The function returns:

5

Example 3:

file = "abcde"
n = 3

One call to read4 may read 4 characters into the temporary buffer:

"abcd"

But we only copy the first 3 characters into buf.

The function returns:

3

First Thought: Keep Calling read4

Since read4 gives us at most 4 characters at a time, we can repeatedly call it until one of two things happens:

1. We have copied n characters into buf.
2. read4 returns fewer than 4 characters, meaning the file has ended.

The important point is that read4 writes into a temporary buffer, not directly into the final answer buffer.

So we need:

buf4 = [""] * 4

Then after each call:

count = read4(buf4)

we copy only the characters we still need.

Key Insight

There are two limits at the same time.

The first limit is how many characters read4 actually returned:

count

The second limit is how many characters the user still wants:

n - total

So after one read4 call, the number of characters we should copy is:

min(count, n - total)

This avoids copying too many characters when n is not a multiple of 4.

Algorithm

Create a temporary buffer of size 4:

buf4 = [""] * 4

Set:

total = 0

While total < n:

1. Call read4(buf4).
2. Let count be the number of characters read.
3. Copy at most min(count, n - total) characters from buf4 to buf.
4. Increase total.
5. If count < 4, stop because the file has ended.

Return total.

Walkthrough

Use:

file = "abcde"
n = 5

Start:

total = 0

First call:

count = read4(buf4)

buf4 contains:

"abcd"

and:

count = 4

We still need 5 characters, so we copy 4.

Now:

buf = ["a", "b", "c", "d"]
total = 4

Second call:

count = read4(buf4)

buf4 contains:

"e"

and:

count = 1

We still need:

5 - 4 = 1

So we copy 1 character.

Now:

buf = ["a", "b", "c", "d", "e"]
total = 5

Return:

5

Correctness

The algorithm copies characters into buf in the same order that read4 returns them.

Each call to read4 advances the file pointer, so repeated calls read consecutive parts of the file.

After each call, the algorithm copies only:

min(count, n - total)

characters.

This means it never writes more than n characters into buf.

If read4 returns fewer than 4 characters, the file has no more characters after that call, so stopping is correct.

If the algorithm reaches total == n, it has read the requested number of characters, so stopping is correct.

Therefore, the returned value is exactly the number of characters copied into buf, which is the number of characters actually read.

Complexity

Let k be the number of characters actually copied, where k <= n.

Implementation

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

class Solution:
    def read(self, buf: List[str], n: int) -> int:
        buf4 = [""] * 4
        total = 0

        while total < n:
            count = read4(buf4)

            chars_to_copy = min(count, n - total)

            for i in range(chars_to_copy):
                buf[total] = buf4[i]
                total += 1

            if count < 4:
                break

        return total

Code Explanation

We create a temporary buffer:

buf4 = [""] * 4

This is where read4 writes its result.

We track how many characters have been copied into buf:

total = 0

The loop runs until we have copied n characters:

while total < n:

Each iteration reads up to 4 characters:

count = read4(buf4)

Then we compute how many of those characters should be copied:

chars_to_copy = min(count, n - total)

This handles cases like n = 3, where read4 might return 4 but we only need 3.

The copy loop writes characters into the destination buffer:

for i in range(chars_to_copy):
    buf[total] = buf4[i]
    total += 1

If read4 returns fewer than 4 characters:

if count < 4:
    break

then we reached the end of the file.

Finally:

return total

returns the number of characters written into buf.

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 read(self, buf: List[str], n: int) -> int:
        buf4 = [""] * 4
        total = 0

        while total < n:
            count = self.read4(buf4)
            chars_to_copy = min(count, n - total)

            for i in range(chars_to_copy):
                buf[total] = buf4[i]
                total += 1

            if count < 4:
                break

        return total

def run_tests():
    sol = Solution("abc")
    buf = [""] * 4
    assert sol.read(buf, 4) == 3
    assert "".join(buf[:3]) == "abc"

    sol = Solution("abcde")
    buf = [""] * 5
    assert sol.read(buf, 5) == 5
    assert "".join(buf[:5]) == "abcde"

    sol = Solution("abcde")
    buf = [""] * 3
    assert sol.read(buf, 3) == 3
    assert "".join(buf[:3]) == "abc"

    sol = Solution("")
    buf = [""] * 2
    assert sol.read(buf, 2) == 0

    sol = Solution("abcdefg")
    buf = [""] * 4
    assert sol.read(buf, 4) == 4
    assert "".join(buf[:4]) == "abcd"

    print("all tests passed")

run_tests()