Please read the new rule regarding the restriction on the use of AI tools. ×

olivergrant's blog

Count squares
By olivergrant, history, 8 months ago, In English

Hi, I stumbled across a simple question:

Given $$$4 \le N \le 1000$$$ points on a cartesian plane, count the number of squares where the corner of each squares lie on the points.

The first obvious method would be to put all the points in a map, and perform an $$$O(N^3)$$$ solution to find the last corner point and see if it exists.

The next method would be to find opposite corner points in $$$O(N^2)$$$ time and check if the rest of the two points exist.

Lastly, I was wondering if there's an $$$O(N\log N)$$$ solution or $$$O(N)$$$ solution?

  • Vote: I like it
  • +9
  • Vote: I do not like it

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In my opinion, the lower bond of this question is $$$O(N \sqrt{N})$$$, although the "proof" is not very solid;

I assume in one "check" we can only count 1 square, so assume we have $$$m^2$$$ points from $$$(1,1)$$$ to $$$(m,m)$$$, there will be about $$$\frac{m (m-1) (2m-1)}{6}$$$ squares. so N points can bring about $$$\frac{N \sqrt{N}}{3}$$$ squares.

but maybe there is a way to "add" multiple squares in one "check"...

→ Reply
  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    update: according to https://oeis.org/A051602 the lower bond is $$$O(N^2)$$$ because the number of squares is $$$O(N^2)$$$

    → Reply
  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    What about if we need to just count squares whose sides are perpendicular and parallel to x-axis and y-axis, then what could be optimization to bring complexity down from O(n^2)

    → Reply
    • »
      »
      »
      3 hours ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I believe this can be done in $$$O(n\sqrt{n})$$$.

      First, you group the points by their $$$x$$$ coordinates. Then, consider some $$$x$$$ coordinate and call it $$$x_0$$$. There are two cases

      1. If the number of points with the $$$x$$$ coordinate equal to $$$x_0$$$ is smaller than $$$\sqrt{n}$$$, we can iterate over every pair of points lying on this coordinate. Then it’s enough to notice that two fixed points with the same $$$x$$$ coordinates uniquely determine a constant number of squares (actually 2 squares) so we simply check if they exists and if so, increase the result.
      1. If the number of points with the $$$x$$$ coordinate equal to $$$x_0$$$ is greater than $$$\sqrt{n}$$$, we can iterate over all points in the input. Note that a fixed $$$x$$$ coordinate and a point also uniquely determine a constant number of squares (namely two squares), so we can simply check if they exist and increase the result by the number of squares found.

      Checking if a square exists given our points can be done in $$$O(1)$$$ using a hashmap. Then it’s easy to see that the total complexity and also upper bound on the answer is $$$O(n\sqrt{n})$$$.

      → Reply