Hash tables aren't cost free

Those of you who know me know that I'm a big fan of key;value pairs for solving problems, mainly using hash tables. But they aren't cost free. The problem below leads to a TLE if you use a hash table to store all the ones in the matrix (up to 1M ones). Interesting that all the tests pass but you still get a TLE. Solution is to replace the hash table with a simple array (a little more space being used) which does the trick. The code with the hash table that led to TLE is in the screenshot below, and the correct code written down below too. Cheers, ACC.

Right Triangles - LeetCode

3128. Right Triangles

Medium

You are given a 2D boolean matrix grid.

Return an integer that is the number of right triangles that can be made with the 3 elements of grid such that all of them have a value of 1.

Note:

• A collection of 3 elements of grid is a right triangle if one of its elements is in the same row with another element and in the same column with the third element. The 3 elements do not have to be next to each other.

 

Example 1:

0	1	0
0	1	1
0	1	0

0	1	0
0	1	1
0	1	0

Input: grid = [[0,1,0],[0,1,1],[0,1,0]]

Output: 2

Explanation:

There are two right triangles.

Example 2:

1	0	0	0
0	1	0	1
1	0	0	0

Input: grid = [[1,0,0,0],[0,1,0,1],[1,0,0,0]]

Output: 0

Explanation:

There are no right triangles.

Example 3:

1	0	1
1	0	0
1	0	0

1	0	1
1	0	0
1	0	0

Input: grid = [[1,0,1],[1,0,0],[1,0,0]]

Output: 2

Explanation:

There are two right triangles.

 

Constraints:

• 1 <= grid.length <= 1000
• 1 <= grid[i].length <= 1000
• 0 <= grid[i][j] <= 1

public long NumberOfRightTriangles(int[][] grid)
{
    int[] rowCountOnes = new int[grid.Length];
    int[] colCountOnes = new int[grid[0].Length];
    int[] rowOnes = new int[grid.Length * grid[0].Length];
    int[] colOnes = new int[grid.Length * grid[0].Length];
    int indexOnes = 0;

    for (int r = 0; r < grid.Length; r++)
    {
        for (int c = 0; c < grid[r].Length; c++)
        {
            if (grid[r][c] == 1)
            {
                int key = r * 1007 + c;
                rowOnes[indexOnes] = r;
                colOnes[indexOnes] = c;
                indexOnes++;
                rowCountOnes[r]++;
                colCountOnes[c]++;
            }
        }
    }

    long retVal = 0;
    for (int i = 0; i < indexOnes; i++)
    {
        int row = rowOnes[i];
        int col = colOnes[i];
        retVal += (rowCountOnes[row] - 1L) * (colCountOnes[col] - 1);
    }

    return retVal;
}