Skip to main content
CodePeet

CodePeet 444 Complete DSA Sheet

Java for DSA

Editorial

A few tools, and the one slow move in each

A data-structures solution in Java leans on a handful of classes from java.util: arrays and ArrayList, String and StringBuilder, HashMap and HashSet, ArrayDeque, PriorityQueue, and TreeMap. It's everything a solution needs, a sorted map and a heap included, and each class is still slow at one thing that looks harmless. On our judge, removing the front of an ArrayList of 100,000, one at a time, took 453 ms; an ArrayDeque did it in 11 ms. Building a 100,000-letter string with += took 796 ms; a StringBuilder, 2 ms.

This lesson covers each tool's fast moves and its slow one, then Java's two traps, numbers that wrap and objects that pretend to be numbers, the main thread's stack, and what the judge runs: Java 25.

Six dashed panels in two rows, each a Java class drawn as the shape of its data, with a green pill for its fast move and a red pill for its slow one. ArrayList: tiles 5, 3, 8, 1 and an empty slot at the end with an arrow into it; end: 1 step, front: shifts all. StringBuilder: tiles c, o, d, e and a padlock; append: 1 step, String +=: copies. HashMap, HashSet: keys the and cat pointing to 2 and 1; lookup: 1 step, missing key: null. ArrayDeque: tiles 2, 3, 4 with arrows into both ends; both ends: 1 step, no index access. PriorityQueue: a small heap of 1 over 2 and 4, with 5 below; offer, poll: log n, contains: scans. TreeMap: a small search tree of 31 over 25 and 40, with 20 below 25; floorKey: log n, every op: log n. Focal line: know the slow move before it costs a submission. Title: each class has one slow move.

The shape of a solution

Every program on the judge is a class named Main with a main method; helpers are static methods beside it, and import java.util.*; brings in the collections. Problems that call your method directly wrap it the same way:

import java.util.*;

public class Main {
    static int sum(int[] nums) {             // a helper is a static method next to main
        int total = 0;
        for (int x : nums) total += x;
        return total;
    }

    public static void main(String[] args) {
        int[] nums = {5, 3, 8};
        System.out.println(sum(nums) + " " + nums.length);
    }
}

From here on, most blocks show only what goes inside main; the class around it is the same as above.

Arrays and ArrayList: cheap at the end, slow at the front

An array has a fixed size and holds primitives, every slot starting at 0, false or null. An ArrayList grows as you add, and holds objects, so a list of numbers is a List<Integer>. Both are one row of slots: reading by index and adding or removing at the end take one step, and the front moves every value:

int[] fixed = new int[3];                   // a fixed size; every slot starts at 0
fixed[1] = 7;
List<Integer> nums = new ArrayList<>(List.of(5, 3, 8));
nums.add(1);                                // at the end: O(1)
int last = nums.remove(nums.size() - 1);    // from the end: O(1)
nums.add(0, 9);                             // at the front: every value moves, O(n)
int first = nums.remove(0);                 // O(n) again
System.out.println(Arrays.toString(fixed) + " " + nums + " " + last + " " + first);
int[][] grid = new int[2][3];               // each row its own array
grid[0][1] = 7;
System.out.println(Arrays.deepToString(grid));

Removing the front 100,000 times took 453 ms; the stacks-and-queues section has the class built for the front. new int[rows][cols] gives every row its own array.

Strings: build them with StringBuilder

A String can't change. s += "a" makes a new string and copies the old one into it, so a loop of them copies more and more. StringBuilder appends in place and becomes a string once, at the end. Read a letter with charAt, and compare strings with equals: == asks whether two strings are the same object:

String s = "code";
System.out.println(s.charAt(0) + " " + s.charAt(s.length() - 1) + " " + s.substring(1, 3) + " " + s.length());
StringBuilder sb = new StringBuilder();     // grows in place
for (char ch : s.toCharArray()) sb.append(Character.toUpperCase(ch));
System.out.println(sb);
System.out.println(('c' - 'a') + " " + (char) ('a' + 2));   // letters as numbers and back
String t = new String("code");
System.out.println((s == t) + " " + s.equals(t));          // == compares objects, equals the letters

