<p>You are given an array of strings <code>nums</code> and an integer <code>k</code>. Each string in <code>nums</code> represents an integer without leading zeros.</p>

<p>Return <em>the string that represents the </em><code>k<sup>th</sup></code><em><strong> largest integer</strong> in </em><code>nums</code>.</p>

<p><strong>Note</strong>: Duplicate numbers should be counted distinctly. For example, if <code>nums</code> is <code>[&quot;1&quot;,&quot;2&quot;,&quot;2&quot;]</code>, <code>&quot;2&quot;</code> is the first largest integer, <code>&quot;2&quot;</code> is the second-largest integer, and <code>&quot;1&quot;</code> is the third-largest integer.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums = [&quot;3&quot;,&quot;6&quot;,&quot;7&quot;,&quot;10&quot;], k = 4
<strong>Output:</strong> &quot;3&quot;
<strong>Explanation:</strong>
The numbers in nums sorted in non-decreasing order are [&quot;3&quot;,&quot;6&quot;,&quot;7&quot;,&quot;10&quot;].
The 4<sup>th</sup> largest integer in nums is &quot;3&quot;.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums = [&quot;2&quot;,&quot;21&quot;,&quot;12&quot;,&quot;1&quot;], k = 3
<strong>Output:</strong> &quot;2&quot;
<strong>Explanation:</strong>
The numbers in nums sorted in non-decreasing order are [&quot;1&quot;,&quot;2&quot;,&quot;12&quot;,&quot;21&quot;].
The 3<sup>rd</sup> largest integer in nums is &quot;2&quot;.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> nums = [&quot;0&quot;,&quot;0&quot;], k = 2
<strong>Output:</strong> &quot;0&quot;
<strong>Explanation:</strong>
The numbers in nums sorted in non-decreasing order are [&quot;0&quot;,&quot;0&quot;].
The 2<sup>nd</sup> largest integer in nums is &quot;0&quot;.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= k &lt;= nums.length &lt;= 10<sup>4</sup></code></li>
	<li><code>1 &lt;= nums[i].length &lt;= 100</code></li>
	<li><code>nums[i]</code> consists of only digits.</li>
	<li><code>nums[i]</code> will not have any leading zeros.</li>
</ul>

class Solution:
    def kthLargestNumber(self, nums: List[str], k: int) -> str:
        # no leading zeros: order of magnitude is number of digits
        # then within each number of digits we compare lexically

        k -= 1 # index in sorted array

        # quickselect to flex

        def compare(s1: str, s2: str) -> int:
            N1 = len(s1)
            N2 = len(s2)
            if N1 > N2: return 1
            elif N1 < N2: return -1
            else:
                for c1, c2 in zip(s1, s2):
                    if c1 > c2: return 1
                    elif c1 < c2: return -1
                return 0

        lo = 0
        hi = len(nums)-1
        while lo < hi:
            p = nums[randrange(lo, hi)]
            l = lo-1
            r = hi+1
            while l < r:
                l += 1
                r -= 1
                while compare(nums[l], p) > 0: l += 1 # fixed: pivot so larger values are left
                while compare(nums[r], p) < 0: r -= 1
                if l < r: nums[l], nums[r] = nums[r], nums[l]

            if k <= r:
                hi = r
            else:
                lo = r+1

        return nums[k]

        # TC: O(n) compares, worst case compare time is average length L of a string
        #   > if it's lopsided then most compares are O(1)
        #   > if it's all the average then that's the worst case
        # average length is chars / n
        # and thus O(n * chars/n) = O(totalChars) is the worst case

        # possible speedup: bucket sort by length first as an easy first step
381