def findClosestElements(self, arr, k, x):
end = k
for i in xrange(k, len(arr)):
delta = abs(arr[i]  x)  abs(arr[i  k]  x)
if delta > 0:
return arr[end  k:end]
if delta < 0:
end = i + 1
return arr[end  k:end]
Python Simple, O(n) Solution

(Edit: This refers to the original title, which said "O(nk)". It's fixed now.)
@dylan20 It's not O(nk). In case of k=n, that would mean O(0). But your
arr[end  k:end]
copies the entire array, which takes Θ(n).

Hmm, I just realized that I didn't even need to look at the special cases with k=n. I did because the
arr[end  k:end]
alone already disproved O(nk), and I'm rather minimalistic. But if we look at the whole code, we can simply say that the loop takes Θ(nk) and the return value takes Θ(k), for a total of Θ(n).