1. Overview
Arrays are the most basic data structures in any language. Although we don’t work on them directly in most cases, knowing how to manipulate them efficiently can dramatically improve our code.
In this tutorial, we’ll learn how to convert a two-dimensional array into one-dimensional, commonly known as flattening. For example, we’ll turn { {1, 2, 3}, {4, 5, 6}, {7, 8, 9} } into {1, 2, 3, 4, 5, 6, 7, 8, 9}.
Although we’ll be working with two-dimensional arrays, the ideas outlined in this tutorial can be applied to arrays with any dimensions. In this article, we’ll use an array of primitive integers as an example, but the ideas can be applied to any array.
2. Loops and Primitive Arrays
The simplest way to approach this problem is to use a for loop, which we can use to transfer the elements from one array to another. However, to improve performance, we must identify the total number of elements to create the destination array.
It’s a trivial task if all the arrays have the same number of elements. In this case, we can use simple math to do the calculations. However, if we work with a jagged array, we need to go through each of the arrays individually:
@ParameterizedTest
@MethodSource("arrayProvider")
void giveTwoDimensionalArray_whenFlatWithForLoopAndTotalNumberOfElements_thenGetCorrectResult(
int [][] initialArray, int[] expected) {
int totalNumberOfElements = 0;
for (int[] numbers : initialArray) {
totalNumberOfElements += numbers.length;
}
int[] actual = new int[totalNumberOfElements];
int position = 0;
for (int[] numbers : initialArray) {
for (int number : numbers) {
actual[position] = number;
++position;
}
}
assertThat(actual).isEqualTo(expected);
}
Also, we can make some improvements and use System.arrayCopy() inside the second for loop:
@ParameterizedTest
@MethodSource("arrayProvider")
void giveTwoDimensionalArray_whenFlatWithArrayCopyAndTotalNumberOfElements_thenGetCorrectResult(
int [][] initialArray, int[] expected) {
int totalNumberOfElements = 0;
for (int[] numbers : initialArray) {
totalNumberOfElements += numbers.length;
}
int[] actual = new int[totalNumberOfElements];
int position = 0;
for (int[] numbers : initialArray) {
System.arraycopy(numbers, 0, actual, position, numbers.length);
position += numbers.length;
}
assertThat(actual).isEqualTo(expected);
}
System.arrayCopy() is relatively fast, and it’s the recommended way of copying arrays, along with the clone() method. However, we need to use these methods with caution on the arrays of reference types, as they perform shallow copy.
Technically, we can avoid counting the number of elements in the first loop and expand the array when necessary:
@ParameterizedTest
@MethodSource("arrayProvider")
void giveTwoDimensionalArray_whenFlatWithArrayCopy_thenGetCorrectResult(
int [][] initialArray, int[] expected) {
int[] actual = new int[]{};
int position = 0;
for (int[] numbers : initialArray) {
if (actual.length < position + numbers.length) {
int[] newArray = new int[actual.length + numbers.length];
System.arraycopy(actual, 0, newArray, 0, actual.length );
actual = newArray;
}
System.arraycopy(numbers, 0, actual, position, numbers.length);
position += numbers.length;
}
assertThat(actual).isEqualTo(expected);
}
However, this approach would tank our performance and turn the initial time complexity of O(n) to O(n^2). Thus, it should be avoided, or we need to use a more optimized algorithm to increase the array size, similar to List’s implementation.
3. Lists
Regarding lists, Java Collection API provides a more convenient way of managing collections of elements. Thus, if we use List as a return type of our flattening logic, or at least as an intermediate value holder, we can simplify the code:
@ParameterizedTest
@MethodSource("arrayProvider")
void giveTwoDimensionalArray_whenFlatWithForLoopAndAdditionalList_thenGetCorrectResult(
int [][] initialArray, int[] intArray) {
List<Integer> expected = Arrays.stream(intArray).boxed().collect(Collectors.toList());
List<Integer> actual = new ArrayList<>();
for (int[] numbers : initialArray) {
for (int number : numbers) {
actual.add(number);
}
}
assertThat(actual).isEqualTo(expected);
}
In this case, we don’t need to handle the expansion of a target array, and the List takes care of it transparently. We can also convert the arrays from the second dimension into Lists to leverage the addAll() method:
@ParameterizedTest
@MethodSource("arrayProvider")
void giveTwoDimensionalArray_whenFlatWithForLoopAndLists_thenGetCorrectResult(
int [][] initialArray, int[] intArray) {
List<Integer> expected = Arrays.stream(intArray).boxed().collect(Collectors.toList());
List<Integer> actual = new ArrayList<>();
for (int[] numbers : initialArray) {
List<Integer> listOfNumbers = Arrays.stream(numbers).boxed().collect(Collectors.toList());
actual.addAll(listOfNumbers);
}
assertThat(actual).isEqualTo(expected);
}
As we cannot use primitives with Collections, boxing creates significant overhead, and we should use it with caution. It’s better to avoid wrapper classes when the number of elements in an array is significant or when the performance is critical.
4. Stream API
Because these types of problems are quite common, Stream API provides a method to do the flattening more conveniently:
@ParameterizedTest
@MethodSource("arrayProvider")
void giveTwoDimensionalArray_whenFlatWithStream_thenGetCorrectResult(
int [][] initialArray, int[] expected) {
int[] actual = Arrays.stream(initialArray).flatMapToInt(Arrays::stream).toArray();
assertThat(actual).containsExactly(expected);
}
We used the flatMapToInt() method only because we’re working on primitive arrays. The solution for reference types would be similar, but we should use the flatMap() method. This is the most straightforward and most readable option. However, some understanding of the Stream API is required.
5. Conclusion
We don’t usually work on arrays directly. However, they are the most basic data structures, and knowing how to manipulate them is essential.
The System class, Collection, and Stream API provide many convenient methods to interact with arrays. However, we should always consider the drawbacks of these approaches and pick the most suitable one for our particular case.
As usual, the code is available over on GitHub.
