We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Check if Grid can be Cut into Sections

Difficulty: Medium

Problem Description

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 [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.

Key Insights

  • We need to find two distinct horizontal or vertical cut positions such that the resulting sections contain at least one rectangle each.
  • The rectangles can be represented by their y-coordinates for horizontal cuts and x-coordinates for vertical cuts.
  • A valid configuration requires careful selection of cut positions to ensure that each section is filled with rectangles.

Space and Time Complexity

Time Complexity: O(m log m), where m is the number of rectangles (for sorting the coordinates).

Space Complexity: O(m), for storing the unique cut positions.

Solution

To solve the problem, we can follow these steps:

  1. Extract Unique Cut Positions: Gather and sort the unique y-coordinates from the rectangles if looking for horizontal cuts or x-coordinates if looking for vertical cuts.
  2. Count Rectangles in Sections: Iterate through the sorted unique coordinates to count how many rectangles fall into each potential section created by the cuts.
  3. Check Validity: Determine if there exist two cut positions such that each of the three sections (formed by the cuts) contains at least one rectangle.

This approach effectively utilizes sorting and linear scanning to determine valid cut positions.

Code Solutions

def canCutIntoSections(n, rectangles):
    y_coords = set()
    
    for rect in rectangles:
        y_coords.add(rect[1])
        y_coords.add(rect[3])
    
    sorted_y = sorted(y_coords)
    
    for i in range(len(sorted_y) - 1):
        for j in range(i + 1, len(sorted_y)):
            section1 = section2 = section3 = 0
            
            for rect in rectangles:
                if rect[1] < sorted_y[i] < rect[3]:
                    section1 += 1
                elif rect[1] < sorted_y[j] < rect[3]:
                    section2 += 1
                elif sorted_y[i] < rect[1] and rect[3] < sorted_y[j]:
                    section3 += 1
            
            if section1 > 0 and section2 > 0 and section3 > 0:
                return True
                
    return False
← Back to All Questions