Check if grid can be cut into sections

Array Sorting

68.3% acceptance

Feb 24, 2026

622

You are given an integer n representing the dimensions of an n x n grid. You are also given a 2D array of coordinates rectangles, where rectangles[i] is in the form [startx, starty, endx, endy]. 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.

Solution

Rust

Time O(n log n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn check_valid_cuts(_n: i32, rectangles: Vec<Vec<i32>>) -> bool {
    // Try to find 2 cuts in X direction or 2 cuts in Y direction
    // A valid cut at coordinate c separates rectangles entirely to left/right (or top/bottom)
    // For vertical cuts: look at x-intervals [startx, endx)
    //   Sort by startx, track merge of intervals. Count number of non-overlapping groups >= 3.
    // For horizontal cuts: same with y-intervals
    
    fn can_cut_into_3(mut intervals: Vec<(i32, i32)>) -> bool {
      intervals.sort_unstable();
      let mut groups = 0;
      let mut cur_end = i32::MIN;
      for (s, e) in intervals {
        if s >= cur_end {
          groups += 1;
          cur_end = e;
        } else {
          cur_end = cur_end.max(e);
        }
      }
      groups >= 3
    }
    
    let x_intervals: Vec<(i32,i32)> = rectangles.iter().map(|r| (r[0], r[2])).collect();
    let y_intervals: Vec<(i32,i32)> = rectangles.iter().map(|r| (r[1], r[3])).collect();
    
    can_cut_into_3(x_intervals) || can_cut_into_3(y_intervals)
  }
}