What is the quickest way to determine if two elements are in the same row or column in a 2D array?

Question

As part of one of my programs, I'm trying to check if two elements in a 2D array are part of the same row or column. I know there might be many ways to go about this, mainly with loops and by iterating through the array, but I was just wondering: is there any quick way to determine this?

Let's say I have a 2D array that looks like {{1, 2}, {3, 4}, {5, 6}}. Would there be any fast way to determine that 1 and 2 belong to the same row? Almost in a way that it could be evaluated in an if statement as "if item x belongs to the same row as item y, then do so and so"? If not, then what would be the quickest way otherwise?

WJS · Accepted Answer · 2021-04-17T17:08:00.340

Here's one approach for rows.

int[][] v = {{1, 2}, {3, 4}, {5, 6}};
System.out.println(rowContains(v, 2, 3));
System.out.println(rowContains(v, 5, 6));

Prints

false
true

The method

stream single d array and ignore duplicates
count filter on finding the values.
return true if any final count is 2.

public static boolean rowContains(int[][] v, int v1, int v2) {
    return Arrays.stream(v)
            .map(arrs -> Arrays.stream(arrs)
                    .distinct().filter(a -> a == v1 || a == v2)
                    .count()).anyMatch(a -> a == 2);
}

For columns, the easiest way would be to write a method to transpose the columns and rows and re-run the method.

score 1 · Answer 2 · 2021-04-17T13:34:26.573

This task is easier to solve with rows than with columns. You can use binarySearch method.

This solution also works with ragged 2d arrays and an unlimited number of elements to search for.

public static void main(String[] args) {
    int[][] arr = {{1, 2, 3}, {4, 5}, {6, 7, 8}};
    System.out.println(sameRow(arr, 4, 5)); // true
    System.out.println(sameCol(arr, 3, 8)); // true
}

/**
 * @param arr      2d array.
 * @param elements 1d array of elements to search for.
 * @return whether any column of a 2d array contains all elements from a 1d array.
 */
public static boolean sameCol(int[][] arr, int... elements) {
    return IntStream
            // iterate through the columns
            .iterate(0, i -> i + 1)
            // take an array of values from the column, if any
            .mapToObj(i -> Arrays
                    // iterate through the rows
                    .stream(arr)
                    // take those rows where this column is present
                    .filter(row -> row.length > i)
                    // take the value from the column
                    .mapToInt(row -> row[i])
                    // int[] - column
                    .toArray())
            // until the columns are still present
            .takeWhile(col -> col.length > 0)
            // whether any column contains all the search elements
            .anyMatch(col -> containsAll(col, elements));
}

/**
 * @param arr      2d array.
 * @param elements 1d array of elements to search for.
 * @return whether any row of a 2d array contains all elements from a 1d array.
 */
public static boolean sameRow(int[][] arr, int... elements) {
    return Arrays.stream(arr).anyMatch(row -> containsAll(row, elements));
}

/**
 * @param a first array.
 * @param b second array.
 * @return whether the first array contains all elements from the second array.
 */
public static boolean containsAll(int[] a, int[] b) {
    return Arrays.stream(b).allMatch(i -> Arrays.binarySearch(a, i) > -1);
}

^{See also:

• Filling a jagged 2d array first by columns

• Check if one array is a subset of the other array - special case}

score 0 · Answer 3 · 2021-04-18T00:55:38.460

This code works in Java 7 without streams. The approach is the same using binarySearch method. Ragged 2d arrays and an unlimited number of elements to search for are accepted.

And also with loops, this task is easier to solve with rows than with columns.

public static void main(String[] args) {
    int[][] arr = {{1, 2, 3}, {4, 5}, {6, 7, 8}};
    System.out.println(sameRow(arr, 4, 5));    // true
    System.out.println(sameCol(arr, 3, 8));    // true
    System.out.println(sameCol(arr, 2, 5, 7)); // true
}

/**
 * @param arr      2d array.
 * @param elements 1d array of elements to search for.
 * @return whether any column of a 2d array contains all elements from a 1d array.
 */
public static boolean sameCol(int[][] arr, int... elements) {
    // iterate through the columns
    for (int i = 0; ; i++) {
        // take an array of values from the column, if any
        int[] col = new int[arr.length];
        // column counter
        int j = 0;
        // iterate through the rows
        for (int[] row : arr)
            // take those rows where this column is present
            if (row.length > i)
                // take the value from the column
                // and increase the counter
                col[j++] = row[i];
        // until the columns are still present
        if (j == 0) break;
        // if this column contains all the search elements
        if (containsAll(Arrays.copyOf(col, j), elements))
            return true;
    }
    return false;
}

/**
 * @param arr      2d array.
 * @param elements 1d array of elements to search for.
 * @return whether any row of a 2d array contains all elements from a 1d array.
 */
public static boolean sameRow(int[][] arr, int... elements) {
    for (int[] row : arr)
        if (containsAll(row, elements))
            return true;
    return false;
}

/**
 * @param a first array.
 * @param b second array.
 * @return whether the first array contains all elements from the second array.
 */
public static boolean containsAll(int[] a, int[] b) {
    for (int i : b)
        if (Arrays.binarySearch(a, i) < 0)
            return false;
    return true;
}

What is the quickest way to determine if two elements are in the same row or column in a 2D array?

3 Answers3

Linked