Amazon Prime




 
Tagged
  • DSA Problems
  • Divide and Conquer Approach
  •  

    Closet Pair of Points

    Problem Statement

    1Problem Description : Given n points in the plane, find smallest euclidean distance between them.
    2
    3NOTE:
    41) Points are given by their x and y coordinates.
    52) Euclidean distance between two points p1 = (x1, y1) and p2 = (x2, y2) is expressed as d(A, B) = √( (x1-x2)² + (y1-y2)² )
    6
    7Constraints: n > 2
    8
    9Input:
    10 Array of x coordinate values of size n
    11 Array of y coordinate values of size n
    12
    13Output: Smallest distance.
    14
     
    1Example 1 :
    2
    3Input :
    4 int[] x = {2, 5, 12};
    5 int[] y = {3, 1, 30};
    6
    7Output: 3.605551275463989
    8
    9Explanation :
    10 Distance between (2, 3) and (5, 1) is 3.605551275463989
    11 Distance between (2, 3) and (12, 30) is 28.792360097775937
    12 Distance between (5, 1) and (12, 30) is 29.832867780352597
    13
    14 So shortest distance is 3.605551275463989
     
    1Example 2 :
    2
    3 Input :
    4 int[] x = {2, 12, 40, 5, 12, 3};
    5 int[] y = {3, 30, 50, 1, 10, 4};
    6
    7 Output: 1.4142135623730951
    8
    9 Explanation :
    10 Distance between (2, 3) and (12, 30) is 28.792360097775937
    11 Distance between (2, 3) and (40, 50) is 60.440052945046304
    12 Distance between (2, 3) and (5, 1) is 3.605551275463989
    13 Distance between (2, 3) and (12, 10) is 12.206555615733702
    14 Distance between (2, 3) and (3, 4) is 1.4142135623730951
    15 Distance between (12, 30) and (40, 50) is 34.40930106817051
    16 Distance between (12, 30) and (5, 1) is 29.832867780352597
    17 Distance between (12, 30) and (12, 10) is 20.0
    18 Distance between (12, 30) and (3, 4) is 27.51363298439521
    19 Distance between (40, 50) and (5, 1) is 60.21627686929839
    20 Distance between (40, 50) and (12, 10) is 48.82622246293481
    21 Distance between (40, 50) and (3, 4) is 59.033888572581766
    22 Distance between (5, 1) and (12, 10) is 11.40175425099138
    23 Distance between (5, 1) and (3, 4) is 3.605551275463989
    24 Distance between (12, 10) and (3, 4) is 10.816653826391969
    25 So shortest distance is 1.4142135623730951

    Solution Approach

    Naïve Solution

    Code Implementation

    1. Java
    2. Python

    1import java.util.Arrays;
    2
    3public class ClosetPairDistanceBruteForce {
    4
    5 public static class Point {
    6 int x;
    7 int y;
    8
    9 Point(int x, int y) {
    10 this.x = x;
    11 this.y = y;
    12 }
    13
    14 @Override
    15 public String toString(){
    16 return "("+x+", "+y+")";
    17 }
    18 }
    19
    20 public Point[] closestPair(Point[] points, int n) {
    21 Point[] result = new Point[2];
    22 double min = Double.MAX_VALUE;
    23
    24 for (int i = 0; i < n; i++) {
    25 for (int j = i + 1; j < n; j++) {
    26 double dist = distance(points[i], points[j]);
    27 if(dist < min) {
    28 min = dist;
    29 result[0] = points[i];
    30 result[1] = points[j];
    31 }
    32 min = min(min, dist);
    33 }
    34 }
    35 return result;
    36 }
    37
    38 // Method to find distance between two points p1 nd p2
    39 private double distance(Point p1, Point p2){
    40 return Math.sqrt((p1.x-p2.x) * (p1.x-p2.x) + (p1.y-p2.y) * (p1.y-p2.y)) ;
    41 }
    42
    43 // Method to find min value among two values
    44 private double min(double val1, double val2) {
    45 return Math.min(val1, val2);
    46 }
    47
    48 public static void main(String[] args) {
    49 int[] x = {2, 12, 40, 5, 12, 3};
    50 int[] y = {3, 30, 50, 1, 10, 4};
    51
    52 int n = x.length;
    53
    54 Point[] points = new Point[n] ;
    55
    56 for(int i=0; i<n; i++) {
    57 points[i] = new Point(x[i], y[i]);
    58 }
    59 ClosetPairDistanceBruteForce obj = new ClosetPairDistanceBruteForce();
    60 Point[] closestPair = obj.closestPair(points, n);
    61 Point p1 = closestPair[0];
    62 Point p2 = closestPair[1];
    63 System.out.println("Closest Pair is : "+ Arrays.toString(closestPair));
    64 }
    65
    66}

    Using Divide And Conquer

    Prerequisite

    Algorithm

    1Input : Array of points represented using x and y coordinates
    2
    3Step1: Create array px which is sorted array of original array by x coordinate.
    4 Create a sorted array py which is sorted array of original array by y coordinate.
    5 Initialize low to 0 and high to n-1 (where n is length of the array)
    6
    7Step 1: Find middle point of the px using (low+high)/2
    8
    9Step 2: Divide px array into two halves, The first sub array contains from px[low] to px[mid] and second array contains from px[mid+1] to p[high]
    10
    11Step 3: Recursively compute smallest distance from both left and right sub arrays leftMin and rightMin and then compute minimum of LeftMin and right which is called min.
    12
    13Step 4: Create a strip of coordinates from py array whose distance is less than min, and compute minValue from strip of coordinates which is called minFromStrip
    14
    15Step 5: Finally the minimum is minimum of leftMin, rightMin and minFromStrip
    16
    17Output : Pair of points which are closer in the plane

    Code Implementation

    1import java.util.Arrays;
    2public class ClosetPairDistance {
    3
    4 // point class
    5 private static class Point {
    6 int x;
    7 int y;
    8
    9 Point(int x, int y) {
    10 this.x = x;
    11 this.y = y;
    12 }
    13 }
    14
    15 private static double MIN_VAL = Double.MAX_VALUE;
    16
    17 // Method to find the min distance
    18 public double closestPair(Point[] points){
    19 int n = points.length;
    20 Point[] xSorted = new Point[n];
    21 Point[] ySorted = new Point[n];
    22
    23 for(int i=0; i<n; i++){
    24 xSorted[i] = points[i];
    25 ySorted[i] = points[i];
    26 }
    27 // sort array using x coordinate
    28 Arrays.sort(xSorted, (p1, p2) -> p1.x - p2.x);
    29
    30 // sort array using y coordinate
    31 Arrays.sort(ySorted, (p1, p2) -> p1.y - p2.y);
    32
    33 return closestPair(xSorted, ySorted, 0, n-1);
    34 }
    35
    36
    37 // recursive call to find the closest pair distance
    38 private double closestPair(Point[] px, Point[] py, int low, int high) {
    39 // count points in the search space
    40 int n = high - low + 1;
    41
    42 //If there are 2 or 3 points, then use brute force
    43 if (n <= 3) {
    44 return closestPairUsingBruteForce(px);
    45 }
    46
    47 // find middle element of the search space
    48 // to divide the space into two halves
    49 int mid = low + (high - low)/2 ;
    50 Point midPoint = px[mid];
    51
    52 // find left and right min recursively
    53 double leftMin = closestPair(px, py, low, mid);
    54 double rightMin = closestPair(px, py, mid+1, high);
    55
    56 // find the min distance from left and right search space
    57 double minDistance = Math.min(leftMin, rightMin);
    58
    59 // there might be possibility that min distance might be there by one point from left and one point from right
    60 // to find such scenarios create strip of distance minDistance from both sides
    61 // find the strip of values which are closer at a distance of d
    62 int stripLeft = -1;
    63 int stripRight = -1;
    64
    65 for(int i=low; i<high; i++) {
    66 if( Math.abs(py[i].x - midPoint.x) < minDistance ) {
    67 if(stripLeft == -1) {
    68 stripLeft = i;
    69 }else {
    70 stripRight = i;
    71 }
    72 }
    73 }
    74 // now find the min distance from strip of points
    75 double minFromStrip = getMinStripeDistance(py, stripLeft, stripRight);
    76 // finally min distance id the one min of left, right and from the strip
    77 return min(minDistance, minFromStrip);
    78 }
    79
    80
    81 // brute force method to check min distance
    82 // this method is used only if we have <=3 points in the plane
    83 public double closestPairUsingBruteForce(Point[] points) {
    84 double min = MIN_VAL;
    85
    86 for (int i = 0; i < points.length; i++) {
    87 for (int j = i + 1; j < points.length; j++) {
    88 double dist = distance(points[i], points[j]);
    89 if(dist < min) {
    90 min = dist;
    91 }
    92 min = min(min, dist);
    93 }
    94 }
    95 return min;
    96 }
    97
    98 // min distance in strip of points
    99 private double getMinStripeDistance(Point[] ySorted, int low, int high) {
    100 double min = MIN_VAL ;
    101
    102 //Pick all points one by one and try the next points till the difference
    103 //between y coordinates is smaller than d.
    104 //This is a proven fact that this loop runs at most 6 times
    105 for(int i=low; i<=high; i++) {
    106 for(int j=i+1; j<=high; j++) {
    107 min = min(min, distance(ySorted[i], ySorted[j]));
    108 }
    109 }
    110 return min;
    111 }
    112
    113 // Method to find distance between two points p1 nd p2
    114 private double distance(Point p1, Point p2){
    115 return Math.sqrt((p1.x-p2.x) * (p1.x-p2.x) + (p1.y-p2.y) * (p1.y-p2.y)) ;
    116 }
    117
    118 // method to find min between two values
    119 private double min(double val1, double val2) {
    120 return Math.min(val1, val2);
    121 }
    122
    123 // driver method
    124 public static void main(String[] args) {
    125 int[] x = {2, 12, 40, 5, 12, 3};
    126 int[] y = {3, 30, 50, 1, 10, 4};
    127
    128 int n = x.length;
    129 Point[] points = new Point[n] ;
    130
    131 for(int i=0; i<n; i++) {
    132 points[i] = new Point(x[i], y[i]);
    133 }
    134
    135 ClosetPairDistance obj = new ClosetPairDistance();
    136 double distance = obj.closestPair(points);
    137
    138 System.out.println(distance);
    139 }
    140
    141}

    Complexity Analysis

    • Time Complexity : O(n log(n))
    • Space Complexity : O(n)
     

  • DSA Problems
  • Divide and Conquer Approach
  •  
    ...