You can use the median of medians with quickselect to guarantee the O(N) time complexity.