Day 4 : Closest Distance Pair

Easy

0/40

Average time to solve is 20m

Contributed by

31 upvotes

Asked in companies

Problem statement

You are given an array containing 'N' points in the plane. The task is to find out the distance of the closest points.

Note :

Where distance between two points (x1, y1) and (x2, y2) is calculated as [(x1 - x2) ^ 2] + [(y1 - y2) ^ 2].

Detailed explanation ( Input/output format, Notes, Images )

Input Format :

The first line contains a single integer 'N' denoting the number of points.

The next 'N' lines contain two integers separated by a single space, where the first integer represents the x coordinate and the second integer represents the y coordinate.

Output Format :

The only line contains the minimum distance between the 'N' points.

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints :

2 <= 'N' <= 10^5
-10^5 <= 'x' <= 10^5 
-10^5 <= 'y' <= 10^5

Time Limit: 1 sec

Sample Input 1:

Sample Output 1:

Explanation of Sample Output 1:

We have 2 pairs which are probable answers (1, 2) with (2, 3) and (2, 3) with (3, 4). The distance between both of them is equal to 2.

Sample Input 2 :

Sample Output 2 :

Explanation of Sample Output 1 :

If we choose the pairs (0, 0) and (-3, -4), the distance between them is 3^2 + 4^2 = 25. This is the optimal answer for this test case.

Hint 1

Hint 2

Try to think of brute force and return the minimum distance.

Approaches (2)

Approach 1

Approach 2

Brute Force Approach

For every pair of points (x1, y1) and (x2, y2), calculate the distance by the following formula:
distance = (x1-x2)^2 + (y1-y2)^2.
And if the minimum distance till now is greater than distance then update the minimum distance.
Return the minimum distance.

Time Complexity

O(N^2), where N is the size of the array ARR.

As we are calculating the distance between every pair.

Space Complexity

O(1)

As constant extra space is used.

(100% EXP penalty)

Day 4 : Closest Distance Pair

Console