Lecture 14 · 100 min

Array Algorithms

How do we add up, search and sort, and how do we store a whole table?

Teacher view

By the end of this lecture you will be able to

Compute the sum, the average, and the largest and smallest elements with their positions
Count elements that match a condition and find a value with linear search
Reverse an array in place and shift its elements
Trace bubble sort pass by pass
Use the Arrays class and explain why == does not compare array contents
Traverse a 2D array with nested loops and print it as a formatted table

In this lecture

Sum and average: a variable that builds up during the walk
The largest element and its position: keep the best seen so far
Counting: a counter that grows when the condition holds
Linear search checks elements in order and stops at the first match
Reversing in place: swap the two ends and move to the middle
In shifting, the loop direction decides whether values survive
In each pass the largest floats to the end of the unsorted part
The outer loop counts passes and the inner loop compares neighbours
The Arrays class prints and sorts in one line
copyOf makes a new row and fill fills every box
== asks if it is the same row; Arrays.equals compares contents
A 2D array is rows and columns, and the first index is the row
A row sum holds the row still; a column sum holds the column still
A tidy marks table: printf sets the width of each column
Rows can differ in length, so always use m[row].length
Review questions

Part one: one loop and a variable or two

Sum and average: a variable that builds up during the walk

Most array algorithms share one shape: a variable with a starting value, a loop over the elements, and an update to that variable inside the loop. Always ask: which variable do I need, and what does it start at?

Sum and average of the marks

Press "Debug line by line" and watch sum grow. Add a fifth mark and predict the new average before running.

public class SumAverage {
    public static void main(String[] args) {
        int[] marks = {80, 75, 90, 64};
        int sum = 0;
        for (int mark : marks) {
            sum += mark;
        }
        double average = (double) sum / marks.length;
        System.out.println("Sum: " + sum);
        System.out.println("Average: " + average);
    }
}

Output

Sum: 309
Average: 77.25

This time we forgot `(double)`. What average is printed?

public class AverageBug {
    public static void main(String[] args) {
        int[] a = {1, 2, 2};
        int sum = 0;
        for (int x : a) {
            sum += x;
        }
        double average = sum / a.length;
        System.out.println(average);
    }
}

Show the output

Output

1.0

Why? sum and a.length are both ints, so the division is whole-number and gives 1, which becomes 1.0 when stored in the double. Too late: the fraction was lost before the assignment.

Average of the marks

Read n, then n marks into an array. Print the average to two decimal places using printf.

import java.util.Scanner;

public class AverageMarks {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // Read the marks, then print the average with printf

    }
}

stdin

3
70 80 90

Expected output

80.00

Hint 1

Cast before dividing: (double) sum / n.

Hint 2

The format string: "%.2f%n".

Solution

import java.util.Scanner;

public class AverageMarks {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] marks = new int[n];
        int sum = 0;
        for (int i = 0; i < n; i++) {
            marks[i] = in.nextInt();
            sum += marks[i];
        }
        System.out.printf("%.2f%n", (double) sum / n);
    }
}

The largest element and its position: keep the best seen so far

Largest and smallest mark with position

Press "Debug line by line" and watch maxPos change only when a larger value appears. Notice 95 repeats and the first position stays. Change > to >=: what is the position now?

public class MaxMin {
    public static void main(String[] args) {
        int[] marks = {72, 95, 60, 95, 81};
        int maxPos = 0;
        int minPos = 0;
        for (int i = 1; i < marks.length; i++) {
            if (marks[i] > marks[maxPos]) {
                maxPos = i;
            }
            if (marks[i] < marks[minPos]) {
                minPos = i;
            }
        }
        System.out.println("Max " + marks[maxPos] + " at " + maxPos);
        System.out.println("Min " + marks[minPos] + " at " + minPos);
    }
}

Output

Max 95 at 1
Min 60 at 2

Here `max` starts at 0 instead of the first element. What does it print?

public class MaxFromZero {
    public static void main(String[] args) {
        int[] temps = {-5, -2, -9};
        int max = 0;
        for (int t : temps) {
            if (t > max) {
                max = t;
            }
        }
        System.out.println(max);
    }
}

Show the output

Output

Why? No element is above 0, so max keeps its starting value, which is not even in the array. That is why we always start from the first element.

