Check if Grid can be Cut into Sections - Practice Coding Problems

Check if Grid can be Cut into Sections - Problem

Array Sorting Medium

You are given an integer n representing the dimensions of an n × 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 [start_x, start_y, end_x, end_y], representing a rectangle on the grid.

Each rectangle is defined as follows:

(start_x, start_y): The bottom-left corner of the rectangle.
(end_x, end_y): 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.

Input & Output

Example 1 — Valid Horizontal Cuts

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

› Output: true

💡 Note: We can make horizontal cuts at y=3 and y=4. This creates three sections: bottom (y≤3) contains rectangles [0,0,3,3] and [3,0,5,5], middle (3

Example 2 — No Valid Cuts

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

› Output: false

💡 Note: Only two rectangles exist in opposite corners. Any two cuts will create three sections, but the middle section will always be empty since rectangles don't span the middle area.

Example 3 — Valid Vertical Cuts

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

› Output: true

💡 Note: We can make vertical cuts at x=2 and x=4. This creates three sections: left (x≤2) contains [0,0,2,6], middle (24) contains [4,0,6,6].

Constraints

3 ≤ n ≤ 10⁹
3 ≤ rectangles.length ≤ 10⁵
rectangles[i].length == 4
0 ≤ start_x < end_x ≤ n
0 ≤ start_y < end_y ≤ n
All rectangles are mutually disjoint

Visualization

Tap to expand

Understanding the Visualization

Input Grid

n×n grid with non-overlapping rectangles positioned by coordinates

Find Cuts

Identify two parallel cuts (horizontal or vertical) that create 3 sections

Validate

Each section must contain at least one complete rectangle

Key Takeaway

🎯 Key Insight: Valid cuts must align with rectangle boundaries to cleanly separate them into exactly three non-empty sections

Asked in

G Google 15 M Meta 12 a Amazon 8

Brief HTML summary: The key insight is that valid cuts must align with rectangle boundaries to ensure clean separation. We extract all possible cut positions from rectangle coordinates and systematically test pairs. Best approach uses coordinate sorting with optimized validation. Time: O(n³), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force	O(n³)	O(n)	Try all possible pairs of horizontal and vertical cuts
Optimized Coordinate Processing	O(n³)	O(n)	Sort coordinates once and use efficient validation

Brute Force — Algorithm Steps

Step 1: Extract all possible horizontal and vertical cut positions from rectangle boundaries
Step 2: Try every pair of horizontal cuts, check if each section has at least one rectangle
Step 3: Try every pair of vertical cuts, check if each section has at least one rectangle
Step 4: Return true if any valid pair is found

Visualization

Tap to expand

Step-by-Step Walkthrough

Extract Coordinates

Collect all unique x and y coordinates from rectangle boundaries

Try Cut Pairs

For each pair of coordinates, check if they create valid sections

Validate Sections

Ensure each of the 3 sections contains at least one rectangle

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

bool canCutHorizontally(int rectangles[][4], int rectCount) {
    int yCoords[1000], yCount = 0;
    
    // Collect unique y coordinates
    for (int i = 0; i < rectCount; i++) {
        int startY = rectangles[i][1], endY = rectangles[i][3];
        
        bool foundStart = false, foundEnd = false;
        for (int j = 0; j < yCount; j++) {
            if (yCoords[j] == startY) foundStart = true;
            if (yCoords[j] == endY) foundEnd = true;
        }
        if (!foundStart) yCoords[yCount++] = startY;
        if (!foundEnd) yCoords[yCount++] = endY;
    }
    
    // Sort coordinates
    for (int i = 0; i < yCount - 1; i++) {
        for (int j = i + 1; j < yCount; j++) {
            if (yCoords[i] > yCoords[j]) {
                int temp = yCoords[i];
                yCoords[i] = yCoords[j];
                yCoords[j] = temp;
            }
        }
    }
    
    // Try all pairs of cuts
    for (int i = 0; i < yCount; i++) {
        for (int j = i + 1; j < yCount; j++) {
            int cut1 = yCoords[i], cut2 = yCoords[j];
            bool section1 = false, section2 = false, section3 = false;
            
            for (int k = 0; k < rectCount; k++) {
                int startY = rectangles[k][1], endY = rectangles[k][3];
                if (endY <= cut1) {
                    section1 = true;
                } else if (startY >= cut2) {
                    section3 = true;
                } else if (startY >= cut1 && endY <= cut2) {
                    section2 = true;
                }
            }
            
            if (section1 && section2 && section3) {
                return true;
            }
        }
    }
    return false;
}

bool canCutVertically(int rectangles[][4], int rectCount) {
    int xCoords[1000], xCount = 0;
    
    // Collect unique x coordinates
    for (int i = 0; i < rectCount; i++) {
        int startX = rectangles[i][0], endX = rectangles[i][2];
        
        bool foundStart = false, foundEnd = false;
        for (int j = 0; j < xCount; j++) {
            if (xCoords[j] == startX) foundStart = true;
            if (xCoords[j] == endX) foundEnd = true;
        }
        if (!foundStart) xCoords[xCount++] = startX;
        if (!foundEnd) xCoords[xCount++] = endX;
    }
    
    // Sort coordinates
    for (int i = 0; i < xCount - 1; i++) {
        for (int j = i + 1; j < xCount; j++) {
            if (xCoords[i] > xCoords[j]) {
                int temp = xCoords[i];
                xCoords[i] = xCoords[j];
                xCoords[j] = temp;
            }
        }
    }
    
    // Try all pairs of cuts
    for (int i = 0; i < xCount; i++) {
        for (int j = i + 1; j < xCount; j++) {
            int cut1 = xCoords[i], cut2 = xCoords[j];
            bool section1 = false, section2 = false, section3 = false;
            
            for (int k = 0; k < rectCount; k++) {
                int startX = rectangles[k][0], endX = rectangles[k][2];
                if (endX <= cut1) {
                    section1 = true;
                } else if (startX >= cut2) {
                    section3 = true;
                } else if (startX >= cut1 && endX <= cut2) {
                    section2 = true;
                }
            }
            
            if (section1 && section2 && section3) {
                return true;
            }
        }
    }
    return false;
}

bool solution(int n, int rectangles[][4], int rectCount) {
    return canCutHorizontally(rectangles, rectCount) || canCutVertically(rectangles, rectCount);
}

int main() {
    int n;
    scanf("%d", &n);
    
    char line[10000];
    scanf(" %[^\n]", line);
    
    // Parse rectangles manually
    int rectangles[100][4];
    int rectCount = 0;
    
    char* ptr = line + 1; // Skip first '['
    while (*ptr && rectCount < 100) {
        if (*ptr == '[') {
            ptr++;
            for (int i = 0; i < 4; i++) {
                rectangles[rectCount][i] = strtol(ptr, &ptr, 10);
                if (*ptr == ',') ptr++;
            }
            if (*ptr == ']') ptr++;
            if (*ptr == ',') ptr++;
            rectCount++;
        } else {
            ptr++;
        }
    }
    
    bool result = solution(n, rectangles, rectCount);
    printf(result ? "true\n" : "false\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n³)

O(n²) pairs of cuts × O(n) rectangles to check per pair

⚠ Quadratic Growth

Space Complexity

O(n)

Storage for cut positions extracted from rectangles

⚡ Linearithmic Space

18.5K Views

Medium Frequency

~25 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler