<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:
    def findKthLargest(self, nums: List[int], k: int) -> int:

        # time complexity if we sort the array and return length - k element is O(nlogn)
        # same TLE in the testcase in which there are uncountable 1 only 
        # def quickSort(nums, s, e):
        #     if (e - s + 1) <= 1:
        #         return nums
        #     pivot = nums[e]

        #     j = s
        #     for i in range(s, e):
        #         if nums[i] <= pivot:
        #             nums[i], nums[j] = nums[j], nums[i]
        #             j = j + 1
        #     temp = nums[j]
        #     nums[j] = pivot
        #     nums[e] = temp

        #     quickSort(nums, s, j - 1)
        #     quickSort(nums, j + 1, e)
        #     return nums

        # arr = quickSort(nums, 0, len(nums) - 1)
        # return arr[len(nums) - k]


        # if we use max heap --> time complexity to build it O(n) we will have to pop k elements to get the kth largest element and each time the heap will percolate in O(logn) so overall it is 
        # O(n + klogn) in case k is smaller in comparison to n it is effecient 
        # but if k = n it will become O(n+nlogn) --> O(nlogn) same as above

        # we will use quick select (avg -> O(n), worst -> O(n^2))
        # target_index = len(nums) - k
        # def quickSelect(nums, s, e):
            
        #     if (e - s + 1) <= 1:
        #         #return nums[0]            # big mistake
        #         return nums[s]
        #     pivot = nums[e]

        #     j = s
        #     for i in range(s, e):
        #         if nums[i] <= pivot:
        #             nums[i], nums[j] = nums[j], nums[i]
        #             j = j + 1
        #     temp = nums[j]
        #     nums[j] = pivot
        #     nums[e] = temp

        #     if j == target_index:
        #         return nums[j]
        #     elif j < target_index:
        #         return quickSelect(nums, j + 1, e)
        #     else:
        #         return quickSelect(nums, s, j-1)

        # return quickSelect(nums, 0, len(nums) - 1)

        # same problem TLE 
        # I will use Hoare's partition instead of Lomuto partition next time

        # Using Max Heap (O(N+KlogN))

        import heapq
        for i  in range(len(nums)):
            nums[i] = -nums[i]

        heapq.heapify(nums)

        for _ in range(k-1):
            heapq.heappop(nums)

        return -1 * heapq.heappop(nums)

        



        



26312