For 100,000 letters, += took 796 ms and StringBuilder 2 ms.

HashMap and HashSet: lookups that don't scan

A HashMap maps keys to values and a HashSet holds keys alone; both hash the key, so adding, finding and removing take one step on average. merge(key, 1, Integer::sum) counts, getOrDefault reads a missing key safely, computeIfAbsent starts a list for a new key, and add on a set returns false when the value was already there. A TreeMap does the same jobs with its keys kept in order:

String[] words = "the cat and the hat".split(" ");
Map<String, Integer> count = new HashMap<>();
for (String w : words) count.merge(w, 1, Integer::sum);   // add 1, starting from 1
System.out.println(count.get("the") + " " + count.getOrDefault("dog", 0));
Map<Character, List<String>> byFirst = new TreeMap<>();   // a TreeMap prints its keys in order
for (String w : words) byFirst.computeIfAbsent(w.charAt(0), k -> new ArrayList<>()).add(w);
System.out.println(byFirst);
Set<String> seen = new HashSet<>();
List<String> repeats = new ArrayList<>();
for (String w : words) if (!seen.add(w)) repeats.add(w);   // add returns false if it was already there
System.out.println(repeats);

contains on a list checks the values one by one: 5,000 hits among 10,000 lookups in a list of 100,000 took 1,361 ms, and 0.9 ms in a HashSet.

ArrayDeque for stacks and queues

ArrayDeque is a ring of slots open at both ends: push, pop and peek make it a stack, offer and poll a queue, all in one step. Use it instead of Stack, an old class that locks on every call, and instead of LinkedList, which builds an object for every value:

Deque<Integer> stack = new ArrayDeque<>();
stack.push(1);
stack.push(2);
stack.push(3);
System.out.println(stack.pop() + " " + stack.peek());   // the top: last in, first out
Queue<Integer> queue = new ArrayDeque<>(List.of(1, 2, 3));
queue.offer(4);                             // join at the back
System.out.println(queue.poll() + " " + queue);         // leave from the front, O(1)

500,000 offer calls and 500,000 poll calls took 18 ms with an ArrayDeque and 42 ms with a LinkedList, the best of five runs each, once the JIT had warmed up.

PriorityQueue: a min-heap, or any order you give it

PriorityQueue keeps the smallest on top: offer and poll take O(log n) steps, peek one. For the largest first, give it Comparator.reverseOrder(); for anything else, a comparator that says which of two items goes first. Chain them with thenComparing to break ties:

PriorityQueue<Integer> heap = new PriorityQueue<>(List.of(5, 1, 4, 2));
heap.offer(3);
System.out.println(heap.poll() + " " + heap.peek());    // the smallest, then the next
PriorityQueue<Integer> largest = new PriorityQueue<>(Comparator.reverseOrder());
largest.addAll(List.of(5, 1, 4, 2));
System.out.println(largest.peek());
String[] names = {"email", "deploy", "lunch"};
int[] priority = {2, 1, 2};
PriorityQueue<Integer> jobs = new PriorityQueue<>(   // by priority, then by arrival
        Comparator.comparingInt((Integer i) -> priority[i]).thenComparingInt(i -> i));
for (int i = 0; i < names.length; i++) jobs.offer(i);
StringBuilder order = new StringBuilder();
while (!jobs.isEmpty()) order.append(names[jobs.poll()]).append(' ');
System.out.println(order.toString().trim());

TreeMap and TreeSet: sorted, with floor and ceiling

A TreeMap keeps its keys in order in a balanced tree, so every operation takes O(log n), and it answers the questions a hash map can't: the largest key at or below x (floorKey), the smallest at or above (ceilingKey), the first and the last. TreeSet does the same for values. Python's standard library has nothing like it:

