Solution: Find the Kth Largest Integer in the Array

Let’s solve the Find the Kth Largest Integer in the Array problem using the Top K Elements pattern.

We'll cover the following

Statement

Given an array of strings, nums, where each string represents an integer without leading zeros, and an integer k, your task is to find and return the string representing the kth^{th} largest integer in the array.

Note: Treat duplicate integers as distinct entities. For instance, if nums =[“2”, “3”, “3”]= [\text{\lq\lq2\rq\rq, \lq\lq3\rq\rq, \lq\lq3\rq\rq]}, the first largest integer is “3”\text{\lq\lq3\rq\rq}, the second largest is also “3”\text{\lq\lq3\rq\rq}, and the third largest is “2”\text{\lq\lq2\rq\rq}.

Constraints:

  • 1<=1 <= k <=<= nums.length <=103<= 10^3

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

  • nums[i] consists of only digits.

  • nums[i] will not have any leading zeros.

Solution

The essence of this solution is to use the top K elements pattern to find the kth^{th} largest number in an array of strings. We maintain the k largest elements using a min heap while iterating through the array. The heap allows us to track and update the k largest elements without sorting the entire array, ensuring an optimal solution for finding the kth^{th} largest element.

Now, let’s look at the steps of the solution:

  1. We initialize an empty min heap, heap, which will be used to store the k largest numbers.

  2. We iterate over each string in nums, and for each string, we convert the string to an integer and push it into the heap.

  3. We also maintain the size of the heap. After pushing each number into the heap, we check if the size of the heap exceeds k. If it does, we remove the smallest element from the top of the heap. This ensures that only the k largest elements are always retained in the heap.

  4. After iterating over nums, we return the kth^{th}largest element as the root of the heap (the smallest element in the min heap) because the heap only contains the k largest elements. We also convert the root of the heap back to a string before returning.

Let’s look at the following illustration to get a better understanding of the solution:

Press + to interact
canvasAnimation-image
1 of 12

Let’s look at the code for the solution we just discussed.

import java.util.*;
import java.math.BigInteger;
public class Solution {
    // Function to find the k-th largest integer in a list of string numbers
    public static String kthLargestInteger(String[] nums, int k) {
        PriorityQueue<BigInteger> minHeap = new PriorityQueue<>();
        for (String num : nums) {
            BigInteger val = new BigInteger(num);
            minHeap.add(val);
            if (minHeap.size() > k) {
                minHeap.poll();
            }
        }
        return minHeap.peek().toString(); 
    }
    public static void main(String[] args) {
        String[][] testCases = {
            {"3", "6", "7", "10"},
            {"2", "21", "12", "1"},
            {"0", "0"},
            {"100", "200", "300", "400"},
            {"10", "100", "1000", "10000"}
        };
        int[] kValues = {4, 3, 2, 2, 1};
        Solution solution = new Solution();
        for (int i = 0; i < testCases.length; i++) {
            String[] nums = testCases[i]; 
            int k = kValues[i];          
            String result = solution.kthLargestInteger(nums, k);
            System.out.println((i + 1) + ".\t nums: " + Arrays.toString(nums) + ", k: " + k);
            System.out.println("\t kth largest integer: " + result);
            System.out.println(new String(new char[100]).replace("\0", "-"));
        }
    }
}
Find the Kth Largest Integer in the Array

Time complexity

We iterate through each element in the nums array with  nn elements. For each element, we perform a push operation, which takes O(log⁡⁡k)O(\log⁡k). Therefore, for each element, we perform at most two heap operations, each taking O(log⁡⁡k)O(\log⁡k) time. Therefore, the overall time complexity of the solution is O(nlog⁡⁡k)O(n\log⁡k), where nn is the number of elements in nums and k is the size of the heap.

Space complexity

The space complexity of this solution is O(k)O(k) because we are using a heap that stores up to k elements at any given time in the heap.

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.