Largest element and its position

Read n, then n numbers. Print Max: X at position P. If the largest repeats, print its first position.

import java.util.Scanner;

public class MaxPosition {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // Read the array, then find the largest element and its position

    }
}

stdin

5
3 9 2 7 4

Expected output

Max: 9 at position 1

Hint 1

One variable for the position is enough; the value is a[pos].

Hint 2

Use >, not >=, so the first position stays when values repeat.

Solution

import java.util.Scanner;

public class MaxPosition {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = in.nextInt();
        }
        int pos = 0;
        for (int i = 1; i < n; i++) {
            if (a[i] > a[pos]) {
                pos = i;
            }
        }
        System.out.println("Max: " + a[pos] + " at position " + pos);
    }
}

Counting: a counter that grows when the condition holds

How many students passed?

A sum adds the value; a counter adds 1. Change the program to count those who failed, then to count marks above 60.

public class CountPassing {
    public static void main(String[] args) {
        int[] marks = {45, 80, 50, 30, 99};
        int count = 0;
        for (int mark : marks) {
            if (mark >= 50) {
                count++;
            }
        }
        System.out.println(count);
    }
}

Output

How many times does the value appear?

Read n, then n numbers, then a number target. Print how many times target appears in the array.

import java.util.Scanner;

public class CountValue {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // Read the array and target, then count the matches

    }
}

stdin

6
1 2 3 2 2 5
2

Expected output

Hint 1

The counter starts at 0, so an absent value prints 0 with no special case.

Solution

import java.util.Scanner;

public class CountValue {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = in.nextInt();
        }
        int target = in.nextInt();
        int count = 0;
        for (int x : a) {
            if (x == target) {
                count++;
            }
        }
        System.out.println(count);
    }
}

Linear search checks elements in order and stops at the first match

A method that returns the position or -1

We return -1 when the value is not found, because no index is negative. Debug both calls line by line and notice how many elements the method checked each time.

public class LinearSearch {
    static int indexOf(int[] arr, int target) {
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == target) {
                return i;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] ids = {10, 20, 30, 20};
        System.out.println(indexOf(ids, 20));
        System.out.println(indexOf(ids, 99));
    }
}

Output

1
-1

A very common bug: we added an `else` inside the loop. What does it print?

public class SearchBug {
    static int indexOf(int[] arr, int target) {
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == target) {
                return i;
            } else {
                return -1;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] ids = {10, 20, 30};
        System.out.println(indexOf(ids, 30));
    }
}

Show the output

Output

-1

Why? The method always ends in the first round, because both branches contain return, so it checks only the first element. You can only say a value is absent after the loop ends.

What does the method return if it finds nothing?

public class MissingReturn {
    static int indexOf(int[] arr, int target) {
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == target) {
                return i;
            }
        }
    }

    public static void main(String[] args) {
        int[] ids = {10, 20};
        System.out.println(indexOf(ids, 20));
    }
}

Compiler messagemissing return statement

Show the fix

public class MissingReturn {
    static int indexOf(int[] arr, int target) {
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == target) {
                return i;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] ids = {10, 20};
        System.out.println(indexOf(ids, 20));
    }
}

Output

Why? The compiler sees a path where the loop ends without running return, so it refuses the program. The right answer on that path is -1.

Find the value

Write the method static int indexOf(int[] arr, int target). In main read n, then n numbers, then target. Print Found at position P for the first match, or Not found.

import java.util.Scanner;

public class FindFirst {
    // Write indexOf here

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // Read the input, call indexOf, print the result

    }
}

stdin

4
5 8 2 9
2

Expected output

Found at position 2

Hint 1

return -1; goes after the loop, not inside it.

Hint 2

Store the method's result in a variable, then check it with if.

Solution

import java.util.Scanner;

public class FindFirst {
    static int indexOf(int[] arr, int target) {
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == target) {
                return i;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = in.nextInt();
        }
        int pos = indexOf(a, in.nextInt());
        if (pos == -1) {
            System.out.println("Not found");
        } else {
            System.out.println("Found at position " + pos);
        }
    }
}

Reversing in place: swap the two ends and move to the middle

Two positions moving towards each other

"In place" means we create no second array. Press "Debug line by line" and watch i and j move closer. What happens to the middle element? Try an array of 4 elements.

public class ReverseInPlace {
    public static void main(String[] args) {
        int[] a = {1, 2, 3, 4, 5};
        for (int i = 0; i < a.length / 2; i++) {
            int j = a.length - 1 - i;
            int temp = a[i];
            a[i] = a[j];
            a[j] = temp;
        }
        for (int x : a) {
            System.out.print(x + " ");
        }
        System.out.println();
    }
}

Output

5 4 3 2 1

We forgot `/ 2` in the loop condition. What does the program print?

public class ReverseTwice {
    public static void main(String[] args) {
        int[] a = {1, 2, 3, 4};
        for (int i = 0; i < a.length; i++) {
            int j = a.length - 1 - i;
            int temp = a[i];
            a[i] = a[j];
            a[j] = temp;
        }
        System.out.println(a[0] + " " + a[1] + " " + a[2] + " " + a[3]);
    }
}

Show the output

Output

1 2 3 4

Why? The reversal is complete after half the rounds. The second half swaps the same pairs again, so the array returns to how it was. No error appears, which is what makes this bug hard to spot.

A method that reverses the array

Write the method static void reverse(int[] a) that reverses the array in place. In main read n, then n numbers, call the method, and print the elements on one line separated by spaces.

import java.util.Scanner;

public class ReverseMethod {
    // Write reverse here

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // Read the array, call reverse, print the elements

    }
}

stdin

5
1 2 3 4 5

Expected output

5 4 3 2 1

Hint 1

A space after the last element does not matter; the check ignores spaces at the end of a line.

Solution

import java.util.Scanner;

public class ReverseMethod {
    static void reverse(int[] a) {
        for (int i = 0; i < a.length / 2; i++) {
            int j = a.length - 1 - i;
            int temp = a[i];
            a[i] = a[j];
            a[j] = temp;
        }
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = in.nextInt();
        }
        reverse(a);
        for (int x : a) {
            System.out.print(x + " ");
        }
        System.out.println();
    }
}

In shifting, the loop direction decides whether values survive

Shifting left copies each element into the box before it. We walk from the left, so we write over a value we have finished with. Shifting right walks from the right for the same reason.

Shifting left

Debug it and watch the elements move. Notice the loop stops at a.length - 1, because it reads a[i + 1]. Change it to shift right: start from the end and write a[i] = a[i - 1].

public class ShiftLeft {
    public static void main(String[] args) {
        int[] a = {10, 20, 30, 40, 50};
        for (int i = 0; i < a.length - 1; i++) {
            a[i] = a[i + 1];
        }
        a[a.length - 1] = 0;
        for (int x : a) {
            System.out.print(x + " ");
        }
        System.out.println();
    }
}

Output

20 30 40 50 0

We want to shift right, but we walk from the left. What does it print?

public class ShiftBug {
    public static void main(String[] args) {
        int[] a = {10, 20, 30, 40};
        for (int i = 0; i < a.length - 1; i++) {
            a[i + 1] = a[i];
        }
        System.out.println(a[0] + " " + a[1] + " " + a[2] + " " + a[3]);
    }
}

Show the output

Output

10 10 10 10

Why? The first round writes 10 over 20 before 20 is copied. The next round reads that new 10, and so it spreads to the end.

Rotate left

Rotating is a shift that loses nothing: the first element moves to the end. Read n, then n numbers, rotate the array one step left, and print it on one line separated by spaces.

import java.util.Scanner;

public class RotateLeft {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // Read the array, rotate it left once, print it

    }
}

stdin

4
1 2 3 4

Expected output

2 3 4 1

Hint 1

Save a[0] in a variable before shifting, because the shift writes over it.

Hint 2

After the loop put the saved value in a[n - 1].

Solution

import java.util.Scanner;

public class RotateLeft {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = in.nextInt();
        }
        int first = a[0];
        for (int i = 0; i < n - 1; i++) {
            a[i] = a[i + 1];
        }
        a[n - 1] = first;
        for (int x : a) {
            System.out.print(x + " ");
        }
        System.out.println();
    }
}

Part two: sorting and the Arrays class

In each pass the largest floats to the end of the unsorted part

Bubble sort compares each element with its neighbour and swaps them if the left one is larger. After the first pass the largest element is in the last position, like a bubble that rose to the surface, so it needs no more checks.

