Get max length of row and column in java two dimensional array

Question

What is the best and efficient way to get the maximum i, which is the number of rows and j, which is the number of columns, in a two dimensional array?

Hopefully, the time complexity can be lower than O(n) for every case. No loop here and can still find the maximum j.

For example, if I have an array like this one

[
    [18,18,19,19,20,22,22,24,25,26],
    [1,2,3],
    [0,0,0,0]
]

Then I want to get i = 3 and j = 10 here as a result.

Can anyone help me?

Answer 1

You can avoid writing the loop yourself, but you can't avoid having a runtime of at least O(n), since "someone" needs to loop the source array.

Here is a possible way to do that in Java 8:

Arrays.stream(arr).map(row -> row.length).max(Integer::compare).get();

This returns the maximum length of a "row" in your 2d array:

10

Another version which avoids using the Comparator and therefore might be a bit easier to read:

Arrays.stream(arr).mapToInt(row -> row.length).max().getAsInt();

---

arr is supposed to be your source array.

Edit: the older version used .max(Integer::max), which is wrong and causes wrong results. See this answer for an explanation.

Answer 2

Assuming your array does not contain null values, you could write something like this:

private static final Comparator<int[]> lengthComparator = new Comparator<int[]> () {
    @Override
    public int compare(int[] o1, int[] o2) {
        return o1.length - o2.length;
    }
};

@Test
public void soArrayMaxLength() {

    int[][] array = new int[][] {
        {18,18,19,19,20, 22, 22, 24, 25,26},
        {1,2,3},
        {0,0,0,0}
    };

    int i = array.length;

    Optional<int[]> longestArray = 
            Arrays.stream(array)
            .max(lengthComparator);

    int j = longestArray.isPresent() ? longestArray.get().length : 0;

    System.out.println(String.format("i=%d j=%d", i, j));
}

If you happen to create a parallel stream from the array instead, you could speed up this even further.

Another option is to sort the array by length, the quicksort usually has an average complexity of O(n*log(n)) therefore this isn't faster;

    int i = array.length;
    Arrays.parallelSort(array, lengthComparator);

    int j = array[i-1].length;

    System.out.println(String.format("i=%d j=%d", i, j));

Answer 3

Your i is the number of rows, which is simply the length of the 2-D array (assuming you are OK with including empty/null rows in this count).

The max row length j, however, would require iterating over all the rows to find the row i having the maximum arr[i].length.

Answer 4

1. There will always be a loop¹, even though the looping will be implicit in solutions that use Java 8 streams.
2. The complexity of getting the max number of columns is O(N) where N is the number of rows.
3. Implicit looping using streams probably will be less efficient than explicit looping using for.

Here's a neat solution using a for loop

int max = o;
for (int i = 0; i < array.length; i++) {
    max = Math.max(max, array[i].length);
}

This works in the edge-case where array.length == 0, but if array or any array[i] is null you will get a NullPointerException. (You could modify the code to allow for that, but if the nulls are not expected, an NPE is probably a better outcome.)

---

^{1 - In theory, you could unroll the loops for all cases of array.length from 0 to Integer.MAX_VALUE, you would not need a loop. However, the code would not compile on any known Java compiler because it would exceed JVM limits on bytecode segments, etcetera. And the performance would be terrible for various reasons.}

Answer 5

You could try this way: loop on the array and find the max length of the arrays which is in this array

byte[][] arrs = new byte[3][];
int maxLength = 0;
for (byte[] array : arrs) {
    if (maxLength < array.length) {
        maxLength = array.length;
    }
}