1. Introduction
In this tutorial, we’ll understand the problem of reversing rows of a 2d array and solve it using a few alternatives using built-in Java libraries.
2. Understanding the Problem
Using 2d arrays is a common task for programmers. For instance, financial spreadsheet software is typically structured as a 2d array where each position represents a number or text. Additionally, in digital arts and photography, the images are often stored as a 2d array, where each position represents a color intensity.
When manipulating a 2d array, a common operation is to reverse all of its rows. For example, in Google Spreadsheets we have the functionality of reversing the spreadsheet row-wise. Moreover, in digital arts and photography, we can find the vertical symmetric part of an image by reversing all of its rows.
Other applications of reversing rows happen when we have a Stream of elements in Java and want to create a reversed version of that Stream or collect it in another collection in the reversed order.
The problem’s definition is quite simple: we want each row of a 2d array reversed so the first element swaps positions with the last, and so on. In other words, we want to transform the input into its vertical symmetry. Noticeably, the problem isn’t related to the reverse natural order of elements but to the reverse order that they appear in the input.
3. Reversing Rows In-Place
To help understand how to reverse rows in place, we can think of each row of a 2d array as a 1d array. Hence, the algorithm for the 1d array is straightforward: we simply swap the current index’s element with the one in its symmetric index until we reach the middle element.
For instance, one solution to the problem is:
original
-5
4
3
-2
7
reversed
7
-2
3
4
-5
We’ve swapped elements in indexes 0 with 4 and 1 with 3. The middle element doesn’t have symmetry, so it stays in the same index.
Therefore, if we call the reverse 1d algorithm for each row of the 2d array, then we’ll solve for the 2d case.
3.1. Using Java for Loops
With the idea from the previous section, let’s look at the source code:
public static void reverseRowsUsingSimpleForLoops(int[][] array) {
for (int row = 0; row < array.length; row++) {
for (int col = 0; col < array[row].length / 2; col++) {
int current = array[row][col];
array[row][col] = array[row][array[row].length - col - 1];
array[row][array[row].length - col - 1] = current;
}
}
}
The inner for loop solves the reverse problem for the 1d array. Hence, we iterate through each element, swapping it with its symmetric element, which is the one at the column array[row].length – col – 1, until we reach the middle index.
The outer loop calls that algorithm to reverse a 1d array for each row of the input.
We can verify the results using a JUnit 5 test and AssertJ matchers:
@Test
void givenArray_whenCallReverseRows_thenAllRowsReversed() {
int[][] input = new int[][] { { 1, 2, 3 }, { 3, 2, 1 }, { 2, 1, 3 } };
int[][] expected = new int[][] { { 3, 2, 1 }, { 1, 2, 3 }, { 3, 1, 2 } };
reverseRowsUsingSimpleForLoops(input);
assertThat(input).isEqualTo(expected);
}
3.2. Using Nested Java 8 IntStreams
Similarly to the previous for loop solution, we can use Java 8 Streams to reverse 2d arrays:
public static void reverseRowsUsingStreams(int[][] array) {
IntStream.range(0, array.length)
.forEach(row -> IntStream.range(0, array[row].length / 2)
.forEach(col -> {
int current = array[row][col];
array[row][col] = array[row][array[row].length - col - 1];
array[row][array[row].length - col - 1] = current;
}));
}
Notably, the main logic stays the same – we swap elements with their symmetric in the array.
The only difference is that we use a combination of IntStream.range() and forEach() to iterate over a stream using indexes. Hence, we can just swap elements in the innermost forEach()’s lambda expression.
3.3. Using the Built-In Collections.reverse() Method
We can also use the built-in reverse() method to help with this task:
public static void reverseRowsUsingCollectionsReverse(int[][] array) {
for (int row = 0; row < array.length; row++) {
List <Integer> collectionBoxedRow = Arrays.stream(array[row])
.boxed()
.collect(Collectors.toList());
Collections.reverse(collectionBoxedRow);
array[row] = collectionBoxedRow.stream()
.mapToInt(Integer::intValue)
.toArray();
}
}
First, like in previous approaches, we start by looping the original 2d array.
Then we box each row from int[] to List
Finally, we unbox the reversed boxed row using the mapToInt() and toArray() methods and assign it to the original array at the index row.
Conversely, the solution becomes clearer if we accept List<List
public static void reverseRowsUsingCollectionsReverse(List<List<Integer>> array) {
array.forEach(Collections::reverse);
}
4. Reversing Rows During a Stream Execution
So far, we’ve seen ways to reverse an array in place. However, sometimes we don’t want to mutate the input, which is the case when working with Java Streams.
In this section, we’ll create a customized mapper and collect functions to reverse rows of a 2d array.
4.1. Creating a Reversed Order Mapper
Let’s first look at how to create a function that returns the input list in reverse order:
static <T> List <T> reverse(List<T> input) {
Object[] tempArray = input.toArray();
Stream<T> stream = (Stream<T>) IntStream.range(0, temp.length)
.mapToObj(i -> temp[temp.length - i - 1]);
return stream.collect(Collectors.toList());
}
The method accepts a List of a generic type T and returns a reversed version of it. Using generics here helps to work with streams of any type.
The algorithm starts by creating a temporary array of Object with the input content. Then, we revert its elements by remapping each element to its symmetric, similar to what we did in Section 3.1. Finally, we collect the results into a list and return it.
Now, we can use reverse() inside a stream of a 2d array:
List<List<Integer>> array = asList(asList(1, 2, 3), asList(3, 2, 1), asList(2, 1, 3));
List<List<Integer>> result = array.stream()
.map(ReverseArrayElements::reverse)
.collect(Collectors.toList());
We used reverse() as a lambda function of the map() method in a stream opened with the original 2d array. Then, we collect the results reversed to a new 2d array.
4.2. Implementing a Reversed Order Collector
We can achieve the same using customized collectors. Let’s look at how it works:
static <T> Collector<T, ? , List<T>> toReversedList() {
return Collector.of(
ArrayDeque::new,
(Deque <T> deque, T element) -> deque.addFirst(element),
(d1, d2) -> {
d2.addAll(d1);
return d2;
},
ArrayList::new
);
}
The method above returns a collector, so we can use it inside the Stream’s collect() method and get the elements of an input list reversed. To do so, we used the Collector.of() method passing 4 arguments:
- A Supplier of ArrayDeque that we’ll use to help us revert the input. The choice of ArrayDeque is because it provides efficient insertion at the first index.
- A function that accumulates each input array element, adding it to the first position of an accumulator ArrayDeque.
- Another function that combines the result of one accumulator ArrayDeque, d1, with another accumulator, d2. Then, we return d2.
- After combining the intermediate results, we convert the ArrayDeque d2 into an ArrayList using the finisher function ArrayList::new.
In short, we read from left to right on the input array and add its elements to the first position of an intermediate ArrayDeque. This guarantees that at the end of execution, the accumulated ArrayDeque will contain the reversed array. Then, we convert it to a list and return.
Then, we can use toReversedList() inside a stream:
List<List<Integer>> array = asList(asList(1, 2, 3), asList(3, 2, 1), asList(2, 1, 3));
List<List<Integer>> result = array.stream()
.map(a -> a.stream().collect(toReversedList()))
.collect(Collectors.toList());
We can pass toReversedList() directly into collect() opened in a stream of the original 2d array rows. Then, we collect the reversed rows into a new list to produce the final result.
5. Conclusion
In this article, we explored several algorithms for reversing rows of a 2d array in place. Additionally, we created customized mappers and collectors for reversing rows and used them inside 2d array streams.
As always, the source code is available over on GitHub.