Teaching Kids Programming – Using Hash Map to Count the Right Triangles in a Binary Matrix

Teaching Kids Programming: Videos on Data Structures and Algorithms

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

Hints:
If grid[x][y] is 1, it can form a right triangle with an element of grid with value 1 in the same row and an element of grid with value 1 in the same column.
Hint 2
So we just need to count the number of 1s in each row and column.
Hint 3
For each x, y with grid[x][y] = 1 if there are row[x] 1s in the row x and col[y] 1s in column y, the answer should be added by (row[x] – 1) * (col[y] – 1).

Using Hash Map to Count the Right Triangles in a Binary Matrix

Each right triangle can be identified by the 1 in the right angle, thus we just have to count the number of 1’s in each row and each column respectively. Then the number of the right triangles can be calculated as the sum of (row[x] – 1) * (col[y] – 1) where x, and y are the indices for rows and columns.

The time/space complexity is O(RC) where R and C are the number of the rows and columns for the matrix. The first pass we go through the matrix and count the 1’s in the hash map. The second pass we accumulate the answer.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

class Solution:
    def numberOfRightTriangles(self, grid: List[List[int]]) -> int:
        rows = len(grid)
        cols = len(grid[0])
 
        r = Counter()
        c = Counter()
        for rr in range(rows):
            for cc in range(cols):
                if grid[rr][cc]:
                    r[rr] += 1
                    c[cc] += 1
 
        ans = 0
        for rr in range(rows):
            for cc in range(cols):
                if grid[rr][cc]:
                    ans += (r[rr]-1) * (c[cc]-1)
        
        return ans

class Solution:
    def numberOfRightTriangles(self, grid: List[List[int]]) -> int:
        rows = len(grid)
        cols = len(grid[0])

        r = Counter()
        c = Counter()
        for rr in range(rows):
            for cc in range(cols):
                if grid[rr][cc]:
                    r[rr] += 1
                    c[cc] += 1

        ans = 0
        for rr in range(rows):
            for cc in range(cols):
                if grid[rr][cc]:
                    ans += (r[rr]-1) * (c[cc]-1)
        
        return ans

–EOF (The Ultimate Computing & Technology Blog) —