<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>

import math
import statistics

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        def median(numList):
            if all([x == nums[0] for x in nums]):
                return nums[0]
            if len(numList) == 1:
                return numList[0]
            sublist = []
            res = []
            for i in range(math.ceil(len(numList) / 5)):
                if (i*5) + 4 > len(numList):
                    index = len(numList)
                else:
                    index = (i * 5) + 5
                sublist.append(numList[i*5:index])
            for x in sublist:
                res.append(statistics.median_low(x))
            return median(res)

        def selection(numList, pivot, goal):
            # if len(numList) < 5:
            #     print(numList, goal)
            #     numList.sort(reverse=True)
            #     return numList[pivot]
            print(numList, pivot, goal)

            if len(numList) == 1:
                return numList[0]
            if len(numList) == 2:
                return sorted(numList)[-(goal)]
            bigger = []
            smaller = []
            for x in numList:
                if x > pivot:
                    bigger.append(x)
                else:
                    smaller.append(x)
            print(bigger, smaller)
            if len(bigger) == 0 or len(smaller) == 0:
                if len(bigger) == 0:
                    return sorted(numList)[-(goal)]
                else:
                    return sorted(bigger)[-(goal)]
            elif goal <= len(bigger):
                return selection(bigger, median(bigger), goal)
            elif len(bigger) == goal:
                return pivot
            else:
                return selection(smaller, median(smaller), goal - (len(bigger)))
        return selection(nums, median(nums), k)
        # return median(nums)
31562