Find k closest numbers in an unsorted array

The problem being addressed is to find the k closest numbers to a given value in an unsorted array of integers. This task involves selecting k numbers from the array that are closest to the given value. This operation can be useful in various contexts, such as recommending similar products to users based on their preferences or finding the nearest neighbors in a dataset.

Problem Statement and Description

Given an unsorted array of integers and a value, the goal is to find the k numbers in the array that are closest to the given value. For example, consider the array [1, 6, 4, 10, 2, 5] and the value 5. If we want to find the 4 closest numbers to 5, the output could be [5, 6, 4, 2], as these are the numbers closest to 5.

Idea to Solve the Problem

To find the k closest numbers, we can iterate through the array and calculate the absolute difference between each element and the given value. We'll store the indices of the k closest elements in an array. For each element beyond the first k elements, we'll compare its difference with the differences of the k closest elements. If its difference is smaller, we'll replace the index of the farthest element among the k closest elements with the index of the current element.

Pseudocode

difference(arr, value, index):
    if value > arr[index]:
        return value - arr[index]
    else:
        return arr[index] - value

k_closest(arr, size, value, k):
    if size <= 1 or k > size:
        return
    
    result[k]
    
    for i from 0 to k-1:
        result[i] = i
        
    for i from k to size-1:
        diff = difference(arr, value, i)
        checker = -1
        
        for j from 0 to k-1:
            auxiliary = difference(arr, value, result[j])
            
            if auxiliary > diff:
                if checker == -1:
                    checker = result[j]
                else:
                    old = difference(arr, value, checker)
                    
                    if old < auxiliary:
                        checker = result[j]
                        
        if checker != -1:
            result[checker] = i
            
    for i from 0 to k-1:
        print "Location", result[i], ":", arr[result[i]]

Algorithm Explanation

1. Create a function difference(arr, value, index) that calculates the difference between the given value and the element at arr[index]. It returns the absolute difference.
2. Create a function k_closest(arr, size, value, k) that takes the array, its size, the target value, and k as inputs.
3. Check if the size of the array is less than or equal to 1, or if k is greater than the size of the array. If any of these conditions are met, return.
4. Create an array result of size k to store the indices of the k closest elements.
5. Initialize the first k elements of the result array with their respective indices.
6. Iterate through the array starting from index k. For each element:
   • Calculate the difference between the element and the given value.
   • Initialize checker to -1.
   • Compare the current element's difference with the differences of the k closest elements. If it's greater:
     • If checker is -1, set checker to the index of the farthest element among the k closest elements.
     • Otherwise, compare the difference of the element at checker with the auxiliary difference. If the old difference is smaller, update checker.
   • If checker is not -1, update the result array with the index of the current element.
7. Print the k closest elements from the result array.

Code Solution

• C
• C++
• Java
• C#
• Php
• Node Js
• Python
• Ruby
• Scala
• Swift 4

//C Program
//Find k closest numbers in an unsorted array
#include <stdio.h>

//Get difference of two elements
int difference(int arr[],int value,int index)
{
  if(value > arr[index])
  {
    return value-arr[index];
  }
  else
  {
    return arr[index]-value;
  }

}
void k_closest(int arr[],int size,int value,int k)
{
  if(size<=1 || k > size )
  {
    return;
  }

  int result[k];
  
  int diff=0,auxiliary=0,checker=0,old=0;
  
  for (int i = 0; i < k; ++i)
  {
    result[i]=i;
  }
 
  for (int i = k; i < size; ++i)
  {
    diff = difference(arr,value,i);
    checker=-1;
    for (int j = 0; j < k; ++j)
    {
      auxiliary = difference(arr,value,result[j]);

      if(auxiliary > diff)
      { 
        if(checker==-1)
        {
          checker=result[j];
        }
        else
        {
          old = difference(arr,value,checker);

          if(old < auxiliary)
          {
             checker=result[j];
          }

        }   
      }


    }
    if(checker!=-1)
    {
      result[checker]=i;
    }
  }

  for (int i = 0; i < k; ++i)
  {
    printf("Location %d : %d\n",result[i],arr[result[i]] );
  }
}

int main()
{
  //Defining collection array elements
  int arr[] = {1, 6, 4, 10, 2, 5};
  //Get the size of array
  int size=sizeof(arr)/sizeof(arr[0]);

  k_closest(arr,size,5,4);
  return 0;
}

Location 5 : 5
Location 1 : 6
Location 2 : 4
Location 4 : 2

/*
  C++ Program
  Find k closest numbers in an unsorted array
*/
#include<iostream>

using namespace std;

class MyArray {
	public:

		//Get difference of two elements
		int difference(int arr[], int value, int index) {
			if (value > arr[index]) {
				return value - arr[index];
			} else {
				return arr[index] - value;
			}
		}
	void k_closest(int arr[], int size, int value, int k) {
		if (size <= 1 || k > size) {
			return;
		}
		int result[k];
		int diff = 0, auxiliary = 0, checker = 0, old = 0;
		for (int i = 0; i < k; ++i) {
			result[i] = i;
		}
		for (int i = k; i < size; ++i) {
			diff = this->difference(arr, value, i);
			checker = -1;
			for (int j = 0; j < k; ++j) {
				auxiliary = this->difference(arr, value, result[j]);
				if (auxiliary > diff) {
					if (checker == -1) {
						checker = result[j];
					} else {
						old = this->difference(arr, value, checker);
						if (old < auxiliary) {
							checker = result[j];
						}
					}
				}
			}
			if (checker != -1) {
				result[checker] = i;
			}
		}
		for (int i = 0; i < k; ++i) {
			cout << "Location " << result[i] << " : " << arr[result[i]] << "\n";
		}
	}
};
int main() {
	MyArray obj ;
	int arr[] = {
		1,
		6,
		4,
		10,
		2,
		5
	};
	//Count size of array
	int size = sizeof(arr) / sizeof(arr[0]);
	obj.k_closest(arr, size, 5, 4);
	return 0;
}

Location 5 : 5
Location 1 : 6
Location 2 : 4
Location 4 : 2

/*
  Java Program
  Find k closest numbers in an unsorted array
*/
public class MyArray {

  //Get difference of two elements
  public int difference(int []arr,int value,int index)
  {
    if(value > arr[index])
    {
      return value-arr[index];
    }
    else
    {
      return arr[index]-value;
    }

  }
  public void k_closest(int []arr,int size,int value,int k)
  {
    if(size<=1 || k > size )
    {
      return;
    }

    int []result = new int[k];
    
    int diff=0,auxiliary=0,checker=0,old=0;
    
    for (int i = 0; i < k; ++i)
    {
      result[i]=i;
    }
   
    for (int i = k; i < size; ++i)
    {
      diff = difference(arr,value,i);
      checker=-1;
      for (int j = 0; j < k; ++j)
      {
        auxiliary = difference(arr,value,result[j]);

        if(auxiliary > diff)
        { 
          if(checker==-1)
          {
            checker=result[j];
          }
          else
          {
            old = difference(arr,value,checker);

            if(old < auxiliary)
            {
               checker=result[j];
            }

          }   
        }


      }
      if(checker!=-1)
      {
        result[checker]=i;
      }
    }

    for (int i = 0; i < k; ++i)
    {
      System.out.print("Location "+result[i]+" : "+arr[result[i]]+"\n");
    }
  }

  public static void main(String[] args) 
  {

    MyArray obj = new MyArray();
    //Define array elements
    int []arr = {1, 6, 4, 10, 2, 5};
    //Count size of array
    int size=arr.length;
 

    obj.k_closest(arr,size,5,4);

  }
}

Location 5 : 5
Location 1 : 6
Location 2 : 4
Location 4 : 2

using System;

/*
  C# Program
  Find k closest numbers in an unsorted array
*/

public class MyArray {
	//Get difference of two elements
	public int difference(int[] arr, int value, int index) {
		if (value > arr[index]) {
			return value - arr[index];
		} else {
			return arr[index] - value;
		}
	}
	public void k_closest(int[] arr, int size, int value, int k) {
		if (size <= 1 || k > size) {
			return;
		}
		int[] result = new int[k];
		int diff = 0, auxiliary = 0, checker = 0, old = 0;
		for (int i = 0; i < k; ++i) {
			result[i] = i;
		}
		for (int i = k; i < size; ++i) {
			diff = difference(arr, value, i);
			checker = -1;
			for (int j = 0; j < k; ++j) {
				auxiliary = difference(arr, value, result[j]);
				if (auxiliary > diff) {
					if (checker == -1) {
						checker = result[j];
					} else {
						old = difference(arr, value, checker);
						if (old < auxiliary) {
							checker = result[j];
						}
					}
				}
			}
			if (checker != -1) {
				result[checker] = i;
			}
		}
		for (int i = 0; i < k; ++i) {
			Console.Write("Location " + result[i] + " : " + arr[result[i]] + "\n");
		}
	}
	public static void Main(String[] args) {
		MyArray obj = new MyArray();
		int[]
		//Define array elements
		arr = {
			1,
			6,
			4,
			10,
			2,
			5
		};
		//Count size of array
		int size = arr.Length;
		obj.k_closest(arr, size, 5, 4);
	}
}

Location 5 : 5
Location 1 : 6
Location 2 : 4
Location 4 : 2

<?php
/*
  Php Program
  Find k closest numbers in an unsorted array
*/
class MyArray {
	//Get difference of two elements

	public 	function difference($arr, $value, $index) {
		if ($value > $arr[$index]) {
			return $value - $arr[$index];
		} else {
			return $arr[$index] - $value;
		}
	}
	public 	function k_closest($arr, $size, $value, $k) {
		if ($size <= 1 || $k > $size) {
			return;
		}
		$result = array_fill(0, $k, 0);
		$diff = 0;
		$auxiliary = 0;
		$checker = 0;
		$old = 0;
		for ($i = 0; $i < $k; ++$i) {
			$result[$i] = $i;
		}
		for ($i = $k; $i < $size; ++$i) {
			$diff = $this->difference($arr, $value, $i);
			$checker = -1;
			for ($j = 0; $j < $k; ++$j) {
				$auxiliary = $this->difference($arr, $value, $result[$j]);
				if ($auxiliary > $diff) {
					if ($checker == -1) {
						$checker = $result[$j];
					} else {
						$old = $this->difference($arr, $value, $checker);
						if ($old < $auxiliary) {
							$checker = $result[$j];
						}
					}
				}
			}
			if ($checker != -1) {
				$result[$checker] = $i;
			}
		}
		for ($i = 0; $i < $k; ++$i) {
			echo("Location ". $result[$i] ." : ". $arr[$result[$i]] ."\n");
		}
	}
}

function main() {
	$obj = new MyArray();
	//Define array elements
	$arr = array(1, 6, 4, 10, 2, 5);
	//Count size of array
	$size = count($arr);
	$obj->k_closest($arr, $size, 5, 4);

}
main();

Location 5 : 5
Location 1 : 6
Location 2 : 4
Location 4 : 2

