<p>Given an integer array <code>nums</code> and an integer <code>k</code>, return <em>the</em> <code>k<sup>th</sup></code> <em>largest element in the array</em>.</p>

<p>Note that it is the <code>k<sup>th</sup></code> largest element in the sorted order, not the <code>k<sup>th</sup></code> distinct element.</p>

<p>Can you solve it without sorting?</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<pre><strong>Input:</strong> nums = [3,2,1,5,6,4], k = 2
<strong>Output:</strong> 5
</pre><p><strong class="example">Example 2:</strong></p>
<pre><strong>Input:</strong> nums = [3,2,3,1,2,4,5,5,6], k = 4
<strong>Output:</strong> 4
</pre>
<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= k &lt;= nums.length &lt;= 10<sup>5</sup></code></li>
	<li><code>-10<sup>4</sup> &lt;= nums[i] &lt;= 10<sup>4</sup></code></li>
</ul>

class Solution {
public:
    int partition(int l, int r, vector<int> &nums) {
        int pick = nums[l];
        int i= r;
        int j = l+1;
        while( j <= i) {
            if( nums[j] < pick && nums[i] > pick ) {
                swap(nums[j] , nums[i]);
                j++;
                i--;
            }
            if(nums[j] >= pick) j++;
            if(nums[i] <= pick)  i--;
        }
        swap(nums[l] , nums[i]);
        return i;
    }

    int findKthLargest(std::vector<int>& nums, int k) {
        // priority_queue<int, vector<int>, greater<int>> pq;
        // int n = nums.size();

        // for(int i=0; i<n; i++) {
        //     pq.push(nums[i]);

        //     if(pq.size() > k) {
        //         pq.pop();
        //     }

        // }
        // return pq.top();

        int n = nums.size();
        
        int r = n-1;
        int l = 0;
        while(true) {
            
            int pivot = partition(l, r, nums);

            if(pivot == k-1) {
                return nums[pivot];
            }
            else if( pivot > k-1) {
                r = pivot -1;
            }else {
                l = pivot +1;
            }
        }
    return -1;
    }
};
57800