I am solving this Leetcode Question Equal Row and Column Pair (;envId=leetcode-75), where the Problem description is

" Given a 0-indexed n x n integer matrix grid, return the number of pairs (r[i], c[j]) such that row r[i] and column c[j] are equal.

A row and column pair is considered equal if they contain the same elements in the same order (i.e., an equal array)."

I have used a HashMap and ArrayList to solve the question.

class Solution {
    public int equalPairs(int[][] grid) {
        //Two Hashmap to put each index and it's list of elements in the value.

        HashMap<Integer, ArrayList<Integer>> row=new HashMap<>(grid.length);
        HashMap<Integer, ArrayList<Integer>> col=new HashMap<>(grid.length);

        for(int i=0;i<grid.length;i++){
            ArrayList<Integer> rowAl=new ArrayList<>(grid.length);
            ArrayList<Integer> colAl=new ArrayList<>(grid.length);
            
            for(int j=0;j<grid.length;j++){
                rowAl.add(grid[i][j]);
                colAl.add(grid[j][i]);
            }
            
            row.put(i,rowAl);
            col.put(i,colAl);
        }
        
        int c=0;
        for(int k=0;k<row.size();k++){
            for(int l=0;l<col.size();l++){
                if(row.get(k).equals(col.get(l)))
                    c++;
            }
        }
        return c;
    }
}

And this gives me TLE in Test-Case 67, which consists of a whole grid of 1's.

But a similar solution with only array is submitted by someone else, which is accepted.

class Solution {
//getting a row
    List<Integer> getrow(int[][] grid, int in, int n) {
        List<Integer> x = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            x.add(grid[in][i]);
        }
        return x;
    }

    // getting a column
    List<Integer> getcol(int[][] grid, int in, int n) {
        List<Integer> x = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            x.add(grid[i][in]);
        }
        return x;
    }

    public int equalPairs(int[][] grid) {
        int c = 0;
        int n = grid.length;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (getrow(grid, i, n).equals(getcol(grid, j, n)))//checking if they are equal
                {
                    c++;
                }
            }
        }
        return c;
    }
}

I can't figure this out, someone please point it out. Thanks.

I am solving this Leetcode Question Equal Row and Column Pair (https://leetcode.com/problems/equal-row-and-column-pairs?envType=study-plan-v2&envId=leetcode-75), where the Problem description is

" Given a 0-indexed n x n integer matrix grid, return the number of pairs (r[i], c[j]) such that row r[i] and column c[j] are equal.

A row and column pair is considered equal if they contain the same elements in the same order (i.e., an equal array)."

I have used a HashMap and ArrayList to solve the question.

class Solution {
    public int equalPairs(int[][] grid) {
        //Two Hashmap to put each index and it's list of elements in the value.

        HashMap<Integer, ArrayList<Integer>> row=new HashMap<>(grid.length);
        HashMap<Integer, ArrayList<Integer>> col=new HashMap<>(grid.length);

        for(int i=0;i<grid.length;i++){
            ArrayList<Integer> rowAl=new ArrayList<>(grid.length);
            ArrayList<Integer> colAl=new ArrayList<>(grid.length);
            
            for(int j=0;j<grid.length;j++){
                rowAl.add(grid[i][j]);
                colAl.add(grid[j][i]);
            }
            
            row.put(i,rowAl);
            col.put(i,colAl);
        }
        
        int c=0;
        for(int k=0;k<row.size();k++){
            for(int l=0;l<col.size();l++){
                if(row.get(k).equals(col.get(l)))
                    c++;
            }
        }
        return c;
    }
}

And this gives me TLE in Test-Case 67, which consists of a whole grid of 1's.

But a similar solution with only array is submitted by someone else, which is accepted.

class Solution {
//getting a row
    List<Integer> getrow(int[][] grid, int in, int n) {
        List<Integer> x = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            x.add(grid[in][i]);
        }
        return x;
    }

    // getting a column
    List<Integer> getcol(int[][] grid, int in, int n) {
        List<Integer> x = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            x.add(grid[i][in]);
        }
        return x;
    }

    public int equalPairs(int[][] grid) {
        int c = 0;
        int n = grid.length;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (getrow(grid, i, n).equals(getcol(grid, j, n)))//checking if they are equal
                {
                    c++;
                }
            }
        }
        return c;
    }
}

I can't figure this out, someone please point it out. Thanks.

• java

• are we expected to know what exactly "Test-Case 67" is? We only know it is "a whole grid of 1's", but no idea how big that is, neither how long it is allowed to run before giving a TLE (Assuming it is Time Limit Exceeded) -- I also believe that writing a code to avoid TLE is part of the game (without asking on the internet) – user85421 Commented Jan 19 at 16:04
• Your HashMap solution times out due to overhead. Second, array-based solution, while using nested loops, avoids this by computing row/column lists only when needed for comparison (and breaks early if a mismatch is found), unlike your approach which stores and retrieves them repeatedly. This, plus the HashMap lookups, makes their solution significantly faster (so no timeout). Don't over-engineer something which doesn't need that. – TheTanadu Commented Jan 19 at 16:08
• actually posted code should not compile: 1) Integer does not have a method value() at if(k.value().equals(l.value())); 2) undeclared c at c++; (probably count++?) – user85421 Commented Jan 19 at 16:14
• BTW2 I also tested both codes with my local installation and JMH - the first code is at least 2 times faster than the second one (2.0 times faster for n=5, 3.5 for n=10, 12.8 for n=50 - all 1's) - I wonder how you got Time Limit Exceeded with the first and not with the second one? – user85421 Commented Jan 19 at 17:07
• @user85421 i know I am supposed to write a around the TLE but out of 80 test cases, the 67 fails. Since the input array is a n*n grid, it's all populated with lots of 1, I couldn't even count them. – Kushagra Srivastava Commented Jan 19 at 17:44

1 Answer 1

Let's gut the path of your code..

given the following matrix:

int[][] matrix = {
   { 3, 2, 1 },
   { 1, 7, 6 },
   { 2, 7, 7 }
};

what is stored in each iteration, with your code:

for( int i = 0; i < grid.length; i++ ) {                       
    for( int j = 0; j < grid.length; j++ ) {
        rowAl.add( grid[i][j] );
        colAl.add( grid[j][i] );
    }            
}

i = 0 ->
    rowAl = 3, 2, 1
    colAl = 3, 1, 2

i = 1 ->
    rowAl = 1, 7, 6
    colAl = 2, 7, 7

i = 2 ->
    rowAl = 2, 7, 7
    colAl = 1, 6, 7

as you can see, a lot of checks are missing... let's try another way:

let's start from the premise, if I already have the information stored, I have nothing to store.

public int equalPairs( int[][] grid ) {
   int count = 0;
   boolean areEquals = true;

   for( int row = 0; row < grid.length; row ++ ) {

      for( int col = 0; col < grid.length; col ++ ) {
         areEquals = true;

         for( int recorre = 0; recorre < grid.length; recorre ++ ) {
            if( grid[ row ][ recorre ] != grid[ recorre ][ col ] ) {
               areEquals = false;
               break;
            }
         }
         if( areEquals ) count ++;
      }
   }
   return count;
} 

the first for selects the row, the second selects the column, and the third one is in charge of going through them comparing.