TreeMap<Integer, String> byAge = new TreeMap<>(Map.of(25, "bo", 31, "ana", 40, "cy"));
System.out.println(byAge.floorKey(30) + " " + byAge.ceilingKey(30) + " " + byAge.firstKey());
TreeSet<Integer> ages = new TreeSet<>(List.of(25, 31, 40));
System.out.println(ages.higher(31) + " " + ages.lower(25));   // null: nothing is lower

Sorting with comparators

Arrays.sort on an array of primitives is fast and takes no comparator. Lists and arrays of objects sort with a Comparator, and that sort is stable, so items that compare equal keep their order. Build comparators from parts with comparingInt, reversed and thenComparing instead of writing the arithmetic yourself; the bugs section shows why:

record Person(String name, int age) {}
List<Person> people = new ArrayList<>(List.of(new Person("ana", 31), new Person("bo", 25), new Person("cy", 31)));
people.sort(Comparator.comparingInt(Person::age));          // stable: ana stays before cy
System.out.println(people.stream().map(Person::name).toList());
people.sort(Comparator.comparingInt(Person::age).reversed().thenComparing(Person::name));
System.out.println(people.stream().map(Person::name).toList());
int[] nums = {5, 3, 8, 1};
Arrays.sort(nums);                          // primitives: fast, no comparator
System.out.println(Arrays.toString(nums) + " " + Arrays.binarySearch(nums, 5));

Numbers that wrap

An int holds up to 2,147,483,647, and going past it doesn't fail: it wraps around to a negative number. long reaches about 9.2 × 10^18. Widen before you multiply, since n * n is computed in int before anything sees it. / and % cut towards zero, and Math.floorDiv and floorMod floor instead. Math.addExact throws rather than wrap, which is handy while testing:

int big = Integer.MAX_VALUE;
System.out.println(big + 1);                // wraps around, silently
int n = 100_000;
System.out.println(n * n + " " + (long) n * n);   // widen before multiplying
System.out.println(-7 / 2 + " " + -7 % 2);  // both cut towards zero
System.out.println(Math.floorDiv(-7, 2) + " " + Math.floorMod(-7, 2));
try {
    Math.addExact(big, 1);
} catch (ArithmeticException e) {
    System.out.println("overflow caught");
}

Boxing: an Integer is an object

Collections hold objects, so an int going into a List<Integer> is boxed into an Integer and unboxed on the way out. That costs time, and it changes what == means. Java keeps one shared Integer for each value from -128 to 127, so two boxed 127s are the same object and two boxed 128s are two objects:

Integer a = 127, b = 127, c = 128, d = 128;
System.out.println((a == b) + " " + (c == d) + " " + c.equals(d));
int sum = c + d;                            // unboxed for arithmetic
System.out.println(sum);
Two dashed panels. Left, titled boxing 127: two slate tiles, a = 127 and b = 127, each with a green arrow to the same single green tile 127, with a pill reading cached under it; a ticked card below reads a == b: true, one object, so == holds. Right, titled boxing 128: tiles c = 128 and d = 128, each with a red arrow to a red tile 128 of its own, with a pill reading a new one each time; a crossed card below reads c == d: false, two objects, c.equals(d): true. Focal line: compare boxed numbers with equals, never ==. Title: two 128s are two objects.

Compare boxed values with equals, or unbox them first. Summing a million numbers took 0.3 ms from an int[] and 1.2 ms from a List<Integer>: when a loop is hot, keep primitives in arrays.

Recursion: the main thread's stack is small

On our judge, a recursion 21,875 calls deep finished on the main thread and one 23,281 deep threw StackOverflowError, far short of a 100,000-node chain. A thread of your own can have a bigger stack: give its size in bytes when you create it, run the recursion inside it, and wait for it with join:

import java.util.*;

