Right Triangles

Right Triangles

What is this problem about?

The Right Triangles interview question gives you a binary matrix and asks you to count the number of right triangles that can be formed using three cells that contain 1. A right triangle is formed when one of the three 1-cells lies at the right-angle vertex, meaning the three cells share either the same row or column at the vertex. Specifically, you count triplets where one cell shares a row with the vertex and another shares a column with it.

Why is this asked in interviews?

Mitsogo and Google ask this problem because it combines combinatorics with efficient row and column counting — moving beyond brute force (O(n^3)) to an O(n^2) solution. It tests whether candidates can translate geometric conditions into counting formulas using precomputed row and column sums, a technique central to combinatorics interview patterns.

Algorithmic pattern used

The pattern is combinatorics with precomputed row and column counts. For each cell (i, j) with value 1, the number of right triangles with the right angle at (i, j) is (row_count[i] - 1) * (col_count[j] - 1) — choosing one other 1 from the same row (excluding the vertex) and one from the same column (excluding the vertex). Precompute row_count[i] = number of 1s in row i, and col_count[j] = number of 1s in column j. Sum across all 1-cells.

Example explanation

Matrix:

1 0 1
0 1 0
1 0 1

Row counts: [2, 1, 2]. Col counts: [2, 1, 2].

For cell (0,0) — value 1: (2-1)(2-1) = 1. For cell (0,2) — value 1: (2-1)(2-1) = 1. For cell (1,1) — value 1: (1-1)(1-1) = 0. For cell (2,0) — value 1: (2-1)(2-1) = 1. For cell (2,2) — value 1: (2-1)*(2-1) = 1.

Total: 4 right triangles.

Common mistakes candidates make

• Using a brute-force O(n^3) triple nested loop to check all triplets.
• Not subtracting 1 from row and column counts — the vertex cell itself must be excluded from the choices.
• Forgetting to handle cells with value 0 — only process cells where grid[i][j] == 1.
• Confusing "right triangle" with "any triangle" — only the specific right-angle configuration is counted.

Interview preparation tip

For the Right Triangles coding problem, the array, math, and counting interview pattern eliminates brute force via combinatorial counting. Precompute row and column sums before the main counting loop. Google interviewers value candidates who immediately reduce the problem to a per-cell multiplication of (row_ones - 1) * (col_ones - 1) — explaining the combinatorial insight before coding earns significant credit.