# You will receive arr which is a sorted list, N and K and find K nearest number pairs for N
# For example, 
# arr = [1, 2, 3, 5, 6, 7, 9, 10, 14, 15, 16, 18, 20], N = 10, K = 3
# Except 10, you can get 2 three nearest num pairs like this.
# [[6, 7, 9], [7, 9, 14]]
# arr = [1, 2, 3, 5, 6, 7, 9, 10, 14, 15, 16, 18, 20], N = 1, K = 3
# [[2, 3, 5]]
# arr = [1, 2, 3, 5, 6, 7, 9, 10, 14, 15, 16, 18, 20], N = 20, K = 3
# [[15, 16, 18]]

from collections import defaultdict

# M: len of arr
# Time O(logM + K)
# Space O(K * K)

def kNearestNums(arr, n, k):
    # Using BST
    start, end = 0, len(arr) - 1
    while start <= end: # Time O(logM)
        mid = (start + end) // 2
        if arr[mid] == n:
            # mid will be N's index
            break
        elif arr[mid] > n:
            # Move left
            end = mid - 1
        else:
            # Move right
            start = mid + 1

    # Narrow down candidates
    hashTable = defaultdict(list) # Space O(K * K) because k-sized array k times
    candidates = arr[mid - k: mid] + arr[mid + 1: mid + k + 1] # Space O(2K) => O(K)

    # Init val, startToEnd
    start, end = 0, 0 + k - 1
    val, startToEnd = 0, []
    for i in range(start, end + 1): # Time O(K)
        val += abs(candidates[i] - n)
        startToEnd.append(candidates[i])
    hashTable[val].append(startToEnd.copy())
    minVal = val
    def move():
        nonlocal val, startToEnd, start, end
        val -= abs(startToEnd[0] - n)
        startToEnd.pop(0)    
        start += 1
        end += 1
        if end < len(candidates):
            startToEnd.append(candidates[end])    
            val += abs(candidates[end] - n)
    move()

    # Move K-sized window one by one
    while start < len(candidates) - k: # Time O(K)
        hashTable[val].append(startToEnd.copy())
        minVal = min(minVal, val)
        move()
    return hashTable[minVal]

print(kNearestNums([1, 2, 3, 5, 6, 7, 9, 10, 14, 15, 16, 18, 20], 10, 3))
print(kNearestNums([1, 2, 3, 5, 6, 7, 9, 10, 14, 15, 16, 18, 20], 1, 3))
print(kNearestNums([1, 2, 3, 5, 6, 7, 9, 10, 14, 15, 16, 18, 20], 20, 3))