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

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

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

| Item | Meaning |
|---|---|
| Input | Destination buffer `buf` and integer `n` |
| Output | Number of characters written into `buf` |
| Given API | `read4(buf4)` |
| `read4` result | Reads between `0` and `4` characters |
| Main challenge | Preserve unused characters across calls |

Example method shape:

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

## Examples

Example 1:

```text
file = "abc"
```

Calls:

```python
read(buf, 1)
read(buf, 2)
read(buf, 1)
```

The first call reads:

```text
"a"
```

and returns:

```python
1
```

The second call reads:

```text
"bc"
```

and returns:

```python
2
```

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

```python
0
```

Example 2:

```text
file = "abc"
```

Call:

```python
read(buf, 4)
```

The file only has 3 characters, so it reads:

```text
"abc"
```

and returns:

```python
3
```

A later call:

```python
read(buf, 1)
```

returns:

```python
0
```

## First Thought: Reuse the LeetCode 157 Solution

For LeetCode 157, `read` is called only once.

So we could do this:

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

Then copy only the needed characters into `buf`.

That breaks when `read` is called multiple times.

Consider:

```text
file = "abcdef"
```

First call:

```python
read(buf, 1)
```

If we call `read4`, it reads:

```text
"abcd"
```

But we only need:

```text
"a"
```

The leftover characters:

```text
"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:

| Variable | Meaning |
|---|---|
| `self.buf4` | Internal buffer of size 4 |
| `self.i4` | Current read position inside `self.buf4` |
| `self.n4` | Number of valid characters currently inside `self.buf4` |

When:

```python
self.i4 < self.n4
```

there are leftover characters available.

When:

```python
self.i4 == self.n4
```

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

## Algorithm

Initialize the internal state in the constructor:

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

```text
file = "abcdef"
```

Call 1:

```python
read(buf, 1)
```

Internal buffer is empty, so we call `read4`.

`self.buf4` becomes:

```text
"abcd"
```

and:

```python
self.n4 = 4
self.i4 = 0
```

We only need one character.

Copy:

```text
"a"
```

Now:

```python
self.i4 = 1
```

Return:

```python
1
```

The internal buffer still has:

```text
"bcd"
```

Call 2:

```python
read(buf, 3)
```

Now:

```python
self.i4 = 1
self.n4 = 4
```

So we copy from the old buffer first:

```text
"bcd"
```

Now:

```python
self.i4 = 4
```

Return:

```python
3
```

Call 3:

```python
read(buf, 2)
```

Internal buffer is empty, so we call `read4`.

It reads:

```text
"ef"
```

and returns:

```python
2
```

We copy both characters and return:

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

| Metric | Value | Why |
|---|---|---|
| Time | `O(k)` | Each returned character is copied once |
| Space | `O(1)` | The internal buffer has fixed size 4 |

## Implementation

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

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

```python
i = 0
```

When the internal buffer has no available characters:

```python
if self.i4 == self.n4:
```

we refill it:

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

If no characters were read:

```python
if self.n4 == 0:
    break
```

the file has ended.

Otherwise, we copy one character:

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

Then we advance both pointers:

```python
i += 1
self.i4 += 1
```

Finally:

```python
return i
```

returns how many characters were copied during this call.

## 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 __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()
```

| Test | Why |
|---|---|
| `"abc"` with calls `1, 2, 1` | Checks leftover reuse and EOF |
| `"abc"` with calls `4, 1` | Reads fewer than requested at EOF |
| `"abcdef"` with calls `1, 3, 2, 1` | Checks buffered leftovers across calls |
| `"abcdefghijk"` with calls `4, 4, 4` | Checks multiple full `read4` batches |