Description
Solutions
Closest Random Points (Also for Core/Database Engineering)
🤘 INTERN

In many real-world applications, the problem of finding a pair of closest points arises. In the real world, data is usually distributed randomly. Given n points on a plane, randomly generated with uniform distribution, find the squared shortest distance between pairs of these points.

Function Description

Complete the function closestSquaredDistance in the editor below.

closestSquaredDistance has the following parameter(s):

  • int x[n]: each x[i] denotes the x coordinate of the ith point
  • int y[n]: each y[i] denotes the y coordinate of the ith point

    • Returns

    long: a long integer that denotes the squared shortest distance between the pairs of points

    Example 1: 

    Input:  x = [0, 1, 2], y = [0, 1, 4]
    Output: 2 
    Explanation:
    
      
There are 3 points with x coordinates x = [0, 1, 2] and y coordinates y = [0, 1, 4]. The points have the xy coordinates (0, 0), (1, 1), and (2, 4). The closest points are (0, 0) and (1, 1), and their squared shortest distance is (1-0)^2 + (1-0)^2 = 2.
    Constraints:
      • 2 ≤ n
      • either n ≤ 1000 or n = 105
      • values of x[i] and y[i] are randomly generated with uniform distribution from the range [0, 109-1]
    Thumbnail 0
    Testcase
    Result
    Case 1

    input:

    output: