Closest Numbers — HackerRank

Hello, I took some rest after completing 30 Days of code challenge, I have been studying new frameworks at work, such as FastAPI and now I am back with new algorithm solution.

Today’s task is called “Closest Numbers ”. Difficulty level — easy.

If we follow task’s description we can see that we have an array of numbers, negative numbers included, and we want to find numbers with minimum difference between them.

Example

arr = [5, 2, 3, 4, 1]

Sorted array is as follows sorted_arr = [1, 2, 3, 4, 5] . Then we find the pairs with minimum difference such as (1, 2), (2, 3), (3, 4) and (4,5). Finally, we return the array: [1, 2, 2, 3, 3, 4, 4, 5]

What we can notice right away is that we need to sort the array, first. Then compare all the values and their difference. In this case we are looking for a minimum difference and what numbers make that difference. For problems that need to keep track of values and when they appear, I suggest using of a dictionary structure. For key we will have the difference value and for values the numbers having that difference. Important thing we need to pay attention to are the constraints. It is said that every arr[i] number is unique, so we do not have to worry for repeating numbers in the dictionary.

If two numbers A and B give difference C then the same number A or B, paired with D cannot give C.

Solution I came with is posted above. Please, note that you can implement your own sorting algorithm or use sort(). After sorting is done we proceed with finding the differences. Here, you can use python’s min() to find the minimum value among all dictionary keys.

def closestNumbers(arr):
  min_diff = None 
  mergeSort(arr)
  differences = {}
  for i in range(len(arr)-1):
     if arr[i] <= arr[i+1]:
       diff = arr[i+1] - arr[i]
     else:
       diff = arr[i] - arr[i+1]
     differences[diff] = differences.get(diff, []) + [arr[i], arr[i+1]]
     if min_diff:
        if min_diff > diff:
           min_diff = diff
         else:
           min_diff = diff
  return differences[min_diff]

Have a happy coding ~