Regions Cut By Slashes

MediumGraphsunion find

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

An n x n grid of unit squares is described by grid, an array of n strings of length n. Each character is one of '/', '\\' (a single backslash), or ' ' (blank). A slash or backslash draws a diagonal line across its square, splitting it into two triangles; a blank leaves the square whole. Return the number of connected regions the whole grid is divided into. Note: in the examples the strings are written with JSON escaping, so "\\" represents a single backslash character.

Examples

Input: grid = [" /","/ "]
Output: 2
The two slashes form one continuous diagonal that splits the grid into two parts.
Input: grid = [" /"," "]
Output: 1
A single slash does not cut the grid all the way through.
Input: grid = ["/\\","\\/"]
Output: 5
The four diagonals form a diamond in the middle plus four corner triangles.

Constraints

  • `n == grid.length == grid[i].length`
  • `1 <= n <= 30`
  • `grid[i][j]` is `'/'`, `'\\'`, or `' '`

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More union find problems