Tagged
• DSA Problems
• Divide and Conquer Approach
•

# 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 > 28
9Input: 10  Array of x coordinate values of size n11  Array of y coordinate values of size n12
13Output: Smallest distance.14
```

```1Example 1 :2
3Input : 4    int[] x = {2, 5, 12};5    int[] y = {3, 1, 30};6
7Output: 3.6055512754639898
9Explanation :10    Distance between (2, 3) and  (5, 1) is 3.60555127546398911    Distance between (2, 3) and  (12, 30) is 28.79236009777593712    Distance between (5, 1) and  (12, 30) is 29.83286778035259713
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.41421356237309518
9  Explanation :10    Distance between (2, 3) and  (12, 30) is 28.79236009777593711    Distance between (2, 3) and  (40, 50) is 60.44005294504630412    Distance between (2, 3) and  (5, 1) is 3.60555127546398913    Distance between (2, 3) and  (12, 10) is 12.20655561573370214    Distance between (2, 3) and  (3, 4) is 1.414213562373095115    Distance between (12, 30) and  (40, 50) is 34.4093010681705116    Distance between (12, 30) and  (5, 1) is 29.83286778035259717    Distance between (12, 30) and  (12, 10) is 20.018    Distance between (12, 30) and  (3, 4) is 27.5136329843952119    Distance between (40, 50) and  (5, 1) is 60.2162768692983920    Distance between (40, 50) and  (12, 10) is 48.8262224629348121    Distance between (40, 50) and  (3, 4) is 59.03388857258176622    Distance between (5, 1) and  (12, 10) is 11.4017542509913823    Distance between (5, 1) and  (3, 4) is 3.60555127546398924    Distance between (12, 10) and  (3, 4) is 10.81665382639196925    So shortest distance is 1.4142135623730951```

# 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        @Override15        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 p239    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 values44    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

## Algorithm

```1Input : Array of points represented using x and y coordinates2
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)/28
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 minFromStrip14
15Step 5: Finally the minimum is minimum of leftMin, rightMin and minFromStrip16
17Output : Pair of points which are closer in the plane```

## Code Implementation

```1import java.util.Arrays;2public class ClosetPairDistance {3
4    // point class5    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 distance18    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 coordinate28        Arrays.sort(xSorted, (p1, p2) -> p1.x - p2.x);29
30        // sort array using y coordinate31        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 distance38    private double closestPair(Point[] px, Point[] py, int low, int high) {39        // count points in the search space40        int n = high - low + 1;41
42        //If there are 2 or 3 points, then use brute force43        if (n <= 3) {44            return closestPairUsingBruteForce(px);45        }46
47        // find middle element of the search space48        // to divide the space into two halves49        int mid = low + (high - low)/2 ;50        Point midPoint = px[mid];51
52        // find left and right min recursively53        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 space57        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 right60        // to find such scenarios create strip of distance minDistance from both sides61        // find the strip of values which are closer at a distance of d62        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 points75        double minFromStrip = getMinStripeDistance(py, stripLeft, stripRight);76        // finally min distance id the one min of left, right and from the strip77        return min(minDistance, minFromStrip);78    }79
80
81    // brute force method to check min distance82    // this method is used only if we have <=3 points in the plane83    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 points99    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 difference103        //between y coordinates is smaller than d.104        //This is a proven fact that this loop runs at most 6 times105        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 p2114    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 values119    private double min(double val1, double val2) {120        return Math.min(val1, val2);121    }122
123    // driver method124    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
•
...