Separate Squares II | LeetCode 3454 | Sweep Line + Segment Tree | Geometry Hard

Problem: LeetCode 3454 - Separate Squares II

Code:
https://leetcode.com/problems/separat...

Upsolve Leetcode Contest:
   • Leetcode Contests  

Greedy & Heaps:
   • Greedy & Heaps  

Two pointers:
   • Two pointers  

Sliding Window:
   • Sliding Window  

Maths & Geometry:
   • Maths & Geometry  

Stack:
   • Stack  

Set & Map:
   • Set & Map  

Bit manipulation:
   • Bit Manipulation  

Backtracking:
   • Backtracking  

Linked List:
   • Linked List  

Binary Search:
   • Binary Search  

Graph:
   • Graph  

Dynamic Progamming:
   • Dynamic Programming  

You are given a 2D integer array squares where squares[i] = [xi, yi, li] represents a square with bottom-left corner at (xi, yi) and side length li.
Each square is parallel to the x-axis.

Find the minimum y-coordinate 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.

Notes:
Squares may overlap.
Overlapping area should be counted only once.
Answers within 1e-5 of the actual answer are accepted.

------------------------------------------------
Approach (Sweep Line + Segment Tree):

We use a vertical sweep line moving along the y-axis.

1. For each square, generate two events:
At y = yi → add interval [xi, xi + li]
At y = yi + li → remove interval [xi, xi + li]

2. Sort all events by y.

3. Use a segment tree on x-coordinates to maintain active x-interval coverage.
The segment tree tracks the total covered x-length at each sweep position.

4. Between consecutive y-events:
Let dy = y[i+1] - y[i]
Current covered x-length = L
Area contributed = L * dy

5. Accumulate total area while sweeping.

6. Binary search the y-value such that:
area_below(y) = total_area / 2

The segment tree allows us to correctly handle overlapping x-intervals and compute union length efficiently.

------------------------------------------------
Time Complexity:
Event creation: O(n)
Sorting events: O(n log n)
Each event update: O(log n)
Total: O(n log n)

Space Complexity:
Segment tree + events: O(n)

------------------------------------------------
Key Concepts:
Sweep Line, Segment Tree, Geometry, Interval Union, Binary Search on Answer

---------------------------------------------
#leetcode #leetcode3454 #separatesquares #geometry #sweepline #segmenttree #intervalunion #binarysearch #hardproblem #datastructures #advancedalgo #codinginterview #competitiveprogramming #javacode #dsa #algorithms #interviewprep #placements #faang #tech #softwareengineering #problemSolving #systemdesign #codinglife #engineer #coding