Fast input and output for online judges

How to read the input HackerRank, CodeChef and company OAs send on stdin, and print the answer fast enough to pass the time limit.

Topic 23 of 98 · 5 min to read · 50 min to build

After this topic you can

Read T test cases of "n, then n numbers" with bufio.NewReader and fmt.Fscan.
Print answers through bufio.NewWriter and explain why defer Flush() is needed.
Read very long lines with bufio.Scanner and Buffer, and words with ScanWords.

Why this comes first

On LeetCode you write a function and the site calls it. On HackerRank, CodeChef, Codeforces and most company online assessments (OAs), you write a whole program. The judge sends the input on standard input (stdin) and reads your answer from standard output (stdout).

A correct solution can still fail with "Time Limit Exceeded" only because it reads and prints slowly. In Go the fix is two lines, and it is the same every time.

Why plain fmt.Scan is slow

fmt.Scan(&x) reads straight from os.Stdin, which is not buffered. To find where one number ends it asks the operating system for one byte at a time. Each ask is a system call, and 1,000,000 numbers means millions of them.
fmt.Println has the same problem in reverse: every call is a separate write to the terminal or pipe.
bufio.NewReader(os.Stdin) asks for 4096 bytes at once and hands them out from memory. bufio.NewWriter(os.Stdout) collects your output and writes it in big chunks. Same fmt functions, just with an F in front: fmt.Fscan(in, &x), fmt.Fprintln(out, x).

The template: T cases, each "n then n numbers"

This is the most common input shape. The first number is T, the number of test cases. Each case starts with n, followed by n numbers. fmt.Fscan skips spaces and newlines alike, so it does not matter how the numbers are split across lines.

Writing the logic as solve(r io.Reader, w io.Writer) lets you test it with strings.NewReader (a string that behaves like stdin) instead of typing input by hand. On the judge, main just calls solve(os.Stdin, os.Stdout).

fast_io.go

1package main
2
3import (
4	"bufio"
5	"fmt"
6	"io"
7	"os"
8	"strings"
9)
10
11// solve is the whole answer. It takes a reader and a writer instead of
12// os.Stdin and os.Stdout, so you can feed it a string while you practise.
13func solve(r io.Reader, w io.Writer) {
14	in := bufio.NewReader(r)  // reads 4096 bytes at a time, not 1
15	out := bufio.NewWriter(w) // collects output, writes it in big chunks
16	defer out.Flush()         // forget this and nothing is printed
17
18	var t int
19	fmt.Fscan(in, &t) // first line: the number of test cases
20	for ; t > 0; t-- {
21		var n int
22		fmt.Fscan(in, &n) // each case: n, then n numbers
23		sum := 0
24		for i := 0; i < n; i++ {
25			var x int
26			fmt.Fscan(in, &x) // Fscan skips spaces AND newlines
27			sum += x
28		}
29		fmt.Fprintln(out, sum)
30	}
31}
32
33func main() {
34	// On the judge you would call solve(os.Stdin, os.Stdout).
35	// Here a string stands in for the input the judge would send.
36	input := "3\n3\n1 2 3\n2\n-5 5\n4\n10 20 30 40\n"
37	solve(strings.NewReader(input), os.Stdout)
38	// 6
39	// 0
40	// 100
41}

Watch out: Forgetting `Flush` prints nothing. A bufio.Writer keeps up to 4096 bytes in memory. If the program ends before you flush, that output is lost and the judge sees an empty answer: "Wrong Answer" on a correct solution. Put defer out.Flush() on the line right after you create it.

Whole lines and very long lines: bufio.Scanner

When the input is text lines (names, sentences, a grid of characters), bufio.Scanner reads one line per Scan(). Two things to know: its default line limit is 64 KB, and when a line is longer it just stops, with the error only in sc.Err(). sc.Buffer(buf, max) raises the limit. sc.Split(bufio.ScanWords) makes it return one word at a time instead of one line.

scanner.go

1package main
2
3import (
4	"bufio"
5	"fmt"
6	"strings"
7)
8
9func main() {
10	input := "hello world from go\nsecond line\n"
11
12	// Line by line. The default limit is 64 KB per line; a long line
13	// (say 1,000,000 numbers on one line) silently stops the scan.
14	// Buffer raises the limit, here to 1 MB.
15	sc := bufio.NewScanner(strings.NewReader(input))
16	sc.Buffer(make([]byte, 1024*1024), 1024*1024)
17	for sc.Scan() {
18		fmt.Printf("line: %q\n", sc.Text())
19	}
20
21	// Word by word, ignoring line breaks: handy for "read n numbers".
22	ws := bufio.NewScanner(strings.NewReader(input))
23	ws.Split(bufio.ScanWords)
24	count := 0
25	for ws.Scan() {
26		count++
27	}
28	fmt.Println("words:", count) // words: 6
29}

Which one to use

input looks like	use
numbers separated by spaces or newlines	`bufio.NewReader` + `fmt.Fscan`
whole lines of text	`bufio.Scanner` (+ `Buffer` if a line can pass 64 KB)
millions of numbers, tight time limit	`bufio.Scanner` with `ScanWords` + `strconv.Atoi`, the fastest of the three
any output	`bufio.NewWriter` + `defer Flush()`

The short version

Online judges send input on stdin and read your answer from stdout.
fmt.Scan on bare stdin reads one byte per system call. Wrap stdin in bufio.NewReader and use fmt.Fscan.
Wrap stdout in bufio.NewWriter and defer out.Flush(), or the output is lost.
bufio.Scanner stops silently on a line over 64 KB unless you call Buffer.
Put the logic in solve(r io.Reader, w io.Writer) so you can test it with strings.NewReader.

Remember: Buffered in, buffered out, and Flush before you leave.

Build this before moving on

Write a program for this input: T, then for each case a line with n, then n numbers. Print the largest number of each case. Test it with strings.NewReader first, then with real stdin: go run . < input.txt.

Coding challenge · checked by tests

Write Solve(r io.Reader, w io.Writer). The input is T, then T test cases; each case is n followed by n integers (spaces and newlines may be mixed freely). Print the sum of each case on its own line. Read through bufio.NewReader and write through bufio.NewWriter with defer Flush(): the hidden tests count your Read and Write calls on a big input. Example: "2\n3\n1 2 3\n2\n-5 5\n" → "6\n0\n".

Tab indents. Press Esc, then Tab, to leave the editor.

Then try these in your own editor

1Delete the defer out.Flush() line from the example and run it. What is printed?
2The input is one line with n and then n names on the next line. Which reader do you pick, and why?
3A problem gives 1,000,000 numbers on a single line and your bufio.Scanner loop reads none of them. What went wrong and what is the fix?
4Why does the example take io.Reader and io.Writer instead of using os.Stdin and os.Stdout directly?

Official documentation

Check yourselfTake the Go for coding rounds test