CODEWITHSUNDEEP
javaalgorithmmatrix
Sergio
Sergio

Reputation: 354

How to check if two matrices have an identical row?

I'm trying to develop an algorithm in Java, which, given two matrices (let's say a and b), returns true if at least one row is identical in a and b.

Here's my attempt of method:

public static boolean check_row(int a[][], int b[][]){
        boolean check = false;
        for(int i = 0; i < a.length; i++){
            for(int j = 0; j < b[0].length; j++){
                if(a[i][j] == b[i][j])
                    check = true;
            }
        }
        return check;
    }

And here's a simple main:

public static void main(String[] args){
        int a[][] = {{1,2}, {3,4}};
        int b[][] = {{1,2}, {7,8}};
        System.out.println(check_row(a, b));
    }

Here I get true because first row of both matrices is the same. But if I change the matrices initialization to this: 

int a[][] = {{1,2}, {3,4}};
int b[][] = {{5,6}, {1,2}};

I get false, even though the first row of a and the second row of b are identical.

How should I modify the method in order to get true in both cases?

Upvotes: 4

Views: 1343

Answers (4)

jihor
jihor

Reputation: 2599

In the example provided by OP, the loop over rows in b matrix was missing.

When learning, the algorithm can be written as follows:

public static boolean check_row(int a[][], int b[][]) {
    int row_size = a[0].length;
    for (int i = 0; i < a.length; i++) {
        b: for (int j = 0; j < b.length; j++) {
            for (int k = 0; k < row_size; k++) {
                if (a[i][k] != b[j][k])
                    continue b; // move to next row in 'b' matrix
            }
            return true; // all elements in row were equal if we reached this point
        }
    }
    return false;
}

In real life it would probably look like this:

public static boolean check_row(int[][] a, int[][] b) {
    return Arrays.stream(b)
                 .anyMatch(rowB -> Arrays.stream(a).anyMatch(rowA -> Arrays.equals(rowA, rowB)));
}

Upvotes: 1

parsa
parsa

Reputation: 995

i hope this code can help you 

public static boolean check_row(int a[][], int b[][])
{
    boolean check = false;

    for(int i = 0; i < a.length; i++)
    {

        for(int k = 0 ; k< b.length ; k++)
        {

            for(int j = 0 ; j<b[0].length ; j++)
            {
                if(a[i][j]!=b[k][j])
                {
                    break;
                }//if even one cell were not similar in both a and b break
                else
                {
                    if(j==b[0].length-1)
                    {
                        check = true;
                    }//if you haven't broken the loop yet and if j went till the end
                }//else if they are equal

            }//j to go through columns
            if(check == true)
            {
               break;
            }//for bringing down the time complexity
        }//k to go through b rows
        if(check == true)
        {
           break;
        }//for bringing down the time complexity
    }//i
    return check;
}

Upvotes: 0

Mathias G.
Mathias G.

Reputation: 5105

You have an error in your 2nd loop. Change:

for(int j = 0; j < b[0].length; j++)

to

for(int j = 0; j < b.length; j++){

Further, the issue is that you cannot compare the rows like you do it. You have to check that the rows have the same length and finally compare the rows. You will need an additional for loop for comparing the rows.

This one will do the trick:

public static boolean check_row(int a[][], int b[][]){
    boolean check = false;
    for(int i = 0; i < a.length; i++){
        for(int j = 0; j < b.length; j++){
            if (compareRows(a[i], b[j]))
                check = true;
        }
    }
    return check;
}

private static boolean compareRows(int[] row1, int[] row2) {
    if (row1.length == row2.length) {
        for (int i = 0; i < row2.length; i++) {
            if (row1[i] != row2[i]) {
                return false;
            }
        }
        return true;
    }
    return false;
}

public static void main(String[] args){
    int a[][] = {{1,2},{3,4}};
    int b[][] = {{5,6}, {1,2}};
    System.out.println(check_row(a, b));
}

Upvotes: 2

Betlista
Betlista

Reputation: 10547

Your condition is too simple... High level idea is, that for each row from a and b pick a row and then identify whether it is the same, so you need 3 loops...

code:

public class SameRowFinder {

    public static void main(String[] args){
        int a[][] = {{1,2},{3,4}};
        int b[][] = {{1,2}, {7,8}};
        System.out.println(hasSameRow(a, b));

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

    private static boolean hasSameRow(int[][] a, int[][] b) {
        for (int i = 0; i < a.length; i++) {
            for (int j = 0; j < b.length; j++) {
                if (isSameRow(a[i], b[j])) {
                    System.out.printf("Same rows are %d and %d (0-based).%n", i, j);
                    return true;
                }
            }
        }
        return false;
    }

    private static boolean isSameRow(int[] row1, int[] row2) {
        if (row1.length != row2.length) {
            throw new IllegalArgumentException("rows with different length");
        }
        for (int i = 0; i < row2.length; i++) {
            if (row1[i] != row2[i]) {
                return false;
            }
        }
        return true;
    }
}

Also you do not need to write your own function for array compare, but use Arrays.equal(int[], int[]), but it will just hide 3rd loop. Method above throws runtime exception in case of different length of arrays. It's definitelly worth look at Arrays.equal(int[], int[]) implementation for some tips (check for equality + null checks).

Upvotes: 7

Related Questions