LeetCode Entry
3394. Check if Grid can be Cut into Sections
non-intersecting ranges on x or y axis sweep
3394. Check if Grid can be Cut into Sections medium
blog post
substack
youtube
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/938
Problem TLDR
3 non-intersecting ranges on x or y axis #medium #line_sweep
Intuition
Solve problem on x axis then on y axis. Several ways:
- sorting: sort by the start, check border, set border at max of the ends
- TreeMap: save starting as +1 and end points as -1, do line sweep and keep counter, 0 is a cut place
- heap: same as previous, but put pairs of coordinate and diff
Approach
- try to reuse the logic
- Rust uses ipnsort https://github.com/Voultapher/sort-research-rs/blob/main/writeup/ipnsort_introduction/text.md
- Kotlin uses Java (21) dual-pivot quicksort https://github.com/Voultapher/sort-research-rs/blob/main/writeup/ipnsort_introduction/text.md
Complexity
-
Time complexity: \(O(nlog(n))\)
-
Space complexity: \(O(log(n))\) or O(1) if we implement O(1) sorting algorithm ourselves
Code
fun checkValidCuts(n: Int, rec: Array<IntArray>) = (0..1).any { j ->
var b = -1; rec.sortBy { it[j] }
rec.count { r -> r[j] >= b.also { b = max(b, r[j + 2]) }} > 2
}
pub fn check_valid_cuts(n: i32, mut rec: Vec<Vec<i32>>) -> bool {
(0..2).any(|j| {
let mut b = -1; rec.sort_unstable_by_key(|r| r[j]);
rec.iter().filter(|r| {
let x = r[j] >= b; b = b.max(r[j + 2]); x }).count() > 2 })
}
bool checkValidCuts(int n, vector<vector<int>>& rec) {
for (int j: {0, 1}) {
sort(begin(rec), end(rec), [j](auto& a, auto& b) { return a[j] < b[j]; });
int b = -1, c = 0; for (auto& r: rec) c += r[j] >= b, b = max(b, r[j + 2]);
if (c > 2) return 1;
} return 0;
}