Reading Input Fast

The problem with Scanner

Scanner is the class most Java courses teach for reading input. It is convenient and it is slow. On a problem with 200,000 numbers, Scanner can spend more time parsing input than your algorithm spends solving the problem.

The reason is that Scanner uses regular expressions to find token boundaries and does not buffer aggressively. Both are fine for reading a handful of values from a keyboard. Neither is fine for reading a few hundred thousand integers from a file.

This is the single most common cause of a Java solution timing out when the algorithm was correct. It is worth fixing once and then never thinking about again.

BufferedReader with split

The straightforward replacement. Read a whole line, split it on whitespace, parse each piece.

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(in.readLine().trim());

        // A line of n space-separated integers
        StringTokenizer st = new StringTokenizer(in.readLine());
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = Integer.parseInt(st.nextToken());
        }

        long sum = 0;
        for (int x : a) sum += x;
        System.out.println(sum);
    }
}

StringTokenizer is used instead of String.split because split compiles a regular expression each call. For one line it does not matter; inside a loop over 200,000 lines it does.

StreamTokenizer for numbers

When the input is entirely numeric, StreamTokenizer is both the fastest option and the one that ignores line structure completely. It reads tokens one at a time regardless of how they are laid out.

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(
            new BufferedInputStream(System.in));

        in.nextToken();
        int n = (int) in.nval;

        long sum = 0;
        for (int i = 0; i < n; i++) {
            in.nextToken();
            sum += (long) in.nval;
        }
        System.out.println(sum);
    }
}

Each nextToken() advances the reader; the value lands in the nval field as a double, which you cast.

Writing output fast

Output has the same problem in reverse. System.out.println flushes on every call, and 200,000 flushes is slow.

Wrap it, write everything, then flush once:

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        PrintWriter out = new PrintWriter(new BufferedWriter(
            new OutputStreamWriter(System.out)));

        for (int i = 1; i <= 200000; i++) {
            out.println(i);
        }

        out.flush();   // required — without this, nothing is printed
    }
}

Forgetting flush() produces no output at all, which looks like a crash. If your program runs and prints nothing, check for a missing flush first.

For very large outputs, building a StringBuilder and printing it once is faster still:

StringBuilder sb = new StringBuilder();
for (int i = 1; i <= 200000; i++) {
    sb.append(i).append('\n');
}
System.out.print(sb);

A template to start from

Keep this in a file and copy it at the start of each problem.

import java.io.*;
import java.util.*;

public class Main {
    static StreamTokenizer in = new StreamTokenizer(
        new BufferedInputStream(System.in));
    static PrintWriter out = new PrintWriter(new BufferedWriter(
        new OutputStreamWriter(System.out)));

    static int nextInt() throws IOException {
        in.nextToken();
        return (int) in.nval;
    }

    static long nextLong() throws IOException {
        in.nextToken();
        return (long) in.nval;
    }

    public static void main(String[] args) throws IOException {
        int n = nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) a[i] = nextInt();

        // solve here

        out.flush();
    }
}

Which reader to use

Next