Step	Compare	Row after
Start	`-`	`5 3 8 1`
Pass 1	5 and 3: swap	`3 5 8 1`
Pass 1	5 and 8: no swap	`3 5 8 1`
Pass 1	8 and 1: swap	`3 5 1 8`
Pass 2	3 and 5: no swap	`3 5 1 8`
Pass 2	5 and 1: swap	`3 1 5 8`
Pass 3	3 and 1: swap	`1 3 5 8`

See the passes in the output and in the debugger

Press "Debug line by line" and compare each step with the table above. Watch pass, j and the row. Then try an array already in order, like {1, 3, 5, 8}.

public class BubblePasses {
    static void show(int pass, int[] a) {
        System.out.print("Pass " + pass + ":");
        for (int x : a) {
            System.out.print(" " + x);
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int[] a = {5, 3, 8, 1};
        for (int pass = 1; pass < a.length; pass++) {
            for (int j = 0; j < a.length - pass; j++) {
                if (a[j] > a[j + 1]) {
                    int temp = a[j];
                    a[j] = a[j + 1];
                    a[j + 1] = temp;
                }
            }
            show(pass, a);
        }
    }
}

Output

Pass 1: 3 5 1 8
Pass 2: 3 1 5 8
Pass 3: 1 3 5 8

The outer loop counts passes and the inner loop compares neighbours

Line	Why this limit?
`pass < a.length`	After `n - 1` passes the one remaining element is automatically in place
`j < a.length - pass`	Elements that floated to the end are sorted, and `a[j + 1]` must stay inside the array
`a[j] > a[j + 1]`	Changing `>` to `<` gives descending order

The array is already in order. How many comparisons and swaps does the program make?

public class BubbleCounts {
    public static void main(String[] args) {
        int[] a = {1, 2, 3, 4};
        int comparisons = 0;
        int swaps = 0;
        for (int pass = 1; pass < a.length; pass++) {
            for (int j = 0; j < a.length - pass; j++) {
                comparisons++;
                if (a[j] > a[j + 1]) {
                    int temp = a[j];
                    a[j] = a[j + 1];
                    a[j + 1] = temp;
                    swaps++;
                }
            }
        }
        System.out.println(comparisons);
        System.out.println(swaps);
    }
}

Show the output

Output

6
0

Why? There are 3 + 2 + 1 = 6 comparisons whatever the order, because the two loops do not depend on the values. Swaps are zero because each element is smaller than its right neighbour.

Descending sort

Read n, then n numbers, and order them from largest to smallest with bubble sort, without Arrays.sort. Print them on one line separated by spaces.

import java.util.Scanner;

public class SortDescending {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // Read the array, bubble sort it largest first, print it

    }
}

stdin

5
3 9 1 7 5

Expected output

9 7 5 3 1

Hint 1

The same program you saw, with one comparison operator changed.

Solution

import java.util.Scanner;

public class SortDescending {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = in.nextInt();
        }
        for (int pass = 1; pass < n; pass++) {
            for (int j = 0; j < n - pass; j++) {
                if (a[j] < a[j + 1]) {
                    int temp = a[j];
                    a[j] = a[j + 1];
                    a[j + 1] = temp;
                }
            }
        }
        for (int x : a) {
            System.out.print(x + " ");
        }
        System.out.println();
    }
}

The `Arrays` class prints and sorts in one line

We wrote the sort by hand to understand it. In your everyday programs use Arrays from the java.util package, which is faster and less error-prone.

`toString` and `sort`

At last we see the whole array without a loop. Change the values to double and try again, then remove Arrays.toString from the first line and see what prints.

import java.util.Arrays;

public class ArraysDemo {
    public static void main(String[] args) {
        int[] a = {5, 3, 8, 1};
        System.out.println(Arrays.toString(a));
        Arrays.sort(a);
        System.out.println(Arrays.toString(a));
    }
}

Output

[5, 3, 8, 1]
[1, 3, 5, 8]

We forgot the import

public class NoImport {
    public static void main(String[] args) {
        int[] a = {2, 1};
        System.out.println(Arrays.toString(a));
    }
}

Compiler messagecannot find symbol

Show the fix

import java.util.Arrays;

