LeetCode 3128 - Right Triangles

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Math, Combinatorics, Counting

Solution

Problem Understanding

The problem gives us a binary matrix grid, where each cell contains either 0 or 1. We need to count how many valid right triangles can be formed using cells whose value is 1.

A valid right triangle in this problem is defined by selecting exactly three cells containing 1 such that:

One chosen cell shares the same row with another chosen cell.
That same chosen cell also shares the same column with the third chosen cell.

This means one cell acts as the right angle vertex. From that pivot cell:

One other 1 must exist somewhere else in the same row.
Another 1 must exist somewhere else in the same column.

The three cells do not need to be adjacent. Their relative positions can be far apart.

For example, suppose a cell (r, c) contains 1. If there are:

x other 1s in row r
y other 1s in column c

then that cell can serve as the right angle of x * y different right triangles.

The input constraints are important:

Up to 1000 rows
Up to 1000 columns

This means the grid may contain up to 1,000,000 cells. Any solution that tries all triples of cells will be far too slow.

Several edge cases are important:

A row may contain only one 1, making it impossible to form the horizontal leg of a triangle.
A column may contain only one 1, making it impossible to form the vertical leg.
A grid full of 0s should return 0.
A single row or single column can never form a valid right triangle because both a row relationship and a column relationship are required.
Multiple 1s in the same row or column alone are not enough, the pivot must connect both dimensions simultaneously.

Approaches

Brute Force Approach

A brute force solution would attempt to examine every possible combination of three cells in the grid and check whether:

All three cells contain 1
One of the cells shares a row with another cell
That same cell shares a column with the third cell

If the grid contains k cells with value 1, then there are:

$$\binom{k}{3}$$

possible triples to check.

In the worst case, the entire grid is filled with 1s, so:

$$k = 10^6$$

Trying all triples becomes computationally impossible.

Even if we optimize the validation step, the sheer number of combinations makes this approach infeasible.

Optimal Approach

The key observation is that every valid triangle is uniquely determined by its right angle vertex.

Suppose cell (r, c) contains 1.

Let rowCount[r] be the number of 1s in row r
Let colCount[c] be the number of 1s in column c

To form a right triangle with (r, c) as the pivot:

We need another 1 in the same row, there are rowCount[r] - 1 choices.
We need another 1 in the same column, there are colCount[c] - 1 choices.

Therefore, the number of triangles contributed by cell (r, c) is:

$$(rowCount[r] - 1) \times (colCount[c] - 1)$$

We simply compute this value for every cell containing 1 and sum the results.

This transforms the problem into a counting problem instead of a geometric enumeration problem.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(k³)	O(1)	Checks every triple of `1` cells
Optimal	O(m × n)	O(m + n)	Counts row and column frequencies

Here:

m = number of rows
n = number of columns
k = number of cells containing 1

Algorithm Walkthrough

Determine the dimensions of the grid.

We need the number of rows and columns so we can iterate efficiently through the matrix. 2. Count the number of 1s in each row.

Create an array rowCount where:

$$rowCount[r]$$

stores how many cells in row r contain 1.

This allows us to instantly know how many horizontal partners any cell has. 3. Count the number of 1s in each column.

Create another array colCount where:

$$colCount[c]$$

stores how many cells in column c contain 1.

This allows us to instantly know how many vertical partners any cell has. 4. Traverse the grid again.

For every cell (r, c):

Skip the cell if it contains 0.
Otherwise, compute:

$$(rowCount[r] - 1) \times (colCount[c] - 1)$$

This represents:

the number of possible horizontal choices
multiplied by the number of possible vertical choices

Add the contribution to the answer.

Sum the contribution from every pivot cell. 6. Return the final count.

Why it works

Every valid right triangle has exactly one right angle vertex. When we process a cell (r, c) containing 1, we count every possible pair formed by:

another 1 in the same row
another 1 in the same column

Each unique pair corresponds to exactly one valid triangle with (r, c) as the pivot. Since every triangle has exactly one pivot, every valid triangle is counted exactly once.

Python Solution

from typing import List

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

        row_count = [0] * rows
        col_count = [0] * cols

        # Count 1s in each row and column
        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == 1:
                    row_count[r] += 1
                    col_count[c] += 1

        result = 0

        # Count triangles using each 1-cell as the pivot
        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == 1:
                    horizontal_choices = row_count[r] - 1
                    vertical_choices = col_count[c] - 1

                    result += horizontal_choices * vertical_choices

        return result

The implementation begins by determining the grid dimensions. Two arrays are then allocated:

row_count stores how many 1s exist in each row.
col_count stores how many 1s exist in each column.

The first traversal computes these counts. This preprocessing step is essential because it allows constant-time access to row and column frequencies later.

The second traversal evaluates every cell containing 1. For each such cell:

row_count[r] - 1 gives the number of valid horizontal partners.
col_count[c] - 1 gives the number of valid vertical partners.

Their product gives the number of triangles formed using that cell as the right angle vertex.

The final answer accumulates contributions from all pivot cells.

Go Solution

func numberOfRightTriangles(grid [][]int) int64 {
	rows := len(grid)
	cols := len(grid[0])

	rowCount := make([]int, rows)
	colCount := make([]int, cols)

	// Count 1s in rows and columns
	for r := 0; r < rows; r++ {
		for c := 0; c < cols; c++ {
			if grid[r][c] == 1 {
				rowCount[r]++
				colCount[c]++
			}
		}
	}

	var result int64 = 0

	// Count triangles
	for r := 0; r < rows; r++ {
		for c := 0; c < cols; c++ {
			if grid[r][c] == 1 {
				horizontalChoices := rowCount[r] - 1
				verticalChoices := colCount[c] - 1

				result += int64(horizontalChoices * verticalChoices)
			}
		}
	}

	return result
}

