LeetCode 157 – Read N Characters Given Read4

Read N Characters Given Read4 is an API-adaptation problem: you are handed a primitive that reads in fixed 4-character chunks and asked to expose one that reads exactly n. The algorithm is a loop. What is being tested is whether you handle the two ways the chunk size and n fail to line up — and whether you know what a short read means.

The problem

read4(buf4) reads up to 4 characters from a file into buf4 and returns how many it actually read. Using only that, implement read(buf, n), which reads up to n characters into buf and returns how many it read.

read is called once. (Being called repeatedly is problem 158, and it is a materially different problem.)

file = "abc",     n = 4   -> 3, buf = "abc"      fewer characters than asked
file = "abcde",   n = 5   -> 5, buf = "abcde"
file = "abcdABCD1234", n = 12 -> 12
file = "leetcode", n = 5  -> 5, buf = "leetc"    MORE available than asked
file = "",        n = 1   -> 0

A short read means end of file

read4 returning fewer than 4 is the only signal you get that the file is exhausted. It is not "try again" and it is not a partial-read hiccup — the contract says it reads 4 unless there are fewer than 4 left.

So read4 returning 0 is the loop's exit condition, and returning 1–3 means this is the last chunk. Getting this wrong gives an infinite loop on a short file, which is the failure mode worth naming out loud.

The two mismatches

n = 5, file = "abcdefgh"

read4 -> "abcd" (4)     total 4, still short of 5
read4 -> "efgh" (4)     but only ONE more character is wanted

  copying all four would write past n.

The chunk you are handed can overshoot n, and the file can run out before n. Both need guarding, and the copy loop can do it with one condition each:

for (i = 0; i < count && total < n; i++)
              ^^^^^^^^^      ^^^^^^^^^
              file limit     caller's limit

Writing past n is a buffer overrun into memory the caller owns. In a real codebase that is a security bug, not a wrong answer — worth saying, because it is the reason the guard is not optional.

Java

class Solution extends Reader4 {
    public int read(char[] buf, int n) {
        char[] buf4 = new char[4];
        int total = 0;

        while (total < n) {
            int count = read4(buf4);
            if (count == 0) break;           // short read of 0 = end of file

            // Two limits: what the file gave us, and what the caller asked for.
            for (int i = 0; i < count && total < n; i++) {
                buf[total++] = buf4[i];
            }
        }

        return total;
    }
}

buf4 is allocated once outside the loop rather than per iteration. It is reused every call to read4, which overwrites it — no state carries between iterations, and there is no reason to allocate n/4 arrays.

The outer total < n and the inner total < n look redundant and are not. The outer one stops fetching more chunks; the inner one stops copying within the chunk you already have. Drop the inner and you overrun; drop the outer and you read one chunk too many from the file, which matters when the file is a stream.

Note that n characters may be consumed from the file even though fewer are copied out — the final read4 can fetch 4 and use 1. For a single call that is harmless. For problem 158 it is the entire difficulty.

Python

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

        while total < n:
            count = read4(buf4)
            if count == 0:                    # end of file
                break

            for i in range(min(count, n - total)):
                buf[total] = buf4[i]
                total += 1

        return total

min(count, n - total) states both limits in one expression — what the file supplied and what the caller still wants. It reads more directly than two loop conditions, and it makes the overshoot case impossible to write incorrectly.

Complexity

	Time	Space
Chunked read	`O(n)`	`O(1)` — one 4-character buffer

At most ⌈n/4⌉ calls to read4, each doing constant work. The scratch buffer is 4 characters regardless of n, which is the point of the design — you never hold the whole file.

Why this problem exists

It is not really about LeetCode's read4. It is the shape of every buffered-I/O wrapper ever written: an underlying source that delivers whatever it feels like, a caller that wants a specific amount, and a layer in between reconciling the two. InputStream.read in Java and read(2) in C both return "up to" a count for the same reason, and misreading that as "exactly" is a classic production bug.

Say that if it comes up. It reframes the question from a puzzle into the thing it is modelling, and it makes the follow-up about buffering leftovers feel inevitable rather than arbitrary.

What the interviewer is checking

That a short read means end of file, and drives the exit condition.
Both guards — the chunk's count and the caller's n.
That you never write past n into the caller's buffer.
n larger than the file, and n smaller than one chunk.
An empty file returning 0.
That buf4 is allocated once.
That you notice characters can be consumed but not delivered — which sets up problem 158.