public class NoImport {
    public static void main(String[] args) {
        int[] a = {2, 1};
        System.out.println(Arrays.toString(a));
    }
}

Output

[2, 1]

Why? The Arrays class lives in the java.util package, so the compiler knows it only if we import it, just as with Scanner.

`sort` returns no array

import java.util.Arrays;

public class SortVoid {
    public static void main(String[] args) {
        int[] a = {2, 1};
        int[] sorted = Arrays.sort(a);
        System.out.println(Arrays.toString(sorted));
    }
}

Compiler messagevoid cannot be converted to int[]

Show the fix

import java.util.Arrays;

public class SortVoid {
    public static void main(String[] args) {
        int[] a = {2, 1};
        Arrays.sort(a);
        System.out.println(Arrays.toString(a));
    }
}

Output

[1, 2]

Why? Arrays.sort is void: it sorts the same array, just as our method changed the elements of the array it received last lecture.

`copyOf` makes a new row and `fill` fills every box

Call	What it does	Returns
`Arrays.toString(a)`	Describes the elements in one text	`String`
`Arrays.sort(a)`	Sorts `a` itself in ascending order	`void`
`Arrays.copyOf(a, n)`	A new row of length `n`	`int[]`
`Arrays.fill(a, v)`	Puts `v` in every box	`void`
`Arrays.equals(a, b)`	Compares lengths and elements	`boolean`

The copy is separate from the original

Predict the four lines. A longer length gives the extra boxes the default value; a shorter one cuts off the rest. Replace Arrays.copyOf(a, a.length) with a on the first line and see the difference.

import java.util.Arrays;

public class CopyFill {
    public static void main(String[] args) {
        int[] a = {1, 2, 3};
        int[] b = Arrays.copyOf(a, a.length);
        b[0] = 99;
        System.out.println(Arrays.toString(a));
        System.out.println(Arrays.toString(b));

        System.out.println(Arrays.toString(Arrays.copyOf(a, 5)));

        int[] c = new int[4];
        Arrays.fill(c, 7);
        System.out.println(Arrays.toString(c));
    }
}

Output

[1, 2, 3]
[99, 2, 3]
[1, 2, 3, 0, 0]
[7, 7, 7, 7]

`==` asks if it is the same row; `Arrays.equals` compares contents

`a` and `b` hold the same values, and `c` is another name for `a`. What does it print?

import java.util.Arrays;

public class CompareArrays {
    public static void main(String[] args) {
        int[] a = {1, 2, 3};
        int[] b = {1, 2, 3};
        int[] c = a;
        System.out.println(a == b);
        System.out.println(a == c);
        System.out.println(Arrays.equals(a, b));
    }
}

Show the output

Output

false
true
true

Why? == compares the arrows: a and b are different rows even with equal values, while a and c point to the same row. Arrays.equals opens the boxes and compares elements one by one.

What is `Arrays.equals(x, y)` if `x` is `{1, 2}` and `y` is `{2, 1}`?

Why? The method compares each index with the same index: x[0] with y[0], and so on. Order is part of the contents.

Part three: 2D arrays

A 2D array is rows and columns, and the first index is the row

`marks`	Column 0	Column 1	Column 2
Row 0	`80`	`70`	`90`
Row 1	`60`	`75`	`85`

int[][] marks = new int[2][3]; creates 2 rows of 3 columns each.
marks[1][2] is row 1, column 2, which is 85.
marks.length is the number of rows, and marks[0].length the number of columns in row 0.
A 2D array is really an array whose elements are arrays.

Two nested loops

Press "Debug line by line" and watch row change slowly and col quickly, as in the nested-loop patterns. Add a fourth column to each row: do the loops need changing?

public class Traverse2D {
    public static void main(String[] args) {
        int[][] marks = {
            {80, 70, 90},
            {60, 75, 85}
        };
        for (int row = 0; row < marks.length; row++) {
            for (int col = 0; col < marks[row].length; col++) {
                System.out.print(marks[row][col] + " ");
            }
            System.out.println();
        }
    }
}

Output

80 70 90
60 75 85

Mind the order: row, then column. What does it print?

public class Index2D {
    public static void main(String[] args) {
        int[][] m = {
            {1, 2, 3},
            {4, 5, 6}
        };
        System.out.println(m.length);
        System.out.println(m[0].length);
        System.out.println(m[1][0]);
    }
}

