Paths in Maze That Lead to Same Room - Practice Coding Problems

Paths in Maze That Lead to Same Room - Problem

Graph Medium

A maze consists of n rooms numbered from 1 to n, and some rooms are connected by corridors. You are given a 2D integer array corridors where corridors[i] = [room1i, room2i] indicates that there is a corridor connecting room1i and room2i, allowing a person in the maze to go from room1i to room2i and vice versa.

The designer of the maze wants to know how confusing the maze is. The confusion score of the maze is the number of different cycles of length 3.

For example, 1 → 2 → 3 → 1 is a cycle of length 3, but 1 → 2 → 3 → 4 and 1 → 2 → 3 → 2 → 1 are not.

Two cycles are considered to be different if one or more of the rooms visited in the first cycle is not in the second cycle.

Return the confusion score of the maze.

Input & Output

Example 1 — Basic Triangle

$ Input: n = 5, corridors = [[1,2],[2,3],[3,1]]

› Output: 1

💡 Note: There is exactly one cycle of length 3: 1 → 2 → 3 → 1. Rooms 4 and 5 are isolated and don't form any cycles.

Example 2 — Multiple Triangles

$ Input: n = 4, corridors = [[1,2],[2,3],[3,4],[4,1],[1,3]]

› Output: 2

💡 Note: There are exactly two cycles of length 3: 1 → 2 → 3 → 1 and 1 → 3 → 4 → 1. The corridor [1,3] participates in both triangles.

Example 3 — No Triangles

$ Input: n = 4, corridors = [[1,2],[2,3],[3,4]]

› Output: 0

💡 Note: This forms a simple path 1-2-3-4 with no cycles of length 3. All paths are longer than 3 or are not cycles.

Constraints

3 ≤ n ≤ 1000
0 ≤ corridors.length ≤ n × (n-1) / 2
corridors[i].length == 2
1 ≤ room1_i, room2_i ≤ n
room1_i ≠ room2_i
There are no duplicate corridors

Visualization

Tap to expand

Understanding the Visualization

Input Graph

Maze with rooms connected by corridors

Find Triangles

Identify cycles of exactly 3 rooms

Count Result

Return total number of distinct triangles

Key Takeaway

🎯 Key Insight: A triangle (3-cycle) exists when three rooms are all mutually connected - this creates maximum confusion as there are multiple valid paths between any two rooms in the triangle.

Asked in

f Facebook 15 G Google 12 M Microsoft 8

Find cycles of length 3 (triangles) in an undirected graph. The key insight is that a triangle exists when three rooms are all mutually connected. The adjacency list approach is optimal: for each room, check if pairs of its neighbors are connected to each other. Time: O(E × d), Space: O(E) where E is edges and d is max degree.

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Check All Triplets	O(n³)	O(E)	Check every possible combination of 3 rooms to see if they form a cycle
Adjacency List Optimization	O(E × d)	O(E)	For each room, check pairs of neighbors to see if they connect to each other

Brute Force - Check All Triplets — Algorithm Steps

Step 1: Generate all possible triplets of rooms (i, j, k)
Step 2: For each triplet, check if all three edges exist: (i,j), (j,k), (i,k)
Step 3: Count valid triangles

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Triplets

Create all possible combinations of 3 rooms

Check Edges

For each triplet, verify all 3 connections exist

Count Triangles

Count valid 3-cycles found

Code -

solution.c — C

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

#define MAX_EDGES 1000

typedef struct {
    int u, v;
} Edge;

int solution(int n, Edge corridors[], int numCorridors) {
    int count = 0;
    
    // Check all possible triplets
    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            for (int k = j + 1; k <= n; k++) {
                // Check if all three edges exist
                int hasIJ = 0, hasIK = 0, hasJK = 0;
                
                for (int e = 0; e < numCorridors; e++) {
                    int u = corridors[e].u, v = corridors[e].v;
                    if ((u == i && v == j) || (u == j && v == i)) hasIJ = 1;
                    if ((u == i && v == k) || (u == k && v == i)) hasIK = 1;
                    if ((u == j && v == k) || (u == k && v == j)) hasJK = 1;
                }
                
                if (hasIJ && hasIK && hasJK) {
                    count++;
                }
            }
        }
    }
    
    return count;
}

int main() {
    int n;
    scanf("%d", &n);
    
    char line[10000];
    fgets(line, sizeof(line), stdin); // consume newline
    fgets(line, sizeof(line), stdin);
    
    Edge corridors[MAX_EDGES];
    int numCorridors = 0;
    
    // Simple parsing for [[a,b],[c,d],...]
    char* ptr = line;
    while (*ptr) {
        if (*ptr == '[' && *(ptr+1) != '[') {
            int u, v;
            sscanf(ptr, "[%d,%d]", &u, &v);
            corridors[numCorridors].u = u;
            corridors[numCorridors].v = v;
            numCorridors++;
        }
        ptr++;
    }
    
    int result = solution(n, corridors, numCorridors);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n³)

Three nested loops to check all triplets of n rooms

⚠ Quadratic Growth

Space Complexity

O(E)

Set to store edges for fast lookup, where E is number of corridors

✓ Linear Space

23.4K Views

Medium Frequency

~25 min Avg. Time

856 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

Brute Force - Check All Triplets — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler