Algorithm A

Given an array of N integers, sort the array, and find the 2 consecutive numbers in the sorted array with the maximum difference. Example - on input [1,7,3,2] output 4 (the sorted array is [1,2,3,7], and the maximum difference is 7-3=4).

Algorithm A runs in O(NlogN) time.

Implement an algorithm identical in function to algorithm A, that runs in O(N) time.

Thanks to Yossi Richter for this riddle!

Spoiler Alert - Solution Ahead

We first find the minimum and maximum of the array. We then allocate another array, call it B, of size N + 2. We let each cell in B contain two integers. Let \(s = \frac{max(A) - min(A)}{N + 2}\). We pseudo-sort the elements of the original array into array B, such that the first bucket of B represents the integers [min(A), s), the second bucket represents [s, 2s), …, the bucket before last represents [max(A) - s, max(A)), and the last bucket represents [max(A), max(A) + s). We only keep the minimum and the maximum in each bucket (hence the 2 integers in each cell of B). Now, we are splitting N numbers between N + 2 cells, so there must be at least one empty cell. We know that the first and last cells are not empty (as they respectively contain the minimum and maximum elements of the original array), so that means that there are 2 consecutive elements with a distance of at least s. That means that the 2 consecutive elements with maximum distance are the maximum and minimum elements in two cells of B such that all cells between them are empty. \(\blacksquare\)

In python:

from dataclasses import dataclass

@dataclass
class Bucket:
  min : int = None
  max : int = None

  def add(self, x : int):
    if not self.min or x < self.min:
      self.min = x
    if not self.max or x > self.max:
      self.max = x

  def empty(self):
    return self.min == self.max == None

def max_diff_neighbors(A):
  N = len(A)
  mn, mx = min(A), max(A)
  tot = mx - mn
  B = [Bucket() for i in range(N + 2)]
  for x in A:
    bucket = (x - mn) * (N + 1) // tot
    B[bucket].add(x)
  max_diff = 0
  cur = B[0].max
  for i in range(1, N+2):
    if B[i].empty(): continue
    diff = B[i].min - cur
    if diff > max_diff: max_diff = diff
    cur = B[i].max
  return max_diff