Java Essentials for DSA

You do not need to know all of Java to learn DSA. Java is huge, with frameworks, annotations and a thousand libraries, and almost all of that is irrelevant for the next 25 articles. What you need is a small, well-understood core.

This article covers exactly that core, and it points out the places where Java behaves differently from what beginners expect. Those places cause far more wrong answers than hard algorithms do.

Version note. The code in this course targets Java 17. It sticks to classic syntax so it also reads easily if you learned an older version. Every complete program in this course was compiled with javac --release 17 and run, and each output block shows what the program printed.

• How a Java program is structured and how to run one.
• The primitive types, their limits, and what happens when they overflow.
• Division, remainder and char arithmetic, including the surprises.
• Conditions and loops, and how to avoid off-by-one errors.
• How methods receive arguments, and why arrays behave differently from int.
• How arrays, strings, lists and a tiny class work.
• How to read input and handle common exceptions.

Every program in this course has the same skeleton:

// File: Main.javapublic class Main {    public static void main(String[] args) {        int age = 21;        long population = 1_400_000_000L;        double average = 72.5;        char grade = 'A';        boolean passed = true;        String name = "Asha";        System.out.println(name + " " + age + " " + population + " " + average + " " + grade + " " + passed);        System.out.println(Integer.MAX_VALUE);        System.out.println(Integer.MIN_VALUE);        System.out.println(Long.MAX_VALUE);    }}

Asha 21 1400000000 72.5 A true2147483647-21474836489223372036854775807

A few things to notice:

• The file name must match the public class name, so this file is Main.java.
• main is where execution begins. static means it belongs to the class itself, so Java can call it without creating an object first.
• The comment // File: Main.java at the top is only there to tell you what to name the file. It has no effect on the program.
• Helper methods in our programs are also static, so main can call them directly.
• 1_400_000_000L uses underscores for readability, and the L marks the number as a long.

A primitive type holds a plain value. These are the ones you will use:

Each type has a default value when it is a field or an array element: 0 for numbers, false for boolean, and '\u0000' for char. Local variables inside a method have no default, and Java refuses to compile code that reads one before it is assigned.

An int cannot hold a number larger than 2,147,483,647. If you go past it, Java does not crash. It wraps around to the most negative number, silently.

// File: Main.javapublic class Main {    public static void main(String[] args) {        int big = Integer.MAX_VALUE;        System.out.println(big + 1);        long wrong = 100000 * 100000;      // the multiplication is done in int first        long right = 100000L * 100000;     // one long operand makes the whole thing long        System.out.println(wrong + " " + right);        try {            Math.addExact(big, 1);         // like +, but throws instead of wrapping        } catch (ArithmeticException e) {            System.out.println("addExact: " + e.getMessage());        }        System.out.println(7 / 2);        System.out.println(-7 / 2);        System.out.println(-7 % 3);        System.out.println(Math.floorMod(-7, 3));        System.out.println(7 / 2.0);        System.out.println((double) 7 / 2);        System.out.println((double) (7 / 2));        System.out.println('a' + 1);        System.out.println((char) ('a' + 1));        System.out.println('7' - '0');    }}

-21474836481410065408 10000000000addExact: integer overflow3-3-123.53.53.098b7

Let us read this output line by line.

1. Integer.MAX_VALUE + 1 wraps to Integer.MIN_VALUE.
2. 100000 * 100000 is ten billion, which does not fit in an int. Both operands are int, so Java multiplies in int and only then widens the (already wrong) result to long. Writing 100000L fixes it, because one long operand makes the whole multiplication a long one. The type of the calculation is decided by the operands, not by the variable you assign to.
3. Math.addExact throws ArithmeticException on overflow. It is useful when you would rather fail loudly.
4. 7 / 2 is 3. When both operands are integers, the fraction is thrown away. -7 / 2 is -3, because Java truncates towards zero and does not round down.
5. -7 % 3 is -1. In Java the sign of the remainder follows the left operand. If you need a non-negative remainder (for example for a circular index), use Math.floorMod(-7, 3), which gives 2.
6. 7 / 2.0 is 3.5, because one operand is a double. Be careful with the cast position: (double) 7 / 2 casts first, giving 3.5, while (double) (7 / 2) divides first (3) and then converts (3.0).
7. 'a' + 1 is the int 98, because char takes part in arithmetic as a number. Cast back with (char) to get 'b'.
8. '7' - '0' is the int 7. This is the standard way to convert a digit character to its numeric value.

