Linearithmic solution to finding closest pairs in an array of N elements

I am reading Algorithms 4ed by Sedgewick and Wayne. I came across this algorithm design question that asks the following:

Write a program that given an array of N integers, finds a closest pair: two values whose difference is no greater than the difference of any other pair (in absolute value). The running time of the program should be linearithmic in the worst case.

I wrote an implementation of this algorithm in javascript and ran a few tests. So far, it looks like the algorithm is correct and also linearithmic. But, I am not very good at proving correctness of algorithms or, in analyzing their time complexity (ammortized). If anyone can help me answer the following it would be great:

  1. Is the algorithm (added later) correct?
  2. Is the amortized time complexity linearithmic (i.e., N*lgN)?

The algorithm is given below:

function binarySearch(key, start, arr) {     let a = arr[start-1]; // start >= 1     let b = arr[start];     let lo = start+1;     let hi = arr.length-1;     let getMid = () => Math.floor((lo+hi)/2);     let getDiff = (a, b) => Math.abs(a-b);       let mid;     let diff;     let ldiff = getDiff(a, b);     let hidx = start;     while(lo < hi) {         mid = getMid();         diff = getDiff(a, arr[mid]);         if(diff < ldiff) {             ldiff = diff;             hidx = mid;             hi = mid-1;         }         else {             lo = mid+1;         }     }     return { highIndex: hidx, leastDiff: ldiff }; }  function closestPair(arr) {     // returns the nearest, closest pair     let ldiff = null;      let hidx;     let lidx;     for(let i=0; i<arr.length-1; ++i) {         let { highIndex, leastDiff } = binarySearch(ldiff, i+1, arr);         console.log(`hi=$  {highIndex} low=$  {i} ld=$  {leastDiff}`);         if(ldiff === null || leastDiff < ldiff) {             ldiff = leastDiff;             hidx = highIndex;             lidx = i;         }      }     if(ldiff !== null && lidx !== null && hidx !== null) {         return { leastDiff: ldiff, lowIndex: lidx, highIndex: hidx };     }     else null; } 

To test the algorithm, I had the following tests setup:

if(!module.parent) {     let arrs = [         [1, 7, 13, 5, 19, 27, 20, 39, 40], // 2; 19-20/39-40          [3, 2, 10, 6, 9, 5],         [-2, 9, 5, 25, 13, -10, -25]     ];     for(let arr of arrs) {         let s = arr.sort(ascComparator);         console.log(`sorted arr: $  {s.toString()}`);         let cp = closestPair(s);         console.log(cp);     } }   

The output on the console for running the tests were as follows:

sorted arr: 1,5,7,13,19,20,27,39,40 hi=1 low=0 ld=4 hi=2 low=1 ld=2 hi=3 low=2 ld=6 hi=4 low=3 ld=6 hi=5 low=4 ld=1 hi=6 low=5 ld=7 hi=7 low=6 ld=12 hi=8 low=7 ld=1 { leastDiff: 1, lowIndex: 4, highIndex: 5 } sorted arr: 2,3,5,6,9,10 hi=1 low=0 ld=1 hi=2 low=1 ld=2 hi=3 low=2 ld=1 hi=4 low=3 ld=3 hi=5 low=4 ld=1 { leastDiff: 1, lowIndex: 0, highIndex: 1 } sorted arr: -25,-10,-2,5,9,13,25 hi=1 low=0 ld=15 hi=2 low=1 ld=8 hi=3 low=2 ld=7 hi=4 low=3 ld=4 hi=5 low=4 ld=4 hi=6 low=5 ld=12 { leastDiff: 4, lowIndex: 3, highIndex: 4 } 

K Closest Points to Origin C# solution deemed too slow by Leetcode.com

LeetCode challenge

I know I could simply use the built in .Sort or .Order by to solve this question in 1 line. However, for interviews I would need to show the whole workings of my solution.

I am using a min-heap to calculate and store the distances from the origin. Then I simply return the K number of distances.

My code fails due to the “Time limit exceeded” error, indicating my code is too slow. However, it does return the correct answer.

Is there a more efficient way of using a min-heap? Or should my code be using a completely different algorithm and data structure?

public class Solution {     public int[][] KClosest(int[][] points, int K)     {         var lists = new int[K][];          Heap head = new Heap();          for (int i = 0; i < points.Length; i++)         {             int a = points[i][0];             int b = points[i][1];             var testMin = a * a + b * b;             var newNode = new Node             {                 val = testMin,                 index = points[i]             };             head.Add(newNode);         }          for (int i = 0; i < K; i++)         {             lists[i] = head.Pop().index;         }          return lists;     } }  class Heap {     public Node head;     public Node tail;      public void Add(Node newNode)     {         if (head == null)         {             head = newNode;             tail = newNode;         }         else         {             newNode.parent = tail;             tail.next = newNode;             tail = tail.next;         }         HeapifyUp();     }      void HeapifyUp()     {         Node curr = tail;         while (curr.parent != null)         {             if (curr.val < curr.parent.val)             {                 var tVal = curr.val;                 var tIndex = curr.index;                  curr.val = curr.parent.val;                 curr.index = curr.parent.index;                  curr.parent.val = tVal;                 curr.parent.index = tIndex;             }             curr = curr.parent;         }     }      public Node Pop()     {         var tempHead = new Node         {             index = head.index,             val = head.val         };          // Set head value to tail value         head.index = tail.index;         head.val = tail.val;          // Deference tail         if (tail.parent != null)         {             tail.parent.next = null;             tail = tail.parent;         }         else         {             tail = null;             head = null;         }          HeapifyDown();          return tempHead;     }      void HeapifyDown()     {         Node curr = head;         while (curr != null && curr.next != null)         {             if (curr.val > curr.next.val)             {                 var tVal = curr.val;                 var tIndex = curr.index;                  curr.val = curr.next.val;                 curr.index = curr.next.index;                  curr.next.val = tVal;                 curr.next.index = tIndex;             }             curr = curr.next;         }     } }  class Node {     public int[] index;     public int val;     public Node next;     public Node parent; } 

Computing the closest point inside an intersection of half-spaces

Is there an efficient way to compute, given a point, the closest point to it that’s on the inside of an intersection of halfspaces?

For example, given the halfspaces a & b, the closest point to p that’s within the halfspaces is x

.p        ^        |        |        | x    <---.--------------> b        |       +        |        | +        |        v a 

I’m particularly interested in an algorithm for halfspaces in 3D (planes)

My current line of thinking leads me to have to compute intersections of each half space, and then find the shortest point by picking from the shortest distance to each halfspace and each intersection (line, point) that’s within all the halfspaces. Is there a better way?

Closest points of curves on convex surfaces

Let $ \Sigma$ be a convex surface in $ \mathbb{R}^3$ and $ \Gamma \subset \Sigma$ be a closed simple space curve with parameterization $ \gamma : \mathbb{S}^1 \rightarrow \mathbb{R}^3$ . Assume that a functional $ \phi: \mathbb{S}^1 \times \mathbb{S}^1 \rightarrow \mathbb{R}^+$ defined as $ \phi(u_1, u_2) := \Vert \gamma(u_2) – \gamma(u_1) \Vert^2$ has a local minimum at $ (u_1, u_2)$ . I would like to show that tangent vectors $ T(u_1)$ and $ T(u_2)$ must then be collinear.

It is easy to prove that the statement holds true when $ \Sigma$ is a plane or a sphere and that its higher dimensional analogy for curves lying on hyperplanes or hyperspheres in spaces of dimension strictly larger that 3 is false.

What is the closest airport to the center of the city it serves?

Inspired by this, but the complete opposite: What is the most remote airport from the center of the city it supposedly serves?

Personally, I can’t think of anything closer than Adelaide Airport (ADL), only 6.0km from Tarntanyangga to the Terminal Dropoff point (as close as you can get to the terminal with a car). https://goo.gl/maps/JLbaCWcUp4kFTof38

Hong Kong’s old Kai Tak would have been close (depending on where you count the ‘centre’ of Hong Kong to be) but that’s long gone.

Are there any others that even come close?

(only rule I’ll stipulate is that it has to be a decent-sized city 50k+ population, rural towns with 5 houses and a dusty airstrip in their backyards don’t count)

Find all k points which are closest to origin


We have a list of points on the plane. Find the K closest points to the origin (0, 0).

(Here, the distance between two points on a plane is the Euclidean distance.)

You may return the answer in any order. The answer is guaranteed to be unique (except for the order that it is in.)

Example 1:

Input: points = [[1,3],[-2,2]], K = 1 Output: [[-2,2]] Explanation:  The distance between (1, 3) and the origin is sqrt(10). The distance between (-2, 2) and the origin is sqrt(8). Since sqrt(8) < sqrt(10), (-2, 2) is closer to the origin. We only want the closest K = 1 points from the origin, so the answer is just [[-2,2]]. 

Example 2:

Input: points = [[3,3],[5,-1],[-2,4]], K = 2 

Output: [[3,3],[-2,4]] (The answer [[-2,4],[3,3]] would also be accepted.)

Note:

1 <= K <= points.length <= 10000 -10000 < points[i][0] < 10000 -10000 < points[i][1] < 10000

Also note that there can be a situation where distance of 2 nodes are equal and hence can print any of the node.

========================================

Here is my approach.

  1. Took tree map (So that I get all sorted distance)
  2. Start filling tree map for all points
  3. Finally took first k element.

    public class KClosestPointsToOrigin {  public int[][] kClosest(int[][] points, int K) {      int rows = points.length;       SortedMap<Double, List<CoordinatePoint>> distanceToPoint = new TreeMap<>();      for(int i =0; i<rows; i++) {         double distance = getDistance(points[i]);         if(Objects.nonNull(distanceToPoint.get(distance))) {             List<CoordinatePoint> coordinatePointList = distanceToPoint.get(distance);             coordinatePointList.add(new CoordinatePoint(points[i][0], points[i][1]));         } else {             List<CoordinatePoint> coordinatePoints = new ArrayList<>();             coordinatePoints.add(new CoordinatePoint(points[i][0], points[i][1]));             distanceToPoint.put(distance, coordinatePoints);// x and y coordinates.         }     }      int[][] arrayToReturn = new int[K][2];     int counter = 0;     for (Double key : distanceToPoint.keySet()) {         List<CoordinatePoint> coordinatePoints = distanceToPoint.get(key);         Iterator iterator1 = coordinatePoints.iterator();         while (iterator1.hasNext() && counter < K) {             CoordinatePoint coordinatePoint = (CoordinatePoint) iterator1.next();             arrayToReturn[counter][0] = coordinatePoint.x;             arrayToReturn[counter][1] = coordinatePoint.y;             counter++;         }     }      return arrayToReturn; }  private double getDistance(int[] point) {     int x = point[0];     int y = point[1];      int x2 = Math.abs(x) * Math.abs(x);     int y2 = Math.abs(y) * Math.abs(y);      return Math.sqrt(x2+y2); } 

    }

    class CoordinatePoint { int x; int y;

    public CoordinatePoint(int x, int y) {     this.x = x;     this.y = y; } 

    }

However, this solution is not efficient as runtime and memory usage is high. Can you please help me to optimize the solution.

find the bitwise and of a subarray closest to given number

It was a question i had been asked on an online assessment for a company please help me in this question-

Given an array,A of size N and an integer P , find the subarray B=A[i…j] such that i<=j , compute the bitwise value of subarray elements say K= B[i]&B[i+1]&..&B[j]. Output the minimum value of |K-P| among all values of K. size of array 1<=A.size<=100000 A[i] 0 to 10^8

i could only think of brute force.

Closest k points – performance on large lists

Very similar to this

Problem formulation: Given a list $ L$ of n points with GPS coordinates and a second list $ Q$ of $ m$ points, find the $ k$ (let’s say 3) closest points on $ L$ for each element on $ Q$ .

Aditional constrains: Assuming that both $ L$ and $ Q$ are very large, and performance is an issue. We can also assume that $ Q$ is much larger thant $ L$ . Preprocessing can be performed, but has to be robust to updates on lists $ L$ and $ Q$ (ergo, it can’t be be very performance heavy).

Problem extensions: If we can’t have preprocessing, because the updates on $ L$ and $ Q$ are very common, what would be the solution?

If you can also point me out to implemented solutions on R or Python it would be great!