[C++/Java/Python] 3 solutions: MinHeap, MaxHeap, QuickSelect - Clean & Concise
\u2714\uFE0F Solution 1: MinHeap\n- Similiar with the problem 215. Kth Largest Element in an Array, in this problem num is a string, not an interger value. \n\t
**\u2714\uFE0F Solution 1: MinHeap**\n- Similiar with the problem **[215. Kth Largest Element in an Array](https://leetcode.com/problems/kth-largest-element-in-an-array/)**, in this problem `num` is a string, not an interger value. \n\t- For C++, Java: We need to custom our comparator since the default comparator is string comparator which compares by **lexicographically** order, it means for example: "123" < "14". \n\t- For Python, we can use native big number feature of Python.\n- The idea is that we use `minHeap` to store up to `k` largest elements so far, where the top of the minHeap is the `kth` largest element.\n\n<iframe src="https://leetcode.com/playground/jQJL2FCQ/shared" frameBorder="0" width="100%" height="420"></iframe>\n\n**Complexity**\n- Time: `O(NlogK * M)`, where `N <= 10^4` is length of `nums` array, `K <= N` is the kth largest element need to output, `M <= 100` is length of each `num`.\n   Explain: The MinHeap keeps up to `K` elements, each `heappush/heappop` operator costs `O(logK)`. We iterate all elements in `nums` and push/pop to the MinHeap `N` times. We need to multiply by `M` as well, since in the worst case, we need to compare strings by their lexicographically.\n- Space: `O(K)`\n\n---\n\n**\u2714\uFE0F Solution 2: MaxHeap**\n- Heapify `nums` to become MaxHeap structure, cost `O(N)` in Time complexity.\n- Then pop `k-1` elements from the max heap, the `kth` element in the MaxHeap is the `kth` largest element in the `nums` array.\n\n<iframe src="https://leetcode.com/playground/aQqpYbTi/shared" frameBorder="0" width="100%" height="400"></iframe>\n\n**Complexity**\n- Time: `O((N + KlogN) * M)`, where `N <= 10^4` is length of `nums` array, `K <= N` is the kth largest element need to output, `M <= 100` is length of each `num`.\n  Explain: \n\t  - Heapify costs `O(N)` in Time Complexity.\n\t  - We push/pop to the MinHeap `K` times. \n\t  - We need to multiply by `M` as well, since in the worst case, we need to compare strings by their lexicographically.\n- Space: \n\t- C++: `O(1)`\n\t- Python: `O(N)` need to convert all strings into big numbers.\n\n---\n\n**\u2714\uFE0F Solution 3: Quick Select**\n- In C++, we can use in-built library `nth_element` to achieve `O(N)` in Time Complexity, each comparison operator costs `O(M)` (where `M` is length of string `num`) for comparing strings as well.\n- Can check the implementation of Quick Select in this post **[215. Kth Largest Element in an Array](https://leetcode.com/problems/kth-largest-element-in-an-array/discuss/1349609)**.\n```c++\nclass NumStrMinComparator {\npublic:\n    bool operator() (string &b, string &a) { // Please note, I swap position of `a` and `b` here!\n        if (a.size() != b.size()) return a.size() < b.size();\n        return  a < b;\n    }\n};\n\nclass Solution {\npublic:\n    string kthLargestNumber(vector<string>& nums, int k) {\n        nth_element(begin(nums), begin(nums)+k-1, end(nums), NumStrMinComparator());\n        return nums[k-1];\n    }\n};\n```\n(Credit `@_InviStar_` for providing this approach)\n**Complexity**\n- Time: `O(N * M)`, where `N <= 10^4` is length of `nums` array, `M <= 100` is length of each `num`.\n- Space: `O(N)`
[]