Choosing a solution

Constraints are part of the problem statement. “n ≤ 10⁵” and “1 second” already rule out most O(n²) solutions. Reading them first can save hours of designing an approach that cannot possibly be fast enough.

Ask five questions: how large can n be, what is the value range (does it fit in int?), is the input sorted, can there be duplicates, and are there multiple queries over the same data?

Assume roughly 10⁸ to 10⁹ simple operations per second in Java. Dividing that by the time limit gives a budget, and the input size tells you which growth classes fit within it. Use the calculator to see where each class crosses one second.

These limits are rules of thumb: the constant factor, memory access pattern and JVM warm-up all matter.

A time limit is a budget for the whole program: reading input, computing and printing. For large inputs, slow input and output alone can exceed it, which is why Chapter 2 covers fast readers and StringBuilder/PrintWriter.

If your solution is the right complexity but still too slow, look at constant factors: boxing, HashMap instead of arrays, allocation inside loops and repeated string concatenation.

Estimate memory from the sizes of the types: an int[] of n elements takes about 4n bytes plus a 16-byte header, a long[] 8n, and a boolean[] n. Boxed collections are far larger: an ArrayList<Integer> stores a reference per element plus a separate 16-byte Integer object, and a HashMap<Integer, Integer> entry costs roughly 50-80 bytes.

So 10⁷ ints are about 40 MB as int[] but several hundred MB as List<Integer>. If the limit is tight, prefer primitive arrays.

How the data is accessed picks the structure: by position (array), by key (hash map), in sorted order or by range (tree map), always the smallest (heap), first-in first-out (queue), last-in first-out (stack), or by connection (graph).

Write down the three operations your program does most and choose the structure that makes those cheapest.

Count how often each operation happens, not only how expensive it is. Many reads and few writes favour structures that precompute (sorted array + binary search, prefix sums). Many inserts and few reads favour structures that make inserts cheap (hash set, heap, linked structures).

A query-heavy workload can justify an O(n log n) preprocessing step that makes each of a million queries O(1) or O(log n).

Before submitting, run through the same list every time: empty input, a single element, all elements equal, already sorted and reverse sorted, negative numbers and zero, the maximum and minimum values (overflow), duplicates, and the smallest input that exercises each branch.

Many wrong answers on a first try fail on exactly one of these.

1static int maxOf(int[] a) {
2    if (a.length == 0) throw new IllegalArgumentException("empty array");   // decide, do not guess
3    int best = a[0];                                                     // not 0: all values may be negative
4    for (int x : a) best = Math.max(best, x);
5    return best;
6}

Every choice trades something: time for memory (a hash map speeds up lookups and uses more memory), simplicity for speed (brute force versus a clever structure), and build time for query time (sort once, search many times).

The two-sum pair below shows it. The brute force uses O(1) extra memory and O(n²) time; the hash map version uses O(n) memory and O(n) time. Neither is “better”; the constraints decide.

1public static int[] twoSum(int[] nums, int target) {
2    for (int i = 0; i < nums.length; i++) {
3        for (int j = i + 1; j < nums.length; j++) {
4            if (nums[i] + nums[j] == target) {
5                return new int[] { i, j };
6            }
7        }
8    }
9    return new int[] { -1, -1 };
10}

1public static int[] twoSum(int[] nums, int target) {
2    Map<Integer, Integer> seen = new HashMap<>();      // value -> index
3    for (int i = 0; i < nums.length; i++) {
4        int need = target - nums[i];
5        if (seen.containsKey(need)) {
6            return new int[] { seen.get(need), i };
7        }
8        seen.put(nums[i], i);
9    }
10    return new int[] { -1, -1 };
11}