public class Main {
    static int depth(int n) {
        return n == 0 ? 0 : depth(n - 1) + 1;
    }

    public static void main(String[] args) throws Exception {
        int[] result = new int[1];
        Thread worker = new Thread(null, () -> result[0] = depth(1_000_000), "deep", 1L << 28);   // a 256 MB stack
        worker.start();
        worker.join();
        System.out.println(result[0]);
    }
}

A million frames ran with a 256 MB stack. For deeper inputs still, use an explicit stack: Depth-First and Breadth-First Search shows the iterative version.

What our judge runs

The judge runs Java 25, so records, List.of and var all work. Most problems call your method directly; a problem that reads its own input should read with a BufferedReader, which needs import java.io.*;:

BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(in.readLine().trim());
long total = 0;
for (int i = 0; i < n; i++) total += Integer.parseInt(in.readLine().trim());
System.out.println(total);

Reading 200,000 lines took 113 ms with BufferedReader and 752 ms with Scanner, which parses every token with patterns.

Pick the collection for the job

Below, each job is a mix of operations repeated 100,000 times. Pick the Java class you'd use; each operation's cost appears with the total work for the whole job, and every class you try keeps its verdict, so you can compare them.

Which Collection? Java

Bugs that cost a submission

A comparator that subtracts.

Integer[] vals = {2_000_000_000, -2_000_000_000, 0};
Arrays.sort(vals, (x, y) -> x - y);         // 2,000,000,000 - (-2,000,000,000) wraps to a negative
System.out.println(Arrays.toString(vals));
Arrays.sort(vals, Integer::compare);
System.out.println(Arrays.toString(vals));

It printed [2000000000, -2000000000, 0] first: 2,000,000,000 minus -2,000,000,000 is 4,000,000,000, which wraps to a negative, so the comparator says the big value comes first. Integer::compare printed [-2000000000, 0, 2000000000].

Top panel, titled −2,000,000,000 − 2,000,000,000 in int: a number line from −2,147,483,648 to 2,147,483,647 with 0 in the middle; a pill on the left reads −4,000,000,000: off the end, and a red dot just right of 0 has a pill reading wraps to +294,967,296; under the line, positive, so the sort keeps −2,000,000,000 after 2,000,000,000. Bottom panel, titled the array, sorted: next to x - y, red tiles 2,000,000,000, −2,000,000,000, 0 with a cross; next to Integer::compare, green tiles −2,000,000,000, 0, 2,000,000,000 with a tick. Focal line: compare with Integer.compare, never with a − b. Title: a comparator that subtracts wraps around.

remove with an int.

List<Integer> nums = new ArrayList<>(List.of(5, 42, 7));
nums.remove(42);                            // an int: the element at index 42

It threw IndexOutOfBoundsException: on a List<Integer>, remove(42) means the element at index 42. Remove the value with remove(Integer.valueOf(42)).

Adding to Arrays.asList.

List<Integer> nums = Arrays.asList(1, 2);
nums.add(3);                                // a fixed-size view of an array

It threw UnsupportedOperationException: the list is a fixed-size view of an array. Copy it into new ArrayList<>(...) first.

Unboxing a missing key.

Map<String, Integer> count = new HashMap<>();
int c = count.get("dog");                   // null, unboxed into an int

It threw NullPointerException: get returned null, and null can't become an int. Use getOrDefault(key, 0).

Check yourself

Quiz

1 / 6

Multiple choice

Integer a = 200, b = 200; What does a == b give?

Practice problems

This section's problems, in Java:

  1. Reading & Printing Values: read with a BufferedReader.
  2. Linear Search and Check if an Array is Sorted: an int[] by index.
  3. Reverse an Array In Place: two indices and a swap.
  4. Count Vowels and Consonants and Toggle Case: charAt and a StringBuilder.
  5. Count Words in a Sentence: split, then a HashMap with merge.
  6. Java Collections Framework: the classes above, side by side.

Then Introduction to Recursion, before the patterns.