Skip to main content
Talentd

Check if Grid can be Cut into Sections - Solution & Explanation

MediumArraySorting7 min readAsked at: Amazon, Google, Bloomberg
Practice this problem

Problem Statement

You are given an integer n representing the dimensions of an n x n grid, with the origin at the bottom-left corner of the grid. You are also given a 2D array of coordinates rectangles, where rectangles[i] is in the form [startx, starty, endx, endy], representing a rectangle on the grid. Each rectangle is defined as follows:

  • (startx, starty): The bottom-left corner of the rectangle.
  • (endx, endy): The top-right corner of the rectangle.

Note that the rectangles do not overlap. Your task is to determine if it is possible to make either two horizontal or two vertical cuts on the grid such that:

  • Each of the three resulting sections formed by the cuts contains at least one rectangle.
  • Every rectangle belongs to exactly one section.

Return true if such cuts can be made; otherwise, return false.

 

Example 1:

Input: n = 5, rectangles = [[1,0,5,2],[0,2,2,4],[3,2,5,3],[0,4,4,5]]

Output: true

Explanation:

The grid is shown in the diagram. We can make horizontal cuts at y = 2 and y = 4. Hence, output is true.

Example 2:

Input: n = 4, rectangles = [[0,0,1,1],[2,0,3,4],[0,2,2,3],[3,0,4,3]]

Output: true

Explanation:

We can make vertical cuts at x = 2 and x = 3. Hence, output is true.

Example 3:

Input: n = 4, rectangles = [[0,2,2,4],[1,0,3,2],[2,2,3,4],[3,0,4,2],[3,2,4,4]]

Output: false

Explanation:

We cannot make two horizontal or two vertical cuts that satisfy the conditions. Hence, output is false.

 

Constraints:

  • 3 <= n <= 109
  • 3 <= rectangles.length <= 105
  • 0 <= rectangles[i][0] < rectangles[i][2] <= n
  • 0 <= rectangles[i][1] < rectangles[i][3] <= n
  • No two rectangles overlap.

Approach Overview

Problem Overview: You are given multiple rectangles inside a grid. The task is to check whether two parallel cuts (either vertical or horizontal) can divide the grid into three sections such that each section contains at least one rectangle and no rectangle is intersected by a cut.

Approach 1: Brute Force Cut Simulation (O(n^2) time, O(1) space)

Try every possible pair of vertical cuts and every pair of horizontal cuts. For each candidate pair, iterate through all rectangles and verify whether every rectangle lies completely inside one of the three resulting sections. If a rectangle crosses a cut, the pair is invalid. This approach works conceptually but becomes slow because each candidate cut pair requires scanning all rectangles. It is mainly useful for reasoning about the problem constraints.

Approach 2: Interval Grouping with Sorting (O(n log n) time, O(n) space)

Instead of testing every cut location, observe that a valid cut must lie in the gap between rectangles. Project each rectangle onto one axis and treat it as an interval. For vertical cuts, use the x intervals [x1, x2]. Sort intervals by start coordinate and merge overlapping ones. Each merged block represents a continuous region where a cut cannot pass.

If the merged intervals form at least three disjoint groups, two cuts can be placed between these groups. The same process is repeated for the y intervals to check horizontal cuts. Sorting the intervals dominates the runtime, giving O(n log n) time with O(n) space for storing intervals.

This method relies on classic interval processing techniques from sorting and array scanning patterns from arrays. Instead of simulating cuts directly, you detect safe gaps where cuts can exist.

Recommended for interviews: The sorting + interval grouping approach is what interviewers expect. Brute force shows that you understand the geometric constraints, but the optimized method demonstrates the ability to transform the grid problem into interval merging using sorting. That reduction is the key insight.

Solution

Code

PythonJavaC++GoTypeScriptJavaScript

Python

Java

C++

Go

TypeScript

JavaScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Cut SimulationO(n^2)O(1)Conceptual baseline or very small inputs
Sorting + Interval GroupingO(n log n)O(n)General case; efficient for large number of rectangles

Video Solution

Check if Grid can be Cut into Sections | Merge Intervals | Leetcode 3394 | Leetcode 56 | Detailed • codestorywithMIK • 14,744 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Check if Grid can be Cut into Sections easy or hard?
The problem is rated Medium because the implementation is simple once you recognize the interval insight. The main challenge is realizing that valid cuts must lie between non-overlapping rectangle groups rather than testing every grid coordinate.
Check if Grid can be Cut into Sections Python/Java solution
Implement the interval approach: extract x-intervals and y-intervals from the rectangles, sort them, merge overlaps, and count disjoint segments. If either axis produces three or more segments, return true. This logic is straightforward to implement in Python, Java, C++, or JavaScript using standard sorting functions.
How to solve Check if Grid can be Cut into Sections in O(n log n)?
Project each rectangle to intervals along one axis, such as [x1, x2] for vertical cuts. Sort intervals by their start coordinate and merge overlaps while counting disjoint groups. If you find at least three non-overlapping groups, two cuts can be placed between them. Repeat the same process with y-intervals to check horizontal cuts.
What is the best approach for Check if Grid can be Cut into Sections?
The most efficient approach converts rectangles into intervals and sorts them. Project rectangles onto the x-axis and y-axis, merge overlapping intervals, and count how many disjoint groups remain. If at least three groups exist along either axis, two valid cuts can be placed between them. This runs in O(n log n) time due to sorting.
Is Check if Grid can be Cut into Sections asked at Google/Amazon/Meta?
Interval merging and geometric partitioning problems frequently appear in interviews at companies like Google, Amazon, and Meta. While this exact problem may vary, the underlying pattern of sorting intervals and detecting gaps is a common interview topic.
What data structure is used in Check if Grid can be Cut into Sections?
The solution mainly uses arrays or lists to store rectangle intervals. After sorting these intervals, a simple linear scan merges overlapping ranges and counts groups. No advanced data structures are required beyond sorting and basic array traversal.
What is the time complexity of Check if Grid can be Cut into Sections?
The optimal solution runs in O(n log n) time and O(n) space. Sorting the rectangle intervals dominates the runtime, while the merge scan itself is linear. A naive brute-force approach that tries all possible cut pairs can degrade to around O(n^2).

Ready to solve this problem?

Practice Check if Grid can be Cut into Sections with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays