LeetCode 3453: Separate Squares I Solution

Master LeetCode problem 3453 (Separate Squares I), a medium 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.

3453. Separate Squares I

Medium

Array Binary Search

Problem Explanation

Explanation:

To solve this problem, we need to find the minimum y-coordinate value of a horizontal line such that the total area of the squares above the line equals the total area of the squares below the line.

We can approach this problem by calculating the area of each square and then iterating through different possible y-coordinates. For each y-coordinate, we calculate the total area above and below that line and check if they are equal. We can use binary search to find the minimum y-coordinate value that satisfies the condition.

Here are the steps to solve the problem:

Calculate the total area of all squares.
Initialize a variable eps as a very small value for precision.
Define a function check that takes the y-coordinate value as input and calculates the total area above and below that line.
Perform binary search on the possible y-coordinates to find the minimum y-coordinate that satisfies the condition.

Time Complexity:

The time complexity of this solution is O(n log n), where n is the number of squares.

Space Complexity:

The space complexity of this solution is O(1).

Solution Code

class Solution {
    public double separateSquares(int[][] squares) {
        double totalArea = 0;
        for (int[] square : squares) {
            totalArea += square[2] * square[2];
        }

        double eps = 1e-5;

        double low = 0.0, high = 1e9;
        while (low + eps < high) {
            double mid = low + (high - low) / 2;
            if (check(mid, squares) < 0) {
                low = mid;
            } else {
                high = mid;
            }
        }

        return low;
    }

    private double check(double y, int[][] squares) {
        double totalAbove = 0, totalBelow = 0;
        for (int[] square : squares) {
            double x1 = square[0];
            double y1 = square[1];
            double len = square[2];

            double x2 = x1 + len;
            double y2 = y1 + len;

            if (y1 >= y) {
                totalAbove += len * len;
            } else if (y2 <= y) {
                totalBelow += len * len;
            } else {
                totalAbove += (y - y1) / len * len * len;
                totalBelow += (y2 - y) / len * len * len;
            }
        }

        return Double.compare(totalAbove, totalBelow);
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 3453 (Separate Squares I)?

This page provides optimized solutions for LeetCode problem 3453 (Separate Squares I) 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 3453 (Separate Squares I)?

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

Can I run code for LeetCode 3453 on DevExCode?

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

Back to LeetCode Solutions