Show the output

Output

2
3
4

Why? m has 2 rows, each with 3 elements. m[1][0] is the second row, first column, which is 4.

A pair of brackets per dimension

Some languages write dimensions with a comma. In Java each dimension has its own brackets.

public class Comma2D {
    public static void main(String[] args) {
        int[][] m = new int[2, 3];
        System.out.println(m.length);
    }
}

Compiler message']' expected

Show the fix

public class Comma2D {
    public static void main(String[] args) {
        int[][] m = new int[2][3];
        System.out.println(m.length);
    }
}

Output

Why? The compiler expects the bracket to close after the first number, so it complains at the comma.

A row sum holds the row still; a column sum holds the column still

The outer loop is what we hold still

Notice the sum goes back to zero at the start of each row or column. Move the line int sum = 0; outside the first loop and predict what happens. Then use "Debug line by line" to check.

public class RowColumnSums {
    public static void main(String[] args) {
        int[][] m = {
            {80, 70, 90},
            {60, 75, 85}
        };

        for (int row = 0; row < m.length; row++) {
            int sum = 0;
            for (int col = 0; col < m[row].length; col++) {
                sum += m[row][col];
            }
            System.out.println("Row " + row + ": " + sum);
        }

        for (int col = 0; col < m[0].length; col++) {
            int sum = 0;
            for (int row = 0; row < m.length; row++) {
                sum += m[row][col];
            }
            System.out.println("Column " + col + ": " + sum);
        }
    }
}

Output

Row 0: 240
Row 1: 220
Column 0: 140
Column 1: 145
Column 2: 175

Table sums

Read rows and cols, then the table numbers row by row. Print each row sum on a line as Row 0: 6, then each column sum as Column 0: 5.

import java.util.Scanner;

public class TableSums {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // Read rows and cols, fill the table, print the sums

    }
}

stdin

2 3
1 2 3
4 5 6

Expected output

Row 0: 6
Row 1: 15
Column 0: 5
Column 1: 7
Column 2: 9

Hint 1

To read: int[][] m = new int[rows][cols]; then two nested loops.

Hint 2

For a column sum col is in the outer loop.

Solution

import java.util.Scanner;

public class TableSums {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int rows = in.nextInt();
        int cols = in.nextInt();
        int[][] m = new int[rows][cols];
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                m[r][c] = in.nextInt();
            }
        }
        for (int r = 0; r < rows; r++) {
            int sum = 0;
            for (int c = 0; c < cols; c++) {
                sum += m[r][c];
            }
            System.out.println("Row " + r + ": " + sum);
        }
        for (int c = 0; c < cols; c++) {
            int sum = 0;
            for (int r = 0; r < rows; r++) {
                sum += m[r][c];
            }
            System.out.println("Column " + c + ": " + sum);
        }
    }
}

A tidy marks table: `printf` sets the width of each column

In the printf lecture you learned that %6d reserves six places with the number on the right, and %-8s puts text on the left. That keeps columns straight however long the values are.

An array of names and an array of marks

names[r] owns row r of marks; these are called parallel arrays. Add a fourth student, then change the widths and watch the table change. Then add an average column with the format %8.2f.

public class MarksTable {
    public static void main(String[] args) {
        String[] names = {"Sara", "Ali", "Mona"};
        int[][] marks = {
            {18, 27, 45},
            {15, 20, 38},
            {20, 30, 49}
        };

        System.out.printf("%-8s%6s%6s%6s%8s%n", "Name", "Quiz", "Mid", "Final", "Total");
        for (int r = 0; r < marks.length; r++) {
            int total = 0;
            System.out.printf("%-8s", names[r]);
            for (int c = 0; c < marks[r].length; c++) {
                System.out.printf("%6d", marks[r][c]);
                total += marks[r][c];
            }
            System.out.printf("%8d%n", total);
        }
    }
}

Output

Name      Quiz   Mid Final   Total
Sara        18    27    45      90
Ali         15    20    38      73
Mona        20    30    49      99

Rows can differ in length, so always use `m[row].length`

A jagged array

