Right Triangles - Practice Coding Problems

Right Triangles - Problem

You are given a 2D boolean matrix grid. 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 may not be next to each other. Return an integer that is the number of right triangles that can be made with 3 elements of grid such that all of them have a value of 1.

Input & Output

Example 1 — Basic Grid

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

› Output: 2

💡 Note: Two right triangles can be formed: (0,0)→(0,2)→(1,2) and (0,0)→(0,2)→(2,2). Each forms an L-shape with one vertex sharing row with another and column with the third.

Example 2 — No Triangles

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

› Output: 0

💡 Note: No three 1s can form a right triangle because no cell shares both a row and column with two other cells containing 1s.

Example 3 — Multiple Triangles

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

› Output: 6

💡 Note: With all cells being 1, many L-shaped triangles are possible. Each corner cell can form triangles with pairs from its row and column.

Constraints

1 ≤ grid.length ≤ 1000
1 ≤ grid[i].length ≤ 1000
grid[i][j] is either 0 or 1

Visualization

Tap to expand

Understanding the Visualization

Input Grid

2D boolean matrix with 1s and 0s

Find L-Shapes

Identify right triangles formed by three 1s

Count Total

Return total number of valid triangles

Key Takeaway

🎯 Key Insight: For each 1 as corner, multiply (remaining 1s in row) × (remaining 1s in column)

Asked in

G Google 25 f Meta 18 a Amazon 15 M Microsoft 12

The key insight is that for each cell with value 1, the number of right triangles with it as corner equals the product of remaining 1s in its row and column. Best approach is the optimized counting method with precomputed row/column counts. Time: O(m×n), Space: O(m+n)

Common Approaches

Approach	Time	Space	Notes
✓ Optimized - Count Row/Column 1s	O(m×n)	O(m+n)	Precompute counts of 1s in each row and column, then calculate triangles mathematically
Brute Force - Check All Triplets	O(n⁶)	O(1)	Check every possible combination of three 1s to see if they form a right triangle

Optimized - Count Row/Column 1s — Algorithm Steps

Count 1s in each row and column
For each cell with value 1, calculate remaining 1s in its row/column
Multiply row count × column count to get triangles for this corner
Sum up all triangles

Visualization

Tap to expand

Step-by-Step Walkthrough

Count 1s

Count 1s in each row and column

Calculate

For each 1, multiply remaining row × col counts

Sum

Add up all triangle counts

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int** grid, int rows, int cols) {
    // Count 1s in each row and column
    int* rowCount = (int*)calloc(rows, sizeof(int));
    int* colCount = (int*)calloc(cols, sizeof(int));
    
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            if (grid[i][j] == 1) {
                rowCount[i]++;
                colCount[j]++;
            }
        }
    }
    
    // For each cell with 1, calculate triangles
    int totalTriangles = 0;
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            if (grid[i][j] == 1) {
                // Subtract 1 because we don't count the cell itself
                int remainingInRow = rowCount[i] - 1;
                int remainingInCol = colCount[j] - 1;
                totalTriangles += remainingInRow * remainingInCol;
            }
        }
    }
    
    free(rowCount);
    free(colCount);
    return totalTriangles;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Simple parsing for [[1,0,1],[0,1,1],[0,1,1]] format
    int grid[100][100];
    int rows = 0, cols = 0;
    
    char* ptr = line + 1; // Skip first [
    while (*ptr && *ptr != ']') {
        if (*ptr == '[') {
            ptr++;
            cols = 0;
            while (*ptr && *ptr != ']') {
                if (*ptr >= '0' && *ptr <= '9') {
                    grid[rows][cols++] = *ptr - '0';
                }
                ptr++;
            }
            rows++;
        }
        ptr++;
    }
    
    // Convert to pointer array
    int* gridPtrs[100];
    for (int i = 0; i < rows; i++) {
        gridPtrs[i] = grid[i];
    }
    
    printf("%d\n", solution(gridPtrs, rows, cols));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(m×n)

Two passes through the grid: once to count, once to calculate triangles

✓ Linear Growth

Space Complexity

O(m+n)

Arrays to store row and column counts where m and n are grid dimensions

⚡ Linearithmic Space

23.4K Views

Medium Frequency

~15 min Avg. Time

847 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Optimized - Count Row/Column 1s — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler