What is the brute force approach and complexity for Regions Cut By Slashes?

Scale each square to 3 × 3 pixels, draw the slashes as walls, count the flood fills with time complexity O(N²) and space complexity O(N²).

What is the optimal approach and complexity for Regions Cut By Slashes?

Union the triangles a slash keeps together, plus the triangles that meet across each edge; count groups with optimal time complexity O(N² · α(N²)) and space complexity O(N²).

How do you identify the pattern for Regions Cut By Slashes?

Look for key signals in the prompt: "regions cut by slashes" indicates The regions are what remains after cutting, so count groups of pieces that touch.; "each character splits a square" indicates A slash decides which sides of the square belong together → union the sides per character.; "cells touch their neighbours" indicates Shared edges link the pieces of neighbouring squares → one more union per edge..

Regions Cut By Slashes

Medium·LeetCode #959 Pro OnlyPattern Transfer

LeetCode

Problem Statement

You get an n × n board of 1 × 1 squares. Each square holds one of three characters: a forward slash /, a backslash \, or a blank space. The lines cut the board into pieces, and the pieces that touch each other form regions.

Return the number of regions.

In C++ a single backslash is written \\ inside a string, so the row /\ is written "/\\" in the examples below.

Input

grid, a list of n strings. Each string has length n and holds only /, \ or a space.

Output

One integer: the number of regions.

Example 1

Input: grid = [" /", "/ "]

Output: 2

The two slashes join into one line from the top-right corner to the bottom-left corner. It cuts the board into the top-left half and the bottom-right half.

Example 2

Input: grid = [" /", " "]

Output: 1

One slash in the top-right square. The blank squares around it still touch each other, so the board stays in one piece.

Example 3

Input: grid = ["/\\", "\\/"]

Output: 5

The four slashes form a diamond. The inside of the diamond is one region, and each of the four outer corners is its own region.

Constraints

• n == grid.length == grid[i].length
• 1 ≤ n ≤ 30
• grid[i][j] is '/', '\' or a space.

Pattern Recognition Clues

Recognising these key signals in the problem description immediately identifies the pattern:

“regions cut by slashes”

→ The regions are what remains after cutting, so count groups of pieces that touch.

“each character splits a square”

→ A slash decides which sides of the square belong together → union the sides per character.

“cells touch their neighbours”

→ Shared edges link the pieces of neighbouring squares → one more union per edge.

Approach Complexity Ladder

Brute Force — 3 × 3 pixels and a flood fillO(N²)O(N²)

Scale each square to 3 × 3 pixels, draw the slashes as walls, count the flood fills

Optimal — four triangles per square, one DSUO(N² · α(N²))O(N²)

Union the triangles a slash keeps together, plus the triangles that meet across each edge; count groups

Brute Force Intuition

Turn each square into a 3 × 3 block of pixels. A / turns the three diagonal pixels from bottom-left to top-right into walls, and a \ does the same from top-left to bottom-right. Then count the flood fills: every open pixel that is not yet visited starts one region.

Recognition rule for this sub-pattern:

Start with n groups; each successful union reduces the count by one.

Remember this · Union-Find (DSU)

Trigger

Edges arrive one by one, "are these connected?", merge equivalent items, count components, extra edge creating a cycle.

Think

Am I repeatedly merging groups and asking whether two things are in the same group?

Key question

What are the elements, and what does it mean to union two of them?

Brute2Best Pro Content

Unlock Complete Visual Walkthrough & Optimal C++

The interactive animated dry-run player, optimized C++ implementation, state invariant derivations, and edge-case breakdown for this question are part of Brute2Best Pro. The anchor question of every sub-pattern is completely free.

All 440 visual dry runs & algorithms

Interactive step-by-step playback with pointer & array state transitions

52 comprehensive LLD chapters

Interactive UML diagrams, real-world stories (Food Delivery, Trading, RPG), and practice solutions

40 C++ basics labs & hardware memory models

Vtables, byte layouts, assembly insights, and multi-threading race conditions

Production-ready C++23 source code

Modern idioms, clean contracts, time/space complexity derivations, and interview takeaways

Create Free Account Log in

First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Union-Find (DSU) translate into production architectures and low-level memory mechanics.

LLD Architecture