LeetCode 3454: Separate Squares II Solution

Master LeetCode problem 3454 (Separate Squares II), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

3454. Separate Squares II

Hard

Array Binary Search Segment Tree Line Sweep

Problem Explanation

Explanation:

To solve this problem, we need to find the minimum y-coordinate value of a horizontal line that splits the total area covered by squares above the line equal to the total area covered by squares below the line. We can approach this problem by calculating the total area covered by the squares above and below different y-coordinate values and then finding the y-coordinate where the areas are equal using binary search.

We iterate through all the squares to calculate the total area covered by each square.
We sort the y-coordinates of the squares and calculate the total area covered by squares above and below each y-coordinate.
We use binary search to find the minimum y-coordinate value where the areas are equal.

Time Complexity: O(n log n) where n is the number of squares, due to sorting and binary search.

Space Complexity: O(n) for storing the y-coordinates.

Solution Code

class Solution {
    public double separateSquaresII(int[][] squares) {
        int n = squares.length;
        long[] yCoords = new long[2 * n];
        int idx = 0;
        
        for (int[] square : squares) {
            yCoords[idx++] = square[1];
            yCoords[idx++] = square[1] + square[2];
        }
        
        Arrays.sort(yCoords);
        
        double left = yCoords[0], right = yCoords[2 * n - 1];
        
        while (right - left > 1e-5) {
            double mid = (left + right) / 2.0;
            double above = 0, below = 0;
            
            for (int[] square : squares) {
                double y1 = Math.max(square[1], mid);
                double y2 = Math.min(square[1] + square[2], mid);
                if (y1 < y2) {
                    above += (y2 - y1) * square[2];
                }
                below += square[2];
            }
            
            if (above > below) {
                right = mid;
            } else {
                left = mid;
            }
        }
        
        return left;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 3454 (Separate Squares II)?

This page provides optimized solutions for LeetCode problem 3454 (Separate Squares II) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 3454 (Separate Squares II)?

The time complexity for LeetCode 3454 (Separate Squares II) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 3454 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 3454 in Java, C++, or Python.

Back to LeetCode Solutions