3657. Check If Grid Can Be Cut Into Sections¶

Difficulty: Medium

3657. Check if Grid can be Cut into Sections

Medium

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.

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

Solution¶

class Solution {
    private ArrayList<Pair> vertical_merged;
    private ArrayList<Pair> horizontal_merged;
    static class Pair {
        int start, end;
        public Pair(int start, int end) {
            this.start = start;
            this.end = end;
        }
        @Override
        public String toString() {
            return "(" + start + " " + end + ")";
        }
    } 
    static class custom_sort implements Comparator<int[]> {
        @Override
        public int compare(int[] first, int[] second) {
            return Integer.compare(first[0], second[0]);
        }
    }
    public boolean checkValidCuts(int n, int[][] arr) {
        int len = arr.length;
        int varr[][] = new int[len][2];
        int harr[][] = new int[len][2];
        for (int i = 0; i < len; i++) {
            int vl = arr[i][0], vr = arr[i][2];
            int hl = arr[i][1], hr = arr[i][3];
            varr[i][0] = vl; varr[i][1] = Math.max(varr[i][1], vr);
            harr[i][0] = hl; harr[i][1] = Math.max(harr[i][1], hr);
        }

        Arrays.sort(varr, new custom_sort());
        Arrays.sort(harr, new custom_sort());

        vertical_merged = new ArrayList<>();
        horizontal_merged = new ArrayList<>();
        merge(varr, vertical_merged);
        merge(harr, horizontal_merged);

        if (vertical_merged.size() >= 3 || horizontal_merged.size() >= 3) return true;
        return false;
    }
    private void merge(int arr[][], ArrayList<Pair> res) {
        int n = arr.length;
        int left = 0, right = 0;
        while (left < n) {
            int mini = arr[left][0], maxi = arr[left][1];
            while (right < n && arr[right][0] < maxi) {
                maxi = Math.max(maxi, arr[right][1]);
                right++;
            }
            res.add(new Pair(mini, maxi));
            left = right;
        }
    }
}

Complexity Analysis¶

Time Complexity: O(?)
Space Complexity: O(?)

Approach¶

Detailed explanation of the approach will be added here