3394. Check if Grid can be Cut into Sections #63

iamAntimPal · 2025-03-25T02:43:01Z

iamAntimPal
Mar 25, 2025
Maintainer

🟩 3394. Check if Grid can be Cut into Sections

Medium | Grid | Geometry | Sorting

📝 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.
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:

We can make horizontal cuts at y = 2 and y = 4.

  -------------
5 | █ █ █ █    
  |█       █   
4 |█ █ █ █ █   
  |█       █   
3 |█ █   █ █   
  |█ █ █ █ █   
2 |█ █ █ █ █   
  -------------
1 |█ █ █ █ █   
  -------------
0  1 2 3 4 5

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.

🔹 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 <= 10^9
✅ 3 <= rectangles.length <= 10^5
✅ 0 <= rectangles[i][0] < rectangles[i][2] <= n
✅ 0 <= rectangles[i][1] < rectangles[i][3] <= n
✅ No two rectangles overlap.

💡 Approach & Hints

Sort rectangles by x or y coordinates.
Find possible cut positions that divide the grid into three valid sections.
Check if each section contains at least one rectangle.
Verify that rectangles do not cross the cuts.

🔹 If a valid set of two horizontal or two vertical cuts exists, return true, else return false.

⏳ Time Complexity Analysis

Sorting the rectangles takes O(m log m) where m is the number of rectangles.
Checking the conditions takes O(m).
Total Complexity: O(m log m) (which is efficient for m ≤ 10^5).

✍ Author

👤 Your Name
📧 your.email@example.com
🌐 [GitHub Profile](https://github.com/yourgithubprofile)

📢 Feel free to contribute by improving the solution or adding more test cases! 🚀


---

This **README.md** file includes:  
✅ **Clear problem statement**  
✅ **Examples with input/output and diagrams**  
✅ **Constraints and approach hints**  
✅ **Time complexity analysis**  

Let me know if you need any modifications! 😊🔥

Answered by iamAntimPal

Mar 25, 2025

solve that to contribute [organization]

View full answer

iamAntimPal · 2025-03-25T08:07:26Z

iamAntimPal
Mar 25, 2025
Maintainer Author

solve that to contribute [organization]

0 replies

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

3394. Check if Grid can be Cut into Sections #63

{{title}}

Replies: 1 comment

{{title}}

Select a reply

3394. Check if Grid can be Cut into Sections #63

iamAntimPal Mar 25, 2025 Maintainer

🟩 3394. Check if Grid can be Cut into Sections

📝 Problem Statement

🔹 Example 1

Input:

Output:

Explanation:

🔹 Example 2

Input:

Output:

Explanation:

🔹 Example 3

Input:

Output:

Explanation:

🛠 Constraints

💡 Approach & Hints

⏳ Time Complexity Analysis

✍ Author

Replies: 1 comment

iamAntimPal Mar 25, 2025 Maintainer Author

iamAntimPal
Mar 25, 2025
Maintainer

iamAntimPal
Mar 25, 2025
Maintainer Author