LeetCode 3454 | Separate Squares II | Java | Hard | Line Sweep & Segment Tree | CodeByTushu
Description: 🚀 Welcome Back to CodeByTushu!
In today’s video, we solve LeetCode 3454 — Separate Squares II using Line Sweep and Segment Tree in Java.
In this problem, we are given a set of axis-aligned squares and need to find the minimum horizontal line y that splits the total area of the union of squares into two equal halves. Unlike Separate Squares I, overlapping areas must be counted only once. To handle this, we break the 2D plane into horizontal strips using a sweep line along the y-axis and dynamically maintain the total length of the union of active horizontal x-intervals using a Segment Tree with coordinate compression.
Each square produces two events on the y-axis: entering at the bottom edge (+1) and exiting at the top edge (-1). Between consecutive y-coordinates, the active horizontal width remains strictly constant, allowing us to compute exact strip areas. Once the total union area is accumulated, we perform a linear scan over the horizontal strips to find where half the area lies and compute the exact minimal y-coordinate using direct closed-form linear interpolation in O(N log N) time and O(N) auxiliary space.
🔥 Problem Highlights
✅ 2D Line Sweep algorithm over sorted y-coordinates
✅ Dynamic interval union length maintenance using a Segment Tree
✅ Coordinate compression over large x-coordinates (up to 2 * 10^9)
✅ Elimination of lazy propagation pushdown due to symmetric enter/exit intervals
✅ Exact minimum splitting y found via linear interpolation without binary search error
✅ Optimal O(N log N) time and O(N) space complexity
⏱️ TIMESTAMPS
00:00 Intro
01:02 Problem Understanding
02:20 Observation & Invariant Slices
03:37 Approach (Sweep-Line & Segment Tree)
04:59 Code Explanation
06:22 Code Run & Dry Run
08:13 Time Complexity Analysis
09:01 Space Complexity Analysis
09:38 Outro & Summary
📂 Problem Folder & Detailed Documentation:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/tree/main/solutions/January/14-January/3454-Separate-Squares-II
☕ Java Solution:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/blob/main/solutions/January/14-January/3454-Separate-Squares-II/Solution.java
🐍 Python Solution:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/blob/main/solutions/January/14-January/3454-Separate-Squares-II/solution.py
⚡ C++ Solution:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/blob/main/solutions/January/14-January/3454-Separate-Squares-II/solution.cpp
🌐 JavaScript Solution:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/blob/main/solutions/January/14-January/3454-Separate-Squares-II/solution.js
🔗 LeetCode Source Code
📌 Admin type the link
🌐 All LeetCode Solutions
📌 https://codebytushu.com/Leetcode/
📱 Join CodeByTushu on WhatsApp
Get coding updates, LeetCode solutions, daily questions and more.
https://whatsapp.com/channel/0029Vb8k5mCDeON2Xwlkxe40
❤️ Donate
📌 https://codebytushu.com/Leetcode/donate.php
🔥 Perfect For
LeetCode Hard Problems
Java DSA Preparation
Line Sweep Algorithm
Segment Tree & Coordinate Compression
Union of Rectangles (Klee's Measure Problem)
Time Complexity Optimization
Coding Interview Preparation
Problem Solving
🌐 Follow CodeByTushu
▶️ YouTube: https://www.youtube.com/@codebytushu
📸 Instagram: https://instagram.com/codebytushu/
💼 LinkedIn: https://www.linkedin.com/company/codebytushu/
🌍 Website: https://codebytushu.com
🐙 GitHub: https://github.com/CodeByTushu
❤️ Don’t Forget To
👍 Like | 💬 Comment | 🔔 Subscribe
💬 Question of the Day
Why is a Segment Tree used with coordinate compression in the horizontal sweep-line algorithm for rectangle union?
1️⃣ To sort the 2D points along the diagonal in O(1) time
2️⃣ To efficiently maintain and query the total length of the union of active horizontal intervals in O(log N) time per event
3️⃣ To eliminate all overlapping rectangles before running the algorithm
4️⃣ To calculate the convex hull of the squares
#LeetCode3454 #LeetCode #SeparateSquaresII #Java #JavaDSA #LineSweep #SegmentTree #DSA #CodingInterview #ProblemSolving #LeetCodeHard #DailyLeetCode #JavaProgramming #CodeByTushu
👇 Comment the answer below! 🔥 Close description
In today’s video, we solve LeetCode 3454 — Separate Squares II using Line Sweep and Segment Tree in Java.
In this problem, we are given a set of axis-aligned squares and need to find the minimum horizontal line y that splits the total area of the union of squares into two equal halves. Unlike Separate Squares I, overlapping areas must be counted only once. To handle this, we break the 2D plane into horizontal strips using a sweep line along the y-axis and dynamically maintain the total length of the union of active horizontal x-intervals using a Segment Tree with coordinate compression.
Each square produces two events on the y-axis: entering at the bottom edge (+1) and exiting at the top edge (-1). Between consecutive y-coordinates, the active horizontal width remains strictly constant, allowing us to compute exact strip areas. Once the total union area is accumulated, we perform a linear scan over the horizontal strips to find where half the area lies and compute the exact minimal y-coordinate using direct closed-form linear interpolation in O(N log N) time and O(N) auxiliary space.
🔥 Problem Highlights
✅ 2D Line Sweep algorithm over sorted y-coordinates
✅ Dynamic interval union length maintenance using a Segment Tree
✅ Coordinate compression over large x-coordinates (up to 2 * 10^9)
✅ Elimination of lazy propagation pushdown due to symmetric enter/exit intervals
✅ Exact minimum splitting y found via linear interpolation without binary search error
✅ Optimal O(N log N) time and O(N) space complexity
⏱️ TIMESTAMPS
00:00 Intro
01:02 Problem Understanding
02:20 Observation & Invariant Slices
03:37 Approach (Sweep-Line & Segment Tree)
04:59 Code Explanation
06:22 Code Run & Dry Run
08:13 Time Complexity Analysis
09:01 Space Complexity Analysis
09:38 Outro & Summary
📂 Problem Folder & Detailed Documentation:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/tree/main/solutions/January/14-January/3454-Separate-Squares-II
☕ Java Solution:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/blob/main/solutions/January/14-January/3454-Separate-Squares-II/Solution.java
🐍 Python Solution:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/blob/main/solutions/January/14-January/3454-Separate-Squares-II/solution.py
⚡ C++ Solution:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/blob/main/solutions/January/14-January/3454-Separate-Squares-II/solution.cpp
🌐 JavaScript Solution:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/blob/main/solutions/January/14-January/3454-Separate-Squares-II/solution.js
🔗 LeetCode Source Code
📌 Admin type the link
🌐 All LeetCode Solutions
📌 https://codebytushu.com/Leetcode/
📱 Join CodeByTushu on WhatsApp
Get coding updates, LeetCode solutions, daily questions and more.
https://whatsapp.com/channel/0029Vb8k5mCDeON2Xwlkxe40
❤️ Donate
📌 https://codebytushu.com/Leetcode/donate.php
🔥 Perfect For
LeetCode Hard Problems
Java DSA Preparation
Line Sweep Algorithm
Segment Tree & Coordinate Compression
Union of Rectangles (Klee's Measure Problem)
Time Complexity Optimization
Coding Interview Preparation
Problem Solving
🌐 Follow CodeByTushu
▶️ YouTube: https://www.youtube.com/@codebytushu
📸 Instagram: https://instagram.com/codebytushu/
💼 LinkedIn: https://www.linkedin.com/company/codebytushu/
🌍 Website: https://codebytushu.com
🐙 GitHub: https://github.com/CodeByTushu
❤️ Don’t Forget To
👍 Like | 💬 Comment | 🔔 Subscribe
💬 Question of the Day
Why is a Segment Tree used with coordinate compression in the horizontal sweep-line algorithm for rectangle union?
1️⃣ To sort the 2D points along the diagonal in O(1) time
2️⃣ To efficiently maintain and query the total length of the union of active horizontal intervals in O(log N) time per event
3️⃣ To eliminate all overlapping rectangles before running the algorithm
4️⃣ To calculate the convex hull of the squares
#LeetCode3454 #LeetCode #SeparateSquaresII #Java #JavaDSA #LineSweep #SegmentTree #DSA #CodingInterview #ProblemSolving #LeetCodeHard #DailyLeetCode #JavaProgramming #CodeByTushu
👇 Comment the answer below! 🔥 Close description