3394. Check if Grid can be Cut into Sections LeetCode Solution

In this guide, you will get 3394. Check if Grid can be Cut into Sections LeetCode Solution with the best time and space complexity. The solution to Check if Grid can be Cut into Sections problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Check if Grid can be Cut into Sections solution in C++
Check if Grid can be Cut into Sections solution in Java
Check if Grid can be Cut into Sections solution in Python
Additional Resources

3394. Check if Grid can be Cut into Sections LeetCode Solution image

Problem Statement of Check if Grid can be Cut into Sections

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.

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.

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:

The grid is shown in the diagram. We can make horizontal cuts at y = 2 and y = 4. 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. Hence, output is true.

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 <= 109
3 <= rectangles.length <= 105
0 <= rectangles[i][0] < rectangles[i][2] <= n
0 <= rectangles[i][1] < rectangles[i][3] <= n
No two rectangles overlap.

Complexity Analysis

Time Complexity: O(\texttt{sort})
Space Complexity: O(\texttt{sort})

3394. Check if Grid can be Cut into Sections LeetCode Solution in C++

class Solution {
 public:
  bool checkValidCuts(int n, vector<vector<int>>& rectangles) {
    vector<pair<int, int>> xs;
    vector<pair<int, int>> ys;

    for (const vector<int> rectangles : rectangles) {
      const int startX = rectangles[0];
      const int startY = rectangles[1];
      const int endX = rectangles[2];
      const int endY = rectangles[3];
      xs.emplace_back(startX, endX);
      ys.emplace_back(startY, endY);
    }

    return max(countMerged(xs), countMerged(ys)) >= 3;
  }

 private:
  int countMerged(vector<pair<int, int>>& intervals) {
    int count = 0;
    int prevEnd = 0;

    ranges::sort(intervals);

    for (const auto& [start, eend] : intervals)
      if (start < prevEnd) {
        prevEnd = max(prevEnd, eend);
      } else {
        prevEnd = eend;
        ++count;
      }

    return count;
  }
};
/* code provided by PROGIEZ */

3394. Check if Grid can be Cut into Sections LeetCode Solution in Java

class Solution {
  public boolean checkValidCuts(int n, int[][] rectangles) {
    int[][] xs = new int[rectangles.length][2];
    int[][] ys = new int[rectangles.length][2];

    for (int i = 0; i < rectangles.length; ++i) {
      xs[i][0] = rectangles[i][0];
      xs[i][1] = rectangles[i][2];
      ys[i][0] = rectangles[i][1];
      ys[i][1] = rectangles[i][3];
    }

    return Math.max(countMerged(xs), countMerged(ys)) >= 3;
  }

  private int countMerged(int[][] intervals) {
    int count = 0;
    int prevEnd = 0;

    Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));

    for (int[] interval : intervals) {
      final int start = interval[0];
      final int end = interval[1];
      if (start < prevEnd) {
        prevEnd = Math.max(prevEnd, end);
      } else {
        prevEnd = end;
        ++count;
      }
    }

    return count;
  }
}
// code provided by PROGIEZ

3394. Check if Grid can be Cut into Sections LeetCode Solution in Python

class Solution:
  def checkValidCuts(self, n: int, rectangles: list[list[int]]) -> bool:
    xs = [(startX, endX) for startX, _, endX, _ in rectangles]
    ys = [(startY, endY) for _, startY, _, endY in rectangles]
    return max(self._countMerged(xs),
               self._countMerged(ys)) >= 3

  def _countMerged(self, intervals: list[tuple[int, int]]) -> int:
    count = 0
    prevEnd = 0
    for start, end in sorted(intervals):
      if start < prevEnd:
        prevEnd = max(prevEnd, end)
      else:
        prevEnd = end
        count += 1
    return count
 # code by PROGIEZ