Logo
IconChallenge
Icon
IconProblem
IconSolutions
IconSubmissions

Check if Grid can be Cut into Sections

XPChallenge Points: 20
levelLevel: Medium

You are given a square grid of size n x n. The grid contains several non-overlapping rectangles. Each rectangle is described using four integers:

[startx, starty] = bottom-left corner [endx, endy] = top-right corner

Your task is to check whether it is possible to make:

  • Two horizontal cuts (parallel to x-axis), or

  • Two vertical cuts (parallel to y-axis)

so that:

  1. The cuts divide the grid into three sections.

  2. Every rectangle lies completely within exactly one section.

  3. Each section contains at least one rectangle.

Return true if such a division exists; otherwise return false.

Example 1:

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

Output: true

Explanation:

Three rectangles are naturally separated by vertical cuts at x = 2 and x = 4.

Example 2:

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

Output: false

Explanation:

n = 5 rectangles = [[0,0,3,3],[3,0,5,2],[3,2,5,5]]

Example 3:

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

Output: true

Explanation:

All rectangles align horizontally, but require 2 horizontal cuts, which would produce 4 sections instead of 3.

to Continue
like
dislike

Accepted:

Submission:

IconReport an issue
Icon
IconCode
IconYou need toto run or submitYou need toto run or submit
IconTest Case
IconTest Result