4ms C++ solution with comments and explanation.


  • 0
    J

    This can easily be done in 1-2 lines of code, but thats going to mean sorting -- and thus O(n log n) time. Not a good solution if you are shooting for optimal efficiency.

    The following code is worst-case O(n^2), but should work in O(n) on average. It is actually possible to do this in worst-case O(n) time (Google "median selection algorithm"), but its painful to write. Probably not worth the effort.

    Explanation: We are using the QuickSort partition algorithm. (Which, along with the MergeSort merge algorithm, you really should know cold when walking into a tech. interview.) If we run partition and get back a value m, that means we have rearranged our array such that:

    1. The m-th largest element is in nums[m]
    2. All elements smaller than then m-th largest element are before it (but not sorted).
    3. All elements larger than the m-th largest element are after it (but not sorted).

    Support m=10. If you are looking go the the 10th smallest* element, you have found it. If m < 10, you know that the 10th smallest element is to the right of element m. Otherwise you know its to the the left of m. Adjust your search bounds and partition again.

    Questions for understanding:

    • Why is this worst-case O(n^2)? (Hint: What happens when you apply this to a sorted list and k=?)
    • Why is this average case O(n), when quick sort is O(n log n)? (Hint: What are you not doing here that you do in quick sort.)
    • This is somewhat similar to binary search. Why is this O(n), when binary search is O(log n)?
    • How would you write this in recursive form? And why shouldn't you?

    Solution:

    int findKthLargest(vector<int>& nums, int k) {
        k = nums.size() - k;   // Makes the code clearer (at least to me).
        int i=0, j = nums.size();
        while (true) {
            int m = partition(nums, i, j);
            if (m==k)  
                return nums[m];
            else if (m < k) // Element must be after nums[m]
                i = m+1;
            else  // Elements must be before nums[m]
                j = m;
        }
        return -1;
    }
    
    int partition(vector<int>& nums, int i, int j) {
        // Basic QuickSort partition algorithm over nums[i], nums[i+1], ..., nums[j-1].  
        // Does not touch nums[j].
        if (j - i <= 2) {
            if (j - i == 2 && nums[i] > nums[j-1])
                swap(nums[i], nums[j-1]);
            return i;
        }
        int part = nums[j-1];
        int a=i, b=i;
        while (b < j-1) {
          if (nums[b] < part) {
              swap(nums[a], nums[b]);
              a++, b++;
          }
          else
              b++;
        }
        swap(nums[a], nums[b]);
        return a;    
    }

  • 1
    S

    if u randomly pick the pivot, u can avoid O(n^2) worst case :)


  • 0
    J

    No: if you randomly pick the pivot, you can greatly reduce the probability of the worst-case. Its still "possible" that you could, by bad luck, keep picking the largest element (or close-to-largest) element at each level of recursion and still get the O(n^2) case. So the worst-case remains O(n^2).

    But you are right that, in practice, that just not going to happen. Its one of those case where only the theoreticians would actually bother to worry about that.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.