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

Problem: LeetCode 3454 - Separate Squares II Code: https://leetcode.com/problems/separate-squares-ii/solutions/7493531/geometry-segment-tree-complete-tutorial-at885 Upsolve Leetcode Contest: https://youtube.com/playlist?list=PLsLlEdtakGoxoGbAwVRSlRjuB1yv1ycnc&si=_IDShX4wq0BxIkNf Greedy & Heaps: https://youtube.com/playlist?list=PLsLlEdtakGozAWFrLtFyKfzHL69QMdpkK&si=05iZsUB_hCmYZGPN Two pointers: https://youtube.com/playlist?list=PLsLlEdtakGow7Brk6c1OM_Bh-Mz55V7nX&si=hwShAQg6AT_VlwOm Sliding Window: https://youtube.com/playlist?list=PLsLlEdtakGozlKx_L-5PQJO-ua_maQb6R&si=hNoGQVZUI7OR9poU Maths & Geometry: https://youtube.com/playlist?list=PLsLlEdtakGoyWTBlOMC_mQ8Pv1M_pY2MX&si=MHwHo53uuirf26zC Stack: https://youtube.com/playlist?list=PLsLlEdtakGowhIcIi8uvWRy7Zw-bKoD85&si=9jvT_g2NQHFUHAMg Set & Map: https://youtube.com/playlist?list=PLsLlEdtakGozffR58V-u_qpYkwkR2Nc_F&si=_h2GBLEVi-hQyvI- Bit manipulation: https://youtube.com/playlist?list=PLsLlEdtakGowS_aAEQDNtNJA9zWkyk5uf&si=f0yO3hkGsorAhiod Backtracking: https://youtube.com/playlist?list=PLsLlEdtakGox7HMCBg3_sh8TrZoKnTPep&si=CMvDSFGzMRg6io1Y Linked List: https://youtube.com/playlist?list=PLsLlEdtakGowLdcT3ocFdt5MCEuTYVOzF&si=16QNR2HY_bLvVw2n Binary Search: https://youtube.com/playlist?list=PLsLlEdtakGozNxx5rfRgEW-1DYseLnDbV&si=RZ1BUYmSAvIvi5a5 Graph: https://youtube.com/playlist?list=PLsLlEdtakGox1mdnH0PrJUhHJByUstkvx&si=JW-6qPw7zXDH-29j Dynamic Progamming: https://youtube.com/playlist?list=PLsLlEdtakGoyNROP7uWS9OLLHs9_JluVM&si=vJY6SxVXIHAbgzgk 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