You will use if, else, for, while and the enhanced for loop constantly.

// File: Main.javapublic class Main {    // Sum of the squares of the even numbers from 1 to n (inclusive).    static long sumOfEvenSquares(int n) {        long total = 0;        for (int i = 1; i <= n; i++) {            if (i % 2 != 0) {                continue;               // skip odd numbers            }            total += (long) i * i;      // cast before multiplying to avoid int overflow        }        return total;    }    public static void main(String[] args) {        System.out.println(sumOfEvenSquares(6));    // 4 + 16 + 36        System.out.println(sumOfEvenSquares(1));        System.out.println(sumOfEvenSquares(0));        int[] marks = {40, 85, 72, 91};        int count = 0;        for (int mark : marks) {                    // enhanced for: no index needed            if (mark >= 75 && mark <= 100) {                count++;            }        }        System.out.println(count);        int i = 0;        while (i < marks.length && marks[i] != 72) { // check the bound first            i++;        }        System.out.println(i);    }}

560022

Key points:

• && and || short-circuit. In i < marks.length && marks[i] != 72, if i is out of range, the second part is never evaluated. That is why the order matters. Reverse them and you crash with an index error.
• for (int mark : marks) visits each element and is the cleanest option when you do not need the index. You cannot use it to modify the array's elements through the loop variable.
• continue skips to the next iteration, and break leaves the loop.
• Off-by-one errors come from < versus <= and from n versus n - 1. For an array a, valid indexes are 0 through a.length - 1. When in doubt, test with an array of length 0, 1 and 2.

When you call a method, Java passes copies of the arguments. For primitives, that copy is the number itself. For arrays and objects, the copy is a reference, which is like an address pointing to the same object.

That has two consequences, shown in this program:

// File: Main.javaimport java.util.Arrays;public class Main {    static void changeNumber(int x) {        x = 99;                         // changes only the local copy    }    static void changeFirst(int[] values) {        values[0] = 99;                 // follows the reference, so the caller's array changes    }    static void reassign(int[] values) {        values = new int[] {7, 7, 7};   // only changes the local copy of the reference    }    public static void main(String[] args) {        int number = 1;        changeNumber(number);        System.out.println(number);        int[] data = {1, 2, 3};        changeFirst(data);        System.out.println(Arrays.toString(data));        reassign(data);        System.out.println(Arrays.toString(data));    }}

1[99, 2, 3][99, 2, 3]

• changeNumber cannot change number.
• changeFirst can change the contents of data, because it reaches the same array.
• reassign cannot make data point at a different array, because it only changed its own copy of the reference.

This is why you can write an in-place reverse(int[] a) method, and why you cannot write swap(int a, int b) that swaps two local ints. We will rely on this constantly.

An array is a fixed-size, ordered collection of values of the same type, stored side by side in memory. We study arrays in depth in Arrays and Array-Based Problem Solving. Here are the Java mechanics.

// File: Main.javaimport java.util.Arrays;public class Main {    public static void main(String[] args) {        int[] scores = new int[5];            // five zeros        boolean[] flags = new boolean[3];     // three falses        String[] names = new String[2];       // two nulls        System.out.println(Arrays.toString(scores));        System.out.println(Arrays.toString(flags));        System.out.println(Arrays.toString(names));        int[] a = {3, 1, 2};        int[] alias = a;                           // the same array with a second name        int[] copy = Arrays.copyOf(a, a.length);   // a new array holding the same values        a[0] = 100;        System.out.println(alias[0] + " " + copy[0]);        System.out.println(Arrays.equals(a, alias) + " " + (a == copy) + " " + Arrays.equals(a, copy));        int[][] grid = new int[2][3];              // 2 rows, 3 columns        grid[1][2] = 5;        System.out.println(Arrays.deepToString(grid));        int[][] jagged = new int[3][];             // rows can have different lengths        jagged[0] = new int[] {1};        jagged[1] = new int[] {1, 2};        jagged[2] = new int[] {1, 2, 3};        System.out.println(Arrays.deepToString(jagged));        Arrays.sort(a);        System.out.println(Arrays.toString(a));        Arrays.fill(scores, -1);        System.out.println(Arrays.toString(scores));    }}

