LeetCode 2013: Detect Squares Solution

Master LeetCode problem 2013 (Detect Squares), 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.

2013. Detect Squares

Medium

Array Hash Table Design Counting

Problem Explanation

Explanation

To solve this problem, we can store the points in a data structure that allows for efficient retrieval of points based on their x and y coordinates. One way to achieve this is by using a hashmap of hashmaps, where the key of the outer hashmap represents the x-coordinate, and the inner hashmap stores the y-coordinate as the key and the frequency of that point as the value.

When adding a new point, we increment the frequency of that point in the hashmap. When counting the number of ways to form axis-aligned squares with a query point, we iterate through the points in the data structure and check for valid squares based on the given conditions.

The time complexity of adding a point is O(1), and the time complexity of counting is O(n), where n is the total number of points in the data structure.

Solution Code

class DetectSquares {
    Map<Integer, Map<Integer, Integer>> points;

    public DetectSquares() {
        points = new HashMap<>();
    }

    public void add(int[] point) {
        int x = point[0];
        int y = point[1];
        points.putIfAbsent(x, new HashMap<>());
        points.get(x).put(y, points.get(x).getOrDefault(y, 0) + 1);
    }

    public int count(int[] point) {
        int x = point[0];
        int y = point[1];
        int result = 0;

        for (int px : points.keySet()) {
            if (px == x) continue;
            for (int py : points.get(px).keySet()) {
                if (Math.abs(px - x) == Math.abs(py - y) && points.containsKey(x) && points.get(px).containsKey(y) && points.containsKey(px) && points.get(px).containsKey(py)) {
                    result += points.get(px).get(py) * points.get(x).get(y) * points.get(px).get(y);
                }
            }
        }

        return result;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 2013 (Detect Squares)?

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

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

Can I run code for LeetCode 2013 on DevExCode?

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

Back to LeetCode Solutions