K Closest Elements time and testcases are misleading

The accepted solution times for K closest elements are bi-modal. Comparing samples from the "faster" peak versus the "slower" peak, the faster solutions start with pointers at 0 and length-1, and walk them in, which is O(n) complexity. The "slower" solutions start with a binary search for x, then walk the pointers out, which is O(logn) complexity. The latter should be faster, given the constraints posed in the problem, namely 1 < arr.length < 10^4, but it appears that the testcases given are closer to 1 < arr.length < 10. As the length of arr increases, the O(n) solution's time will increase significantly faster than the O(logn) solution, but the accepted solution time tells the opposite story, since the testcases don't accurately reflect the given constraints.

Comments (0)