LeetCode 3454 | Separate Squares II (14-01-2026) | Sweep Line + Geometry

Описание: 📌 LeetCode 3454 | Separate Squares II | Sweep Line + Geometry

In this video, we solve LeetCode Problem 3454, a challenging computational geometry problem that builds upon the idea of separating overlapping squares using area calculations.

The task is to determine a horizontal line (Y-coordinate) such that the total area of squares below the line is exactly equal to the area above it. The squares may overlap, which means we cannot simply sum individual areas — we must carefully compute the union area formed by overlapping regions.

To solve this efficiently, we use a Sweep Line Algorithm along the Y-axis. As we sweep vertically, we maintain active X-intervals corresponding to squares currently intersecting the sweep line. For each horizontal strip between consecutive Y-events, we calculate the union width of active intervals and multiply it by the strip height to accumulate area.

After computing the total union area, we perform a second pass to locate the exact Y-coordinate where the accumulated area reaches half of the total. This step involves precise floating-point calculations to ensure accuracy.

This builds on concepts from LeetCode 3453 — Separate Squares I, where you learn the core idea of splitting area in half using geometry and binary search. If you haven’t seen that yet, this video is a great warm-up to understand how area accumulation works in these splitting problems:

📺 Watch here:    • LeetCode Problem 3453 | Separate-squares-I...  

🔗 Problem Link :https://leetcode.com/problems/separat...


💡 Key Concepts Used:

Sweep Line Technique

Interval Merging (Union of X-ranges)

Geometry & Area Computation

Precision Handling with Doubles

⏱️ Complexity:

Time: O(N log N)

Space: O(N)

This problem is an excellent example of combining algorithms + geometry, and is frequently asked to test advanced problem-solving skills in coding interviews.