Separate Squares II

Hard

#3070Time: O(K * N log N), where N is the number of squares and K is the number of iterations in the binary search. K is determined by `log(Range / precision)`, which is roughly a constant factor (e.g., 100). This is generally slower than the optimal approach.Space: O(N), where N is the number of squares. This space is required for the data structures used in the sweep-line algorithm, such as the event list and the segment tree.

Patterns

Line Sweep

Algorithms

Binary Search

Data structures

Array Segment Tree

Prompt

You are given a 2D integer array squares. Each squares[i] = [x_i, y_i, l_i] represents the coordinates of the bottom-left point and the side length of a square parallel to the x-axis.

Find the minimum y-coordinate value of a horizontal line such that the total area covered by squares above the line equals the total area covered by squares below the line.

Answers within 10^-5 of the actual answer will be accepted.

Note: Squares may overlap. Overlapping areas should be counted only once in this version.

Example 1:

Input: squares = [[0,0,1],[2,2,1]]

Output: 1.00000

Explanation:

Any horizontal line between y = 1 and y = 2 results in an equal split, with 1 square unit above and 1 square unit below. The minimum y-value is 1.

Example 2:

Input: squares = [[0,0,2],[1,1,1]]

Output: 1.00000

Explanation:

Since the blue square overlaps with the red square, it will not be counted again. Thus, the line y = 1 splits the squares into two equal parts.

Constraints:

1 <= squares.length <= 5 * 10⁴
squares[i] = [x_i, y_i, l_i]
squares[i].length == 3
0 <= x_i, y_i <= 10⁹
1 <= l_i <= 10⁹
The total area of all the squares will not exceed 10¹⁵.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach leverages the monotonic nature of the area function with respect to the dividing line's y-coordinate. We can binary search for the optimal y-coordinate h. For each guess of h, we calculate the area of the union of squares below that line. This area calculation is a classic computational geometry problem that can be solved with a sweep-line algorithm and a segment tree. While correct, this method is less efficient because it involves running the entire O(N log N) area calculation multiple times.

Algorithm

Overall Strategy: The area of the union of squares below a horizontal line y = h, let's call it A(h), is a monotonically increasing function of h. This property allows us to use binary search on the value of h to find the one that splits the total area in half.
Area Calculation: The main subproblem is to compute A(h) for a given h. This can be solved using a sweep-line algorithm.
Steps:
1. First, compute the total area of the union of all squares, TotalArea. This is done once using a standard sweep-line algorithm. The target area for the lower half is TargetArea = TotalArea / 2.
2. Define a search range for h. A safe range is from the minimum possible y-coordinate to the maximum possible top-edge y-coordinate.
3. Perform a binary search for h in this range.
4. In each iteration, for a candidate value mid_h: a. Create a new set of rectangles by clipping each original square with the line y = mid_h. A square [x, y, l] becomes a rectangle with corners (x, y) and (x+l, min(y+l, mid_h)). b. Calculate the area of the union of these clipped rectangles using a sweep-line algorithm. This involves sweeping a vertical line from left to right and using a segment tree to maintain the length of the union of vertical intervals on the sweep line. c. If the calculated area is greater than or equal to TargetArea, it means mid_h is a potential answer, so we try to find a smaller h by setting high = mid_h. Otherwise, we need a larger h, so we set low = mid_h.
5. The binary search continues until the range [low, high] is smaller than the required precision (e.g., 10^-5).

Walkthrough

The fundamental idea is to find a root for the equation AreaBelow(h) - TotalArea / 2 = 0. Since AreaBelow(h) is monotonic, binary search is a natural fit. The main challenge lies in efficiently computing AreaBelow(h).

A sweep-line algorithm is used for this. We treat the clipped rectangles' vertical edges as events. A vertical line sweeps across the plane from left to right. Between any two consecutive x-events, the set of active rectangles is constant. We use a segment tree to manage the y-intervals of these active rectangles and query the total length of their union on the sweep line. By multiplying this length by the distance between consecutive x-events and summing up these areas, we get the total area of the union.

This entire process is wrapped inside a binary search loop. The number of iterations for the binary search depends on the coordinate range and required precision, typically around 100 iterations for the given constraints. This leads to a high overall time complexity.

Complexity

Time

O(K * N log N), where N is the number of squares and K is the number of iterations in the binary search. K is determined by `log(Range / precision)`, which is roughly a constant factor (e.g., 100). This is generally slower than the optimal approach.

Space

O(N), where N is the number of squares. This space is required for the data structures used in the sweep-line algorithm, such as the event list and the segment tree.

Trade-offs

Pros

Conceptually clear, as it breaks down the problem into two well-known subproblems: binary search and calculating the area of union of rectangles.
Guaranteed to find the answer within the desired precision.

Cons

Inefficient due to the repeated execution of the O(N log N) area calculation within the binary search loop.
The implementation can be complex, as the set of y-coordinates for the segment tree in the sweep-line algorithm changes with each h, requiring repeated setup or a more complex data structure.

This is the most efficient approach, solving the problem in O(N log N) time. It avoids the repeated calculations of the binary search method by performing a single conceptual sweep across the y-axis. We treat the top and bottom edges of the squares as events. Between any two consecutive event y-coordinates, the set of squares crossing a horizontal line is constant. We can calculate the total length of the x-intervals covered by these squares using a segment tree. By integrating this length over y, we first find the total area and then, in a second pass, find the exact y-coordinate where the accumulated area reaches half of the total.

Algorithm

Core Idea: Instead of binary searching, we can find the answer directly by sweeping a horizontal line from bottom to top. The total length of the horizontal cross-section of the union of squares is a step function that only changes at the y-coordinates of the squares' top and bottom edges.
Steps:
1. Events and Coordinate Compression:
  - For each square [x, y, l], create two events: an 'enter' event at y and an 'exit' event at y+l. Both are associated with the x-interval [x, x+l].
  - Collect all unique x-coordinates (x and x+l) and compress them into a smaller integer range to be used as indices for a segment tree.
2. Segment Tree:
  - Build a segment tree over the compressed x-coordinates. Each node in the tree will maintain a count (how many rectangles cover its range) and length (the length of the covered portion of its range).
3. First Pass (Total Area):
  - Sort the y-events. Iterate through them, processing horizontal 'slabs' between consecutive event y-coordinates.
  - For each slab between y_prev and y_curr, the area is (covered_x_length) * (y_curr - y_prev). The covered_x_length is queried from the root of the segment tree.
  - Sum these slab areas to get the TotalArea.
  - After calculating a slab's area, process the event(s) at y_curr to update the segment tree for the next slab.
4. Second Pass (Find Split Line):
  - Calculate TargetArea = TotalArea / 2.
  - Reset the segment tree and an areaSoFar counter.
  - Perform another sweep through the sorted y-events.
  - For each slab, calculate its area. If areaSoFar + slabArea >= TargetArea, the split line h lies within this slab.
  - The exact value of h can be found with the formula: h = y_prev + (TargetArea - areaSoFar) / covered_x_length.
  - Return h and terminate.

Walkthrough

This method reframes the problem from finding a point to integrating a function. The function to integrate, L(y), is the total length of the union of horizontal segments obtained by intersecting the squares with the line at height y. L(y) is a step function, constant between the y-coordinates of the tops and bottoms of the squares. The algorithm calculates the area under this step function.

We use a horizontal sweep-line. The events are the y-coordinates. The state of the sweep-line is the set of active x-intervals, and we need to find the length of their union. A segment tree is perfectly suited for this. The x-coordinates are first compressed. The segment tree is built on these compressed coordinates. Each node stores a count of how many active intervals cover its range and the length of the union within its range. An update involves adding or removing an x-interval, which translates to incrementing or decrementing the count on the corresponding segment tree nodes. The total covered length is always available at the root of the tree.

Two passes are made: the first to compute the total area, and the second to find the y-value where the accumulated area equals half the total. This avoids the log(Range) factor from binary search, leading to a significantly faster solution.

