Skip to content

157. Read N Characters Given Read4 👎

Approach 1: $O(2(R + W))$

  • Time: $O(n)$
  • Space: $O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/**
 * The read4 API is defined in the parent class Reader4.
 *     int read4(char *buf4);
 */

class Solution {
 public:
  /**
   * @param buf Destination buffer
   * @param n   Number of characters to read
   * @return    The number of actual characters read
   */
  int read(char* buf, int n) {
    char* buf4 = new char[4];
    int i4 = 0;  // buf4's index
    int n4 = 0;  // buf4's size
    int i = 0;   // buf's index

    while (i < n) {
      if (i4 == n4) {      // All the characters in the buf4 are consumed.
        i4 = 0;            // Reset the buf4's index.
        n4 = read4(buf4);  // Read <= 4 characters from the file to the buf4.
        if (n4 == 0)       // Reach the EOF.
          return i;
      }
      buf[i++] = buf4[i4++];
    }

    return i;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
 * The read4 API is defined in the parent class Reader4.
 *     int read4(char[] buf4);
 */

public class Solution extends Reader4 {
  /**
   * @param buf  Destination buffer
   * @param n    Number of characters to read
   * @return The number of actual characters read
   */
  public int read(char[] buf, int n) {
    char[] buf4 = new char[4];
    int i4 = 0; // buf4's index
    int n4 = 0; // buf4's size
    int i = 0;  // buf's index

    while (i < n) {
      if (i4 == n4) {     // All the characters in the buf4 are consumed.
        i4 = 0;           // Reset the buf4's index.
        n4 = read4(buf4); // Read <= 4 characters from the file to the buf4.
        if (n4 == 0)      // Reach the EOF.
          return i;
      }
      buf[i++] = buf4[i4++];
    }

    return i;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
"""
The read4 API is already defined for you.
  def read4(buf4: list[str]) -> int:

# Below is an example of how the read4 API can be called.
file = File("abcdefghijk") # File is "abcdefghijk", initially file pointer (fp) points to 'a'
buf4 = [' '] * 4 # Create buffer with enough space to store characters
read4(buf4) # Read4 returns 4. Now buf = ['a','b','c','d'], fp points to 'e'
read4(buf4) # Read4 returns 4. Now buf = ['e','f','g','h'], fp points to 'i'
read4(buf4) # Read4 returns 3. Now buf = ['i','j','k',...], fp points to end of file
"""


class Solution:
  def read(self, buf: list[str], n: int) -> int:
    buf4 = [' '] * 4
    i4 = 0  # buf4's index
    n4 = 0  # buf4's size
    i = 0  # buf's index

    while i < n:
      if i4 == n4:  # All the characters in the buf4 are consumed.
        i4 = 0  # Reset the buf4's index.
        n4 = read4(buf4)  # Read <= 4 characters from the file to the buf4.
        if n4 == 0:  # Reach the EOF.
          return i
      buf[i] = buf4[i4]
      i += 1
      i4 += 1

    return i

Approach 2: $O(R + W)$

  • Time: $O(n)$
  • Space: $O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
/**
 * The read4 API is defined in the parent class Reader4.
 *     int read4(char *buf4);
 */

class Solution {
 public:
  /**
   * @param buf Destination buffer
   * @param n   Number of characters to read
   * @return    The number of actual characters read
   */
  int read(char* buf, int n) {
    char* buf4 = new char[4];
    int i4 = 0;  // buf4's index
    int n4 = 0;  // buf4's size
    int i = 0;   // buf's index

    // While we're not reaching the tail (< 4 characters).
    while (i + 4 < n) {
      const int k = read4(buf + i);  // Directly write to the buf.
      if (k == 0)                    // Reach the EOF.
        return i;
      i += k;
    }

    while (i < n) {
      if (i4 == n4) {      // All the characters in the buf4 are consumed.
        i4 = 0;            // Reset the buf4's index.
        n4 = read4(buf4);  // Read <= 4 characters from the file to the buf4.
        if (n4 == 0)       // Reach the EOF.
          return i;
      }
      buf[i++] = buf4[i4++];
    }

    return i;
  }
};