/*
  Node Js Program
  Find k closest numbers in an unsorted array
*/
class MyArray {
	//Get difference of two elements
	difference(arr, value, index) {
		if (value > arr[index]) {
			return value - arr[index];
		} else {
			return arr[index] - value;
		}
	}
	k_closest(arr, size, value, k) {
		if (size <= 1 || k > size) {
			return;
		}
		var result = Array(k).fill(0);
		var diff = 0;
		var auxiliary = 0;
		var checker = 0;
		var old = 0;
		for (var i = 0; i < k; ++i) {
			result[i] = i;
		}

		for (var i = k; i < size; ++i) {
			diff = this.difference(arr, value, i);
			checker = -1;
			for (var j = 0; j < k; ++j) {
				auxiliary = this.difference(arr, value, result[j]);
				if (auxiliary > diff) {
					if (checker == -1) {
						checker = result[j];
					} else {
						old = this.difference(arr, value, checker);
						if (old < auxiliary) {
							checker = result[j];
						}
					}
				}
			}

			if (checker != -1) {
				result[checker] = i;
			}
		}

		for (var i = 0; i < k; ++i) {
			process.stdout.write("Location " + result[i] + " : " + arr[result[i]] + "\n");
		}
	}
}

function main(args) {
	var obj = new MyArray();
	//Define array elements
	var arr = [1, 6, 4, 10, 2, 5];
	//Count size of array
	var size = arr.length;
	obj.k_closest(arr, size, 5, 4);
}

main();

Location 5 : 5
Location 1 : 6
Location 2 : 4
Location 4 : 2

# Python 3 Program
# Find k closest numbers in an unsorted array
class MyArray :
	# Get difference of two elements
	def difference(self, arr, value, index) :
		if (value > arr[index]) :
			return value - arr[index]
		else :
			return arr[index] - value
		
	
	def k_closest(self, arr, size, value, k) :
		if (size <= 1 or k > size) :
			return
		
		result = [0] * k
		diff = 0
		auxiliary = 0
		checker = 0
		old = 0
		i = 0
		while (i < k) :
			result[i] = i
			i += 1
		
		i = k
		while (i < size) :
			diff = self.difference(arr, value, i)
			checker = -1
			j = 0
			while (j < k) :
				auxiliary = self.difference(arr, value, result[j])
				if (auxiliary > diff) :
					if (checker == -1) :
						checker = result[j]
					else :
						old = self.difference(arr, value, checker)
						if (old < auxiliary) :
							checker = result[j]
						
					
				
				j += 1
			
			if (checker != -1) :
				result[checker] = i
			
			i += 1
		
		i = 0
		while (i < k) :
			print("Location ", result[i] ," : ", arr[result[i]] ,"\n", end = "")
			i += 1
		
	

def main() :
	obj = MyArray()
	arr = [1, 6, 4, 10, 2, 5]
	size = len(arr)
	obj.k_closest(arr, size, 5, 4)


if __name__ == "__main__":
	main()

Location  5  :  5
Location  1  :  6
Location  2  :  4
Location  4  :  2

# Ruby Program
# Find k closest numbers in an unsorted array
class MyArray 
	# Get difference of two elements
	def difference(arr, value, index) 
		if (value > arr[index]) 
			return value - arr[index]
		else 
			return arr[index] - value
		end
	end
	def k_closest(arr, size, value, k) 
		if (size <= 1 || k > size) 
			return
		end
		result = Array.new(k, 0)
		diff = 0
		auxiliary = 0
		checker = 0
		old = 0
		i = 0
		while (i < k) 
			result[i] = i
			i += 1
		end
		i = k
		while (i < size) 
			diff = self.difference(arr, value, i)
			checker = -1
			j = 0
			while (j < k) 
				auxiliary = self.difference(arr, value, result[j])
				if (auxiliary > diff) 
					if (checker == -1) 
						checker = result[j]
					else 
						old = self.difference(arr, value, checker)
						if (old < auxiliary) 
							checker = result[j]
						end
					end
				end
				j += 1
			end
			if (checker != -1) 
				result[checker] = i
			end
			i += 1
		end
		i = 0
		while (i < k) 
			print("Location ", result[i] ,"  : ", arr[result[i]] ,"\n")
			i += 1
		end
	end
end
def main() 
	obj = MyArray.new()
	arr = [1, 6, 4, 10, 2, 5]
	size = arr.length
	obj.k_closest(arr, size, 5, 4)
end
main()

Location 5  : 5
Location 1  : 6
Location 2  : 4
Location 4  : 2

