Leetcode 1985: Find the Kth Largest Integer in the Array

Input: The input consists of an array of strings nums, where each string represents an integer, and an integer k that represents the kth largest number to return.

Example: nums = ['5', '12', '15', '9'], k = 2

Constraints:

• 1 <= k <= nums.length <= 10^4

• 1 <= nums[i].length <= 100

• nums[i] consists of only digits

• nums[i] will not have any leading zeros

Output: Return the string that represents the kth largest integer from the input array.

Example: Output: '12'

Constraints:

• The output should be the kth largest number, as a string.

Goal: The goal is to find the kth largest integer in the list, where duplicates are counted distinctly.

Steps:

• Use a priority queue (min-heap) to maintain the top k largest numbers.

• For each number in the array, insert it into the priority queue.

• If the size of the heap exceeds k, remove the smallest element.

• After processing all numbers, the root of the heap will be the kth largest number.

Goal: The array can be large, so the algorithm should be efficient in both time and space.

Steps:

• The solution should work for arrays with up to 10,000 elements efficiently.

Assumptions:

• The array is non-empty and contains valid numbers as strings.

• Input: Input: nums = ['5', '12', '15', '9'], k = 2

• Explanation: After sorting the array in non-decreasing order, we get ['5', '9', '12', '15']. The 2nd largest number is '12'.

• Input: Input: nums = ['2', '1', '2'], k = 3

• Explanation: The sorted array is ['1', '2', '2']. The 3rd largest number is '1'.

Approach: We will use a priority queue (min-heap) to efficiently track the kth largest element as we process each element in the array.

Observations:

• We can maintain a heap of size k to efficiently keep track of the largest numbers seen so far.

• Using a heap will allow us to remove the smallest number efficiently when the heap size exceeds k, ensuring the heap always holds the k largest numbers.

Steps:

• Create a min-heap to store the top k largest numbers.

• Iterate through the array, adding each number to the heap.

• If the heap exceeds size k, remove the smallest element.

• Return the root of the heap as the kth largest number.

Empty Inputs:

• The array will always contain at least one number, so this case doesn't need to be handled explicitly.

Large Inputs:

• For large arrays, ensure that the priority queue is implemented efficiently to handle up to 10,000 numbers.

Special Values:

• If k equals the length of the array, the kth largest number is the smallest element in the array.

Constraints:

• The algorithm should operate within O(n log k) time complexity, where n is the length of the array.

string kthLargestNumber(vector<string>& nums, int k) {
    priority_queue<string, vector<string>, cmp> pq;
    for(int i = 0; i < nums.size(); i++) {
        
        pq.push(nums[i]);
        while(pq.size() > k) {
            pq.pop();
        }


    }
    
    return pq.top();
}

1 : Function Definition

string kthLargestNumber(vector<string>& nums, int k) {

Defines the function `kthLargestNumber` which takes a vector of strings `nums` and an integer `k` to find the k-th largest number.

2 : Priority Queue Initialization

    priority_queue<string, vector<string>, cmp> pq;

Initializes a priority queue `pq` that will store strings in descending order based on the custom comparator `cmp`.

3 : Looping

    for(int i = 0; i < nums.size(); i++) {

Starts a loop that iterates through each element in the vector `nums`.

4 : Queue Operation

        pq.push(nums[i]);

Pushes the current string from `nums` into the priority queue.

5 : Queue Size Check

        while(pq.size() > k) {

Checks if the size of the priority queue exceeds `k`, and if so, removes the smallest element.

6 : Queue Operation

            pq.pop();

Removes the smallest element from the priority queue to maintain only the top `k` largest elements.

7 : Return Statement

    return pq.top();

Returns the top element of the priority queue, which will be the k-th largest number.

Best Case: O(n log k)

Average Case: O(n log k)

Worst Case: O(n log k)

Description: We insert each element into the heap, which takes O(log k) time. The total time complexity is O(n log k), where n is the number of elements.

Best Case: O(k)

Worst Case: O(k)

Description: We use a heap of size k, so the space complexity is O(k).

Leetcode 1985: Find the Kth Largest Integer in the Array

Explore →