The Go implementation follows the same algorithmic structure as the Python solution.

One important difference is the use of int64 for the result. The number of triangles can become large because the grid may contain up to one million cells. Using int64 prevents overflow.

Slices are used for rowCount and colCount, which provide dynamic arrays similar to Python lists.

Worked Examples

Example 1

grid =
[
  [0,1,0],
  [0,1,1],
  [0,1,0]
]

Step 1: Compute Row Counts

Row	Number of 1s
0	1
1	2
2	1

So:

rowCount = [1, 2, 1]

Step 2: Compute Column Counts

Column	Number of 1s
0	0
1	3
2	1

So:

colCount = [0, 3, 1]

Step 3: Evaluate Each 1 Cell

Cell	Horizontal Choices	Vertical Choices	Contribution
(0,1)	0	2	0
(1,1)	1	2	2
(1,2)	1	0	0
(2,1)	0	2	0

Total:

Example 2

grid =
[
  [1,0,0,0],
  [0,1,0,1],
  [1,0,0,0]
]

Row Counts

rowCount = [1, 2, 1]

Column Counts

colCount = [2, 1, 0, 1]

Contributions

Cell	Horizontal Choices	Vertical Choices
(0,0)	0	1
(1,1)	1	0
(1,3)	1	0
(2,0)	0	1

Total:

Example 3

grid =
[
  [1,0,1],
  [1,0,0],
  [1,0,0]
]

Row Counts

rowCount = [2, 1, 1]

Column Counts

colCount = [3, 0, 1]

Contributions

Cell	Horizontal Choices	Vertical Choices	Contribution
(0,0)	1	2	2
(0,2)	1	0	0
(1,0)	0	2	0
(2,0)	0	2	0

Total:

Complexity Analysis

Measure	Complexity	Explanation
Time	O(m × n)	Two full traversals of the grid
Space	O(m + n)	Row and column count arrays

The algorithm scans the matrix twice:

Once to compute row and column counts
Once to compute triangle contributions

Each traversal processes every cell exactly once, leading to linear complexity relative to the size of the grid.

The auxiliary memory consists only of:

one row frequency array
one column frequency array

No additional structures proportional to the total number of cells are required.

Test Cases

from typing import List

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

        row_count = [0] * rows
        col_count = [0] * cols

        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == 1:
                    row_count[r] += 1
                    col_count[c] += 1

        result = 0

        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == 1:
                    result += (row_count[r] - 1) * (col_count[c] - 1)

        return result

sol = Solution()

assert sol.numberOfRightTriangles([
    [0,1,0],
    [0,1,1],
    [0,1,0]
]) == 2  # Example 1

assert sol.numberOfRightTriangles([
    [1,0,0,0],
    [0,1,0,1],
    [1,0,0,0]
]) == 0  # Example 2

assert sol.numberOfRightTriangles([
    [1,0,1],
    [1,0,0],
    [1,0,0]
]) == 2  # Example 3

assert sol.numberOfRightTriangles([
    [0]
]) == 0  # Single zero cell

assert sol.numberOfRightTriangles([
    [1]
]) == 0  # Single one cell

assert sol.numberOfRightTriangles([
    [1,1,1]
]) == 0  # Single row cannot form triangles

assert sol.numberOfRightTriangles([
    [1],
    [1],
    [1]
]) == 0  # Single column cannot form triangles

assert sol.numberOfRightTriangles([
    [1,1],
    [1,1]
]) == 4  # Every cell contributes one triangle

assert sol.numberOfRightTriangles([
    [0,0],
    [0,0]
]) == 0  # No ones at all

assert sol.numberOfRightTriangles([
    [1,0,1],
    [0,1,0],
    [1,0,1]
]) == 0  # Diagonal style placement, no valid pivot

assert sol.numberOfRightTriangles([
    [1,1,1],
    [1,1,1],
    [1,1,1]
]) == 36  # Dense grid stress test

Test	Why
Example 1	Verifies standard valid triangle counting
Example 2	Verifies no accidental counting
Example 3	Verifies vertical-heavy arrangement
`[[0]]`	Smallest empty grid
`[[1]]`	Single cell cannot form triangle
Single row	Requires both row and column relationships
Single column	Requires both row and column relationships
2×2 all ones	Every cell acts as a pivot
All zeros	No valid cells
Diagonal pattern	Ensures geometric condition is enforced
3×3 all ones	Stress test with many combinations

Edge Cases

One important edge case is a grid with only one row or one column. A right triangle requires both a horizontal leg and a vertical leg. In a single-row grid, no vertical partner can exist. In a single-column grid, no horizontal partner can exist. The implementation naturally handles this because either rowCount[r] - 1 or colCount[c] - 1 becomes zero for every cell.

Another important case is when the grid contains many isolated 1s. A naive implementation might incorrectly count pairs that only align in one direction. The formula avoids this problem because both row and column counts must contribute positively. If either side lacks a partner, the multiplication produces zero.

A dense grid full of 1s is also important. This creates the maximum number of triangles and stresses both performance and integer range. The algorithm remains efficient because it still processes each cell only twice. In Go, the implementation uses int64 to avoid overflow when accumulating large triangle counts.

A subtle edge case occurs when multiple 1s exist in the same row or same column, but no valid pivot exists. For example, three 1s all in a straight vertical line should not count as a triangle. The algorithm handles this correctly because a valid pivot must simultaneously have another 1 in its row and another 1 in its column.