[0, 0, 0, 0, 0][false, false, false][null, null]100 3true false false[[0, 0, 0], [0, 0, 5]][[1], [1, 2], [1, 2, 3]][1, 2, 100][-1, -1, -1, -1, -1]

What to remember:

• An array's size is fixed when it is created. a.length is a field, not a method, so there are no parentheses.
• Printing an array directly with System.out.println(a) shows something like [I@1b6d3586, not the contents. Use Arrays.toString(a) or Arrays.deepToString for 2D arrays.
• int[] alias = a does not copy. It creates a second name for the same array. To copy, use Arrays.copyOf(a, a.length) or a.clone().
• == on arrays compares references (are they the same object?), while Arrays.equals(x, y) compares the contents.
• A 2D array is an array of arrays. Rows can have different lengths ("jagged").
• Arrays.sort, Arrays.fill, Arrays.copyOfRange and Arrays.asList are the helpers you will use most.

A String is an object, not a primitive. Two facts matter most: strings are immutable (they never change after creation), and you compare them with equals.

// File: Main.javapublic class Main {    public static void main(String[] args) {        String a = "hello";        String b = "hello";        String c = new String("hello");        System.out.println(a == b);        // true here, because identical literals are shared        System.out.println(a == c);        // false: two different objects        System.out.println(a.equals(c));   // true: same characters        String s = "DSA in Java";        System.out.println(s.length() + " " + s.charAt(0) + " " + s.substring(4, 6) + " " + s.indexOf("Java"));        System.out.println(s.toUpperCase() + " " + s);   // s itself never changes        String t = s.replace("Java", "C++");        System.out.println(t);        System.out.println("apple".compareTo("banana") < 0);        char[] letters = "dcba".toCharArray();        java.util.Arrays.sort(letters);        System.out.println(new String(letters));        System.out.println(String.valueOf(42) + 1);        System.out.println(Integer.parseInt("123") + 1);    }}

truefalsetrue11 D in 7DSA IN JAVA DSA in JavaDSA in C++trueabcd421124

Notes:

• a == b is true only because Java reuses one object for identical string literals. Never depend on that. a == c shows what happens with a string created at runtime. Always compare strings with equals.
• substring(start, end) includes start and excludes end. So s.substring(4, 6) is the two characters at positions 4 and 5.
• Methods like toUpperCase and replace return a new string, and leave the original alone. If you forget to use the returned value, nothing happens.
• To change individual characters, convert with toCharArray(), modify the array, and build a new string. We study strings properly in Strings.

Arrays have a fixed size. For a growable sequence, use ArrayList. It stores objects, so for numbers it stores Integer, the object wrapper of int. Java converts between int and Integer automatically (called boxing and unboxing).

// File: Main.javaimport java.util.ArrayList;import java.util.List;public class Main {    public static void main(String[] args) {        List<Integer> list = new ArrayList<>();        list.add(10);        list.add(20);        list.add(30);        System.out.println(list + " size=" + list.size() + " first=" + list.get(0));        list.remove(Integer.valueOf(20));   // removes the VALUE 20        list.remove(0);                     // removes the element at INDEX 0        System.out.println(list);        Integer p = 127;        Integer q = 127;        Integer r = 1000;        Integer s = 1000;        System.out.println((p == q) + " " + p.equals(q));        System.out.println(r.equals(s));    // always compare boxed numbers with equals        int total = 0;        for (int value : List.of(1, 2, 3)) {            total += value;        }        System.out.println(total);    }}

[10, 20, 30] size=3 first=10[30]true truetrue6

Two traps are visible here:

• remove(int) versus remove(Object). On a List<Integer>, list.remove(20) would try to remove the element at index 20 and crash. To remove the value 20, pass an object: list.remove(Integer.valueOf(20)).
• Comparing boxed numbers. p == q happened to be true because Java caches Integer objects for small values (-128 to 127). With larger values, == on two Integer objects compares references and is usually false, even when the numbers are equal. Use equals for Integer, Long, String and every other object. (We deliberately did not print r == s, since showing it adds nothing except confusion.)

You write List<Integer>, with the angle brackets, to say what the list holds. That feature is called generics. You can only use object types there, never int.

Data structures such as linked lists and trees are built from small classes. A class groups data (fields) with behaviour (methods).

// File: Main.javapublic class Main {    static class Student {        private final String name;        private int marks;        Student(String name, int marks) {   // constructor: runs when you write new Student(...)            this.name = name;            this.marks = marks;        }        boolean passed() {            return marks >= 40;        }        @Override        public String toString() {          // controls how the object prints            return name + "(" + marks + ")";        }    }    public static void main(String[] args) {        Student asha = new Student("Asha", 82);        Student ravi = new Student("Ravi", 35);        System.out.println(asha + " " + asha.passed());        System.out.println(ravi + " " + ravi.passed());        Student nobody = null;              // a reference that points to no object        try {            System.out.println(nobody.passed());        } catch (NullPointerException e) {            System.out.println("cannot call a method on null");        }    }}

Asha(82) trueRavi(35) falsecannot call a method on null

• new Student("Asha", 82) creates an object and runs the constructor. The variable holds a reference to that object.
• this means "the object this method was called on".
• null means "no object". Calling a method on null throws NullPointerException, the most common Java runtime error. We will check for null explicitly whenever a data structure can be empty.
• static class inside Main is a nested class we can create without an enclosing object. In later articles our Node classes are declared this way, to keep each program in a single file.

Online judges and coding tests give you input through the keyboard stream, System.in. The simplest reader is Scanner. In the example below we feed it a fixed string so the program runs on its own. In a real submission replace the string with System.in.

// File: Main.javaimport java.util.Scanner;public class Main {    public static void main(String[] args) {        // Real programs use: new Scanner(System.in)        Scanner in = new Scanner("5\n10 20 30 40 50\nhello world\n");        int n = in.nextInt();        long sum = 0;        int max = Integer.MIN_VALUE;        for (int i = 0; i < n; i++) {            int x = in.nextInt();            sum += x;            max = Math.max(max, x);        }        in.nextLine();                       // finish the line that held the numbers        String line = in.nextLine();        System.out.println(sum + " " + max + " [" + line + "]");        StringBuilder out = new StringBuilder();        for (int i = 1; i <= 3; i++) {            out.append(i).append(' ');        }        System.out.println(out.toString().trim());    }}

150 50 [hello world]1 2 3

• nextInt() reads a number but leaves the end-of-line character unread. That is why we call in.nextLine() once before reading a full line.
• For a very large input, Scanner is slow. Programmers then use BufferedReader with StringTokenizer. We show that template in Indian Fresher Placement and Coding Interview Preparation.
• Calling System.out.println many thousands of times is also slow. Collect the output in a StringBuilder and print once. We explain StringBuilder properly in the strings article.

When something illegal happens, Java throws an exception. If nothing catches it, the program stops and prints a message. The message tells you exactly what happened, so learn to read it.

// File: Main.javapublic class Main {    public static void main(String[] args) {        int[] data = {1, 2, 3};        try {            System.out.println(data[3]);        } catch (ArrayIndexOutOfBoundsException e) {            System.out.println("bad index: " + e.getMessage());        }        try {            System.out.println(10 / (data[0] - 1));        } catch (ArithmeticException e) {            System.out.println("math problem: " + e.getMessage());        }        try {            Integer.parseInt("12a");        } catch (NumberFormatException e) {            System.out.println("not a number");        }        System.out.println(10.0 / 0);    }}

bad index: Index 3 out of bounds for length 3math problem: / by zeronot a numberInfinity

Notice that dividing a double by zero does not throw. It gives Infinity, while dividing an int by zero throws.

You will learn Big O properly in the next article. Meanwhile, keep this table handy, because the hidden cost of a library call is a classic source of slow solutions.

• Comparing strings or boxed numbers with ==. Use equals.
• Forgetting integer division. sum / count with two ints drops the fraction. Cast one operand to double.
• Overflow. int sums and products wrap silently. Use long, and cast before the operation: (long) a * b.
• Loop bounds. i <= array.length crashes on the last iteration. Use i < array.length.
• Integer.MIN_VALUE surprises. Math.abs(Integer.MIN_VALUE) is still negative, because +2,147,483,648 does not fit in an int. Negating it also gives the same value.
• Using the wrong remove. list.remove(5) removes an index; list.remove(Integer.valueOf(5)) removes a value.
• Modifying a list while looping over it with an enhanced for loop throws ConcurrentModificationException.
• Assuming a default value for a local variable. Fields and array elements get defaults. Local variables do not.
• Printing an array directly. Use Arrays.toString.
• Forgetting that arrays are references. Assigning one array variable to another does not copy it.

int a = 7, b = 2;System.out.println(a / b + " " + a % b + " " + (double) a / b);char c = 'c';System.out.println(c - 'a');System.out.println((char) (c + 1));int x = Integer.MAX_VALUE;x++;System.out.println(x);String s = "abc";s.toUpperCase();System.out.println(s);

static double average(int[] marks) {    int sum = 0;    for (int i = 0; i <= marks.length; i++) {        sum += marks[i];    }    return sum / marks.length;}static boolean isYes(String answer) {    return answer == "yes";}

// File: Main.javapublic class Main {    public static void main(String[] args) {        int a = 7, b = 2;        System.out.println(a / b + " " + a % b + " " + (double) a / b);        char c = 'c';        System.out.println(c - 'a');        System.out.println((char) (c + 1));        int x = Integer.MAX_VALUE;        x++;        System.out.println(x);        String s = "abc";        s.toUpperCase();        System.out.println(s);    }}

3 1 3.52d-2147483648abc

// File: Main.javapublic class Main {    static boolean isPrime(int n) {        if (n < 2) {            return false;        }        if (n % 2 == 0) {            return n == 2;        }        for (int i = 3; i <= n / i; i += 2) {   // same as i * i <= n, without overflow            if (n % i == 0) {                return false;            }        }        return true;    }    public static void main(String[] args) {        int[] tests = {-5, 0, 1, 2, 3, 4, 17, 25, 97, 2147483646, 2147483647};        for (int n : tests) {            System.out.println(n + " " + isPrime(n));        }    }}

-5 false0 false1 false2 true3 true4 false17 true25 false97 true2147483646 false2147483647 true

// File: Main.javapublic class Main {    static double averageFixed(int[] marks) {        if (marks.length == 0) {            throw new IllegalArgumentException("marks must not be empty");        }        long sum = 0;        for (int i = 0; i < marks.length; i++) {            sum += marks[i];        }        return (double) sum / marks.length;    }    static boolean isYesBuggy(String answer) {        return answer == "yes";    }    static boolean isYesFixed(String answer) {        return "yes".equals(answer);    }    public static void main(String[] args) {        System.out.println(averageFixed(new int[] {3, 4}));        String typed = new String("yes");   // like text read from a user        System.out.println(isYesBuggy(typed) + " " + isYesFixed(typed) + " " + isYesFixed(null));    }}

3.5false true false

// File: Main.javaimport java.util.Scanner;public class Main {    public static void main(String[] args) {        Scanner in = new Scanner("4 7 10 12 3");   // use System.in for real input        int evens = 0;        while (in.hasNextInt()) {            int x = in.nextInt();            if (x % 2 == 0) {                evens++;            }        }        System.out.println(evens);    }}

3

// File: Main.javaimport java.util.Arrays;public class Main {    static void swap(int[] a, int i, int j) {        int temp = a[i];        a[i] = a[j];        a[j] = temp;    }    static void reverse(int[] a) {        int left = 0;        int right = a.length - 1;        while (left < right) {            swap(a, left, right);            left++;            right--;        }    }    public static void main(String[] args) {        int[] even = {1, 2, 3, 4};        int[] odd = {1, 2, 3};        int[] single = {9};        int[] empty = {};        reverse(even);        reverse(odd);        reverse(single);        reverse(empty);        System.out.println(Arrays.toString(even));        System.out.println(Arrays.toString(odd));        System.out.println(Arrays.toString(single));        System.out.println(Arrays.toString(empty));    }}

[4, 3, 2, 1][3, 2, 1][9][]

• Next: Time and Space Complexity Without the Confusion will let you describe how fast and how large your solutions are.
• Then: in Arrays and Array-Based Problem Solving you will put the array mechanics from this article to work.
• If you want more Java practice, write the exercises from this article again from memory a few days later. That is the most efficient revision.