Because each row is its own array, each can have a different length, like students taking different numbers of courses. Change quizzes[row].length to quizzes[0].length and run: what happens, and what index is in the message?

public class Jagged {
    public static void main(String[] args) {
        int[][] quizzes = {
            {9, 7, 8},
            {6},
            {10, 5}
        };
        for (int row = 0; row < quizzes.length; row++) {
            for (int col = 0; col < quizzes[row].length; col++) {
                System.out.print(quizzes[row][col] + " ");
            }
            System.out.println();
        }
    }
}

Output

9 7 8
6
10 5

In the array above, what is `quizzes[1].length`?

Why? Row 1 is {6}, which has one element. The number 6 is that element's value, not the length.

Review questions

Why does `max` start at `a[0]` and not at 0?

Why? If all the elements are negative, 0 stays unchanged. a[0] is always a real element of the array.

Why does the search method return -1 when it finds nothing?

When computing each row's sum, where do we declare `int sum = 0;`?

Does sorting the copy change the original array?

import java.util.Arrays;

public class SortCopy {
    public static void main(String[] args) {
        int[] a = {3, 1, 2};
        int[] b = Arrays.copyOf(a, a.length);
        Arrays.sort(b);
        System.out.println(Arrays.toString(a));
        System.out.println(Arrays.toString(b));
    }
}

Show the output

Output

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

Why? copyOf made a new row, so the sort reached only that one. With int[] b = a; both would change.

Sum and average: a variable that builds up during the walk

Sum and average of the marks

This time we forgot (double). What average is printed?

Average of the marks

The largest element and its position: keep the best seen so far

Largest and smallest mark with position

Here max starts at 0 instead of the first element. What does it print?

Largest element and its position

Counting: a counter that grows when the condition holds

How many students passed?

How many times does the value appear?

Linear search checks elements in order and stops at the first match

A method that returns the position or -1

A very common bug: we added an else inside the loop. What does it print?

What does the method return if it finds nothing?

Find the value

Reversing in place: swap the two ends and move to the middle

Two positions moving towards each other

We forgot / 2 in the loop condition. What does the program print?

A method that reverses the array

In shifting, the loop direction decides whether values survive

Shifting left

We want to shift right, but we walk from the left. What does it print?

Rotate left

In each pass the largest floats to the end of the unsorted part

See the passes in the output and in the debugger

The outer loop counts passes and the inner loop compares neighbours

The array is already in order. How many comparisons and swaps does the program make?

Descending sort

The Arrays class prints and sorts in one line

toString and sort

We forgot the import

sort returns no array

copyOf makes a new row and fill fills every box

The copy is separate from the original

== asks if it is the same row; Arrays.equals compares contents

a and b hold the same values, and c is another name for a. What does it print?

What is Arrays.equals(x, y) if x is {1, 2} and y is {2, 1}?

A 2D array is rows and columns, and the first index is the row

Two nested loops

Mind the order: row, then column. What does it print?

A pair of brackets per dimension

A row sum holds the row still; a column sum holds the column still

The outer loop is what we hold still

Table sums

A tidy marks table: printf sets the width of each column

An array of names and an array of marks

Rows can differ in length, so always use m[row].length

A jagged array

In the array above, what is quizzes[1].length?

Review questions

Why does max start at a[0] and not at 0?

Why does the search method return -1 when it finds nothing?

When computing each row's sum, where do we declare int sum = 0;?

Does sorting the copy change the original array?

This time we forgot `(double)`. What average is printed?

Here `max` starts at 0 instead of the first element. What does it print?

A very common bug: we added an `else` inside the loop. What does it print?

We forgot `/ 2` in the loop condition. What does the program print?

The `Arrays` class prints and sorts in one line

`toString` and `sort`

`sort` returns no array

`copyOf` makes a new row and `fill` fills every box

`==` asks if it is the same row; `Arrays.equals` compares contents

`a` and `b` hold the same values, and `c` is another name for `a`. What does it print?

What is `Arrays.equals(x, y)` if `x` is `{1, 2}` and `y` is `{2, 1}`?

A tidy marks table: `printf` sets the width of each column

Rows can differ in length, so always use `m[row].length`

In the array above, what is `quizzes[1].length`?

Why does `max` start at `a[0]` and not at 0?

When computing each row's sum, where do we declare `int sum = 0;`?