<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:
        # Use a counter dictionary?
        c = Counter(nums)
        print(c)
        for i in range(10000, -10000, -1):
            if i in c:
                print(i, c[i])
                k -= c[i]
                if k <= 0:
                    return i
        return 0

class Solution2:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        
        # Quickselect -> O(n^2) almost certain avg case O(n)
        # 1) Choosing a pivot (choose last item, but random() might prevent pathological cases where data is already sorted)
        # 2) Partition based on that pivot
        # 3) Recurse down only one of the two partitions
        
        # Partition according to pivot - highest are on the right.
        def partition(low: int, high: int) -> int:
            #pivot = high
            # select a random pivot_index between 
            pivot = random.randint(low, high)   
            
            # Move pivot to end
            nums[high], nums[pivot] = nums[pivot], nums[high]
            pivot = high
            
            pivot_value = nums[pivot]
            left = low
            
            #            left->
            # <p1...><new_pivot_pos><p2...>
            
            for i in range(low, high):
                if nums[i] < pivot_value:
                    nums[i], nums[left] = nums[left], nums[i]
                    left += 1
            
            nums[pivot], nums[left] = nums[left], nums[pivot]
            return left
        
        def qselect(low: int, high: int, place: int) -> int:
            if low == high:
                return nums[low]
            
            pivot_pos = partition(low, high)
            # We have 3 partitions: low:pivot_pos, pivot_pos:pivot_pos+1, pivot_pos+1:high+1
            right_partition_len = high - pivot_pos
            if right_partition_len >= place:
                # Recurse on right partition
                return qselect(pivot_pos + 1, high, place)
            elif right_partition_len + 1 >= place:
                # Return our pivot.
                return nums[pivot_pos]
            else:
                # Recurse on left partition.
                new_place = place - right_partition_len - 1
                return qselect(low, pivot_pos - 1, new_place)
        
        return qselect(0, len(nums) - 1, k)
        
31437