Skip to content

Beginner · Arrays and strings · topic 12 of 60 · 30 min

Two-dimensional arrays and array algorithms

Explanation

A 2D array is an array of arrays, written int[][], perfect for grids such as a cinema seat map or marks of students across subjects. Classic algorithms on arrays include linear search, binary search (only on sorted data), reversing, finding max and min, and counting frequencies.

2D arrays: rows and columns

java
int[][] marks = {
    {78, 82, 91},     // student 0: Maths, Science, English
    {65, 70, 58},     // student 1
    {88, 95, 84},     // student 2
};
System.out.println(marks[2][1]);         // 95 (row 2, column 1)
System.out.println(marks.length);        // 3 rows
System.out.println(marks[0].length);     // 3 columns in row 0

for (int r = 0; r < marks.length; r++) {
    int total = 0;
    for (int c = 0; c < marks[r].length; c++) total += marks[r][c];
    System.out.println("Student " + r + ": " + total);
}

Java 2D arrays are really arrays whose elements are arrays. That means rows can have different lengths (a jagged array), for example a train coach map where some rows have fewer seats.

java
boolean[][] seats = new boolean[3][];   // 3 rows, columns not yet created
seats[0] = new boolean[6];
seats[1] = new boolean[6];
seats[2] = new boolean[4];              // a shorter last row
seats[1][3] = true;                     // book row 1, seat 3
System.out.println(java.util.Arrays.deepToString(seats));

Check each element in turn until you find the target. Works on any array; takes up to n steps (O(n)).

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

On a SORTED array, compare the target with the middle element and throw away the half where it cannot be. Each step halves the range, so a million elements need about 20 steps (O(log n)). Java provides Arrays.binarySearch(sorted, key).

java
static int binarySearch(int[] sorted, int target) {
    int lo = 0, hi = sorted.length - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;      // avoids int overflow of (lo + hi)
        if (sorted[mid] == target) return mid;
        if (sorted[mid] < target) lo = mid + 1;
        else hi = mid - 1;
    }
    return -1;
}
Careful: Binary search on unsorted data gives wrong answers without any error. Sort first (Arrays.sort) or use linear search. The famous bug (lo + hi) / 2 overflows for huge arrays; lo + (hi - lo) / 2 is safe.

Reverse in place and frequency counting

java
static void reverse(int[] a) {
    for (int i = 0, j = a.length - 1; i < j; i++, j--) {
        int tmp = a[i]; a[i] = a[j]; a[j] = tmp;     // swap the two ends
    }
}

int[] ratings = {5, 3, 5, 4, 5, 1, 3};
int[] count = new int[6];                  // index = rating 0..5
for (int r : ratings) count[r]++;
System.out.println(java.util.Arrays.toString(count));   // [0, 1, 0, 2, 1, 3]
Think of it like this: Binary search is how you find a word in a printed dictionary: open in the middle, see whether your word comes before or after, and ignore the other half. Linear search is reading the dictionary from page one.
Tip: Draw the array on paper with indexes when writing these algorithms. Mark lo, hi and mid at each step; most bugs appear immediately.

Need help?

Stuck on a word or an idea? Search this course, or every course, and jump straight to the explanation or a worked question.

Try:

Watch the lesson

Two-dimensional arrays and array algorithms · 1/6

2D arrays and algorithms

In this lesson you will use grids of data and classic array algorithms.

Prefer a video by a teacher? Find free videos on “java 2d arrays binary search algorithm tutorial” on YouTube ↗

In real life: A cinema seat map

A ticket booking counter keeps seats as a 2D boolean array (true = booked). To suggest seats, it scans row by row and returns the first row with enough free seats next to each other.

java
static int firstRowWithBlock(boolean[][] seats, int needed) {
    for (int r = 0; r < seats.length; r++) {
        int run = 0;
        for (boolean booked : seats[r]) {
            run = booked ? 0 : run + 1;
            if (run == needed) return r;
        }
    }
    return -1;
}

Practice (0/3 done)

Task 1 · Question

int[][] g = {{1, 2, 3}, {4, 5, 6}}; What is g[1][0] + g[0].length?

Task 2 · Code · Python

The same binary search algorithm in Python, which runs here: write binary_search(sorted_list, target) that returns the index of target or -1, without using index() or the in operator.

Task 3 · Code · Javascript

The same seat-map algorithm in JavaScript: write firstRowWithBlock(seats, needed) where seats is an array of rows of booleans (true = booked). Return the index of the first row with `needed` free seats next to each other, or -1.

Quick quiz

Question 1

1.What must be true for binary search to work?

Question 2

2.Why write mid = lo + (hi - lo) / 2?

Question 3

3.In int[][] t = new int[3][5]; what is t.length and t[0].length?

Question 4

4.Linear search on 1,000 items needs at most how many comparisons?

Read more (free)

Before this, learn

This topic builds on these. If something here feels new, open them first.

Open a question to see the answer and why. The first ones are this topic's own quiz, so try the quiz above before you peek.

What must be true for binary search to work?

Answer: The array is sorted

Binary search relies on sorted order.

Why write mid = lo + (hi - lo) / 2?

Answer: It avoids int overflow of lo + hi on huge arrays

lo + hi can exceed Integer.MAX_VALUE.

In int[][] t = new int[3][5]; what is t.length and t[0].length?

Answer: 3 and 5

First dimension rows (3), second columns (5).

Linear search on 1,000 items needs at most how many comparisons?

Answer: 1,000

It may check every element.

In a function parameter for a 2D int array with 4 columns, which is valid?Related

Answer: int g[][4]

All dimensions except the first are required.

From 2D arrays and classic array algorithms

What is the index of the last item in an array of length 8?Related

Answer: 7

Indexes go from 0 to Length - 1.

From Arrays: one name, many values

About how many steps does binary search need for 1,000,000 sorted items?Related

Answer: About 20

Halving 1,000,000 about 20 times gets down to 1, because 2 to the power 20 is about a million.

From Big-O and searching

What must be true before using std::binary_search or std::lower_bound?Related

Answer: The range is sorted (with the same ordering)

Binary search relies on sorted order to throw away halves.

From STL algorithms: sort, find, count, accumulate and binary search

Pass the quiz (60% or more) or mark this topic as done when you are ready.

Your progress is saved on this device only.

Next: Strings in depth →

Next steps

  1. 3 more topics in “Arrays and strings” before its exam: Strings in depth, StringBuilder and formatting, Wrapper classes and autoboxing.
  2. Module 3 exam: Arrays and strings · 12 questions · 25 min, without help. 5 topics of this module still to finish first.
  3. Then the next module, Classes and objects. 60 topics left in the course before the final exam.

← Previous: Arrays