/*
  Scala Program
  Find k closest numbers in an unsorted array
*/
class MyArray {
	//Get difference of two elements
	def difference(arr: Array[Int], value: Int, index: Int): Int = {
		if (value > arr(index)) {
			return value - arr(index);
		} else {
			return arr(index) - value;
		}
	}
	def k_closest(arr: Array[Int], size: Int, value: Int, k: Int): Unit = {
		if (size <= 1 || k > size) {
			return;
		}
		var result: Array[Int] = Array.fill[Int](k)(0);
        var diff: Int = 0;
        var auxiliary: Int = 0;
        var checker: Int = 0;
        var old: Int = 0;
        var i: Int = 0;
        while (i < k) {
            result(i) = i;
            i += 1;
        }
        i = k;
        while (i < size) {
            diff = this.difference(arr, value, i);
            checker = -1;
            var j: Int = 0;
            while (j < k) {
                auxiliary = this.difference(arr, value, result(j));

                if (auxiliary > diff) {
                    if (checker == -1) {
                        checker = result(j);
                    } else {
                        old = this.difference(arr, value, checker);

                        if (old < auxiliary) {
                            checker = result(j);
                        }
                    }
                }
                j += 1;
            }
            if (checker != -1) {
                result(checker) = i;
            }
            i += 1;
        }
        i = 0;
        while (i < k) {
            print("Location " + result(i) + " : " + arr(result(i)) + "\n");
            i += 1;
        }
    }
}
object Main {
	def main(args: Array[String]): Unit = {
		val obj: MyArray = new MyArray();
		val arr: Array[Int] = Array(1, 6, 4, 10, 2, 5);
		val size: Int = arr.length;
		obj.k_closest(arr, size, 5, 4);
	}
}

Location 5 : 5
Location 1 : 6
Location 2 : 4
Location 4 : 2

/*
  Swift Program
  Find k closest numbers in an unsorted array
*/
class MyArray {
	//Get difference of two elements
	func difference(_ arr: [Int], _ value: Int, _ index: Int) -> Int {
		if (value > arr[index]) {
			return value - arr[index];
		} else {
			return arr[index] - value;
		}
	}
	func k_closest(_ arr: [Int], _ size: Int, _ value: Int, _ k: Int) {
		if (size <= 1 || k > size) {
			return;
		}
		var result: [Int] = Array(repeating: 0, count: k);
        var diff: Int = 0;
        var auxiliary: Int = 0;
        var checker: Int = 0;
        var old: Int = 0;
        var i: Int = 0;
        while (i < k) {
            result[i] = i;
            i += 1;
        }
        i = k;
        while (i < size) {
            diff = self.difference(arr, value, i);
            checker = -1;
            var j: Int = 0;
            while (j < k) {
                auxiliary = self.difference(arr, value, result[j]);
                if (auxiliary > diff) {
                    if (checker == -1) {
                        checker = result[j];
                    } else {
                        old = self.difference(arr, value, checker);
                        if (old < auxiliary) {
                            checker = result[j];
                        }
                    }
                }
                j += 1;
            }
            if (checker != -1) {
                result[checker] = i;
            }
            i += 1;
        }
        i = 0;
        while (i < k) {
            print("Location ", result[i] ," : ", arr[result[i]] ,"\n", terminator: "");
            i += 1;
        }
    }
}
func main() {
	let obj: MyArray = MyArray();
	let arr: [Int] = [1, 6, 4, 10, 2, 5];
	let size: Int = arr.count;
	obj.k_closest(arr, size, 5, 4);
}
main();

Location  5  :  5
Location  1  :  6
Location  2  :  4
Location  4  :  2

Time Complexity Analysis

The algorithm iterates through the array once to initialize the result array and then again for each remaining element. For each remaining element, it iterates through the result array of size k. Therefore, the worst-case time complexity of the algorithm is O(k * (size - k)), where size is the size of the input array and k is the number of closest elements to find.