1class Solution {2    class Event implements Comparable<Event> {3        long y;4        long x1, x2;5        int type; // 1 for enter, -1 for exit6 7        Event(long y, long x1, long x2, int type) {8            this.y = y;9            this.x1 = x1;10            this.x2 = x2;11            this.type = type;12        }13 14        @Override15        public int compareTo(Event other) {16            return Long.compare(this.y, other.y);17        }18    }19 20    class Node {21        int count;22        long length;23    }24 25    Node[] tree;26    long[] xCoords;27    Map<Long, Integer> xMap;28 29    public double separateSquares(int[][] squares) {30        List<Event> events = new ArrayList<>();31        Set<Long> xSet = new HashSet<>();32 33        for (int[] s : squares) {34            long x = s[0], y = s[1], l = s[2];35            events.add(new Event(y, x, x + l, 1));36            events.add(new Event(y + l, x, x + l, -1));37            xSet.add(x);38            xSet.add(x + l);39        }40 41        if (xSet.isEmpty()) return 0.0;42        Collections.sort(events);43 44        xCoords = new long[xSet.size()];45        int idx = 0;46        for (long val : xSet) xCoords[idx++] = val;47        Arrays.sort(xCoords);48 49        xMap = new HashMap<>();50        for (int i = 0; i < xCoords.length; i++) xMap.put(xCoords[i], i);51 52        tree = new Node[4 * xCoords.length];53        for (int i = 0; i < tree.length; i++) tree[i] = new Node();54 55        // Pass 1: Calculate total area56        long totalArea = 0;57        long lastY = events.get(0).y;58        for (int i = 0; i < events.size(); ) {59            long currentY = events.get(i).y;60            if (currentY > lastY) {61                totalArea += tree[1].length * (currentY - lastY);62            }63            int j = i;64            while (j < events.size() && events.get(j).y == currentY) {65                Event e = events.get(j);66                update(1, 0, xCoords.length - 2, xMap.get(e.x1), xMap.get(e.x2) - 1, e.type);67                j++;68            }69            lastY = currentY;70            i = j;71        }72 73        if (totalArea == 0) {74            long minY = Long.MAX_VALUE;75            for(int[] s : squares) minY = Math.min(minY, s[1]);76            return minY;77        }78        79        double targetArea = totalArea / 2.0;80        81        // Pass 2: Find the split line82        for (int i = 0; i < tree.length; i++) tree[i] = new Node();83        double areaSoFar = 0;84        lastY = events.get(0).y;85 86        for (int i = 0; i < events.size(); ) {87            long currentY = events.get(i).y;88            if (currentY > lastY) {89                long coveredLength = tree[1].length;90                if (coveredLength > 0) {91                    double slabArea = (double) coveredLength * (currentY - lastY);92                    if (areaSoFar + slabArea >= targetArea) {93                        double neededArea = targetArea - areaSoFar;94                        return lastY + neededArea / coveredLength;95                    }96                    areaSoFar += slabArea;97                }98            }99            int j = i;100            while (j < events.size() && events.get(j).y == currentY) {101                Event e = events.get(j);102                update(1, 0, xCoords.length - 2, xMap.get(e.x1), xMap.get(e.x2) - 1, e.type);103                j++;104            }105            lastY = currentY;106            i = j;107        }108        109        return -1.0; // Should be unreachable110    }111 112    private void update(int nodeIdx, int start, int end, int l, int r, int val) {113        if (l > r) return;114        if (l == start && r == end) {115            tree[nodeIdx].count += val;116        } else {117            int mid = start + (end - start) / 2;118            update(2 * nodeIdx, start, mid, l, Math.min(r, mid), val);119            update(2 * nodeIdx + 1, mid + 1, end, Math.max(l, mid + 1), r, val);120        }121        pushUp(nodeIdx, start, end);122    }123 124    private void pushUp(int nodeIdx, int start, int end) {125        if (tree[nodeIdx].count > 0) {126            tree[nodeIdx].length = xCoords[end + 1] - xCoords[start];127        } else {128            if (start == end) {129                tree[nodeIdx].length = 0;130            } else {131                tree[nodeIdx].length = tree[2 * nodeIdx].length + tree[2 * nodeIdx + 1].length;132            }133        }134    }135}

Complexity

Time

O(N log N), dominated by sorting the events. The sweep itself involves 2N events, and each event triggers an `O(log N)` update on the segment tree.

Space

O(N), where N is the number of squares. Space is used for storing events, the coordinate compression map, and the segment tree.

Trade-offs

Pros

Optimal time complexity, making it very efficient for large inputs.
Calculates the exact answer without requiring iterative approximation (like binary search).
The core logic (sweep-line with segment tree) is a powerful technique applicable to many other geometric problems.

Cons

Implementation is more complex than the binary search approach, requiring careful handling of the segment tree and event processing.
Requires two passes over the data, though this does not change the overall asymptotic complexity.

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem