I got a google interview type question from facebook:
You are given an array and an integer k. Find the Kth largest integer in that array.
Expected time complexity - O(n)
Expected space complexity - O(1)
I was shocked by the fact that the time complexity can be O(n) !
Can someone please explain?