# 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:

```python
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:

```python
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

| Item | Meaning |
|---|---|
| Input | Destination buffer `buf` and integer `n` |
| Output | Number of characters actually read |
| Given API | `read4(buf4)` |
| `read4` return value | Number of characters read, from `0` to `4` |
| File access | Only through `read4` |
| Important detail | `read` is called once per test case |

Example method shape:

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

## Examples

Example 1:

```text
file = "abc"
n = 4
```

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

So `buf` should contain:

```text
"abc"
```

The function returns:

```python
3
```

Example 2:

```text
file = "abcde"
n = 5
```

We need all 5 characters.

One call to `read4` reads:

```text
"abcd"
```

The second call reads:

```text
"e"
```

The function returns:

```python
5
```

Example 3:

```text
file = "abcde"
n = 3
```

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

```text
"abcd"
```

But we only copy the first 3 characters into `buf`.

The function returns:

```python
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:

```python
buf4 = [""] * 4
```

Then after each call:

```python
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:

```python
count
```

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

```python
n - total
```

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

```python
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:

```python
buf4 = [""] * 4
```

Set:

```python
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:

```text
file = "abcde"
n = 5
```

Start:

```python
total = 0
```

First call:

```python
count = read4(buf4)
```

`buf4` contains:

```text
"abcd"
```

and:

```python
count = 4
```

We still need 5 characters, so we copy 4.

Now:

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

Second call:

```python
count = read4(buf4)
```

`buf4` contains:

```text
"e"
```

and:

```python
count = 1
```

We still need:

```python
5 - 4 = 1
```

So we copy 1 character.

Now:

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

Return:

```python
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:

```python
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`.

| Metric | Value | Why |
|---|---|---|
| Time | `O(k)` | Each copied character is written once |
| Space | `O(1)` | The temporary buffer always has size 4 |

## Implementation

```python
# 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:

```python
buf4 = [""] * 4
```

This is where `read4` writes its result.

We track how many characters have been copied into `buf`:

```python
total = 0
```

The loop runs until we have copied `n` characters:

```python
while total < n:
```

Each iteration reads up to 4 characters:

```python
count = read4(buf4)
```

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

```python
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:

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

If `read4` returns fewer than 4 characters:

```python
if count < 4:
    break
```

then we reached the end of the file.

Finally:

```python
return total
```

returns the number of characters written into `buf`.

## Testing

LeetCode provides `read4`, but we can simulate it locally.

```python
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()
```

| Test | Why |
|---|---|
| `file = "abc", n = 4` | File shorter than requested |
| `file = "abcde", n = 5` | Needs multiple `read4` calls |
| `file = "abcde", n = 3` | Must copy less than `read4` returns |
| `file = "", n = 2` | Empty file |
| `file = "abcdefg", n = 4` | Exact one full `read4` call |