saint_coder's blog

By saint_coder, history, 4 months ago, In English,

I thought of a solution but I have a doubt if my solution will work.

Please tell your solution of solving it, also a little analysis of the time complexity(if you have time)

Here's the Problem:

Given two arrays of integers A and B of size N each, where each pair (A[i], B[i]) for represents a unique point (x, y) in the 2D Cartesian plane.

Find and return the number of unordered quadruplet (i, j, k, l) such that (A[i], B[i]), (A[j], B[j]), (A[k], B[k]) and (A[l], B[l]) form a rectangle with the rectangle having all the sides parallel to either x-axis or y-axis.

Input Format The first argument given is the integer array A. The second argument given is the integer array 8.

Output Format Return the number of unordered quadruplets that form a rectangle.

Constraints

1<=N<=2000

1<=A[i],B[i]<=10^9

For Example:

Input 1: A=[1,1,2,2] B=[1,2,1,2]

Output 1: 1

Input 2: A=[1,1,2,2,3,3] B=[1,2,1,2,1,2]

Output 2: 3

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

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

Auto comment: topic has been updated by saint_coder (previous revision, new revision, compare).

»
4 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by saint_coder (previous revision, new revision, compare).

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

This problem can be solved by using the relation a+c-b = d for any parallelogram So what you can do is sort the array so we can find points parallel to the y-axis, store these points in another array. Now use the rule for the parallelogram taking into consideration that the y-axis also remains the same. I hope you get it.

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

A simple solution that, maybe, is too slow is: you use 2 loops to check any pair of points, and if the 2 points dont share the same X or the same Y then you search if among the points there are the other 2 vertices(looking for opposite vertices) (if A=(2,5) and B=(3,7) you are searching for (3,5) and (2,7). If you use a set you can search in O(logN) , the total complexity is O(N^2logN).Remember that you are counting the same rectangle 4 times.

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

    Okay great! I get it. It can be reduced to O(N^2) if we use a hashmap with customized hash function to store pair of points. Cool! Thanks for your solution. :D

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

    unordered quadruplet means counting 4 or 4! ???

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

      Let's suppose the rectangle has vertices ABCD, and the 2 loops are i=0 to n-1 and j=0 to n-1 ( if i==j the has the same X so the algorithm doesn't search other vertices). The 4 possibilites are: i=A and j=C i=B and j=D i=C and j=A i=D and j=B If you want to partially fix this problem you can simply run i form 0 to n and j from i+1 to n in this way you will count the same rectangle 2 times.