Skip to main content
Talentd

Find the Kth Largest Integer in the Array - Solution & Explanation

MediumArrayStringDivide and ConquerSorting14 min readAsked at: Google
Practice this problem

Problem Statement

You are given an array of strings nums and an integer k. Each string in nums represents an integer without leading zeros.

Return the string that represents the kth largest integer in nums.

Note: Duplicate numbers should be counted distinctly. For example, if nums is ["1","2","2"], "2" is the first largest integer, "2" is the second-largest integer, and "1" is the third-largest integer.

 

Example 1:

Input: nums = ["3","6","7","10"], k = 4
Output: "3"
Explanation:
The numbers in nums sorted in non-decreasing order are ["3","6","7","10"].
The 4th largest integer in nums is "3".

Example 2:

Input: nums = ["2","21","12","1"], k = 3
Output: "2"
Explanation:
The numbers in nums sorted in non-decreasing order are ["1","2","12","21"].
The 3rd largest integer in nums is "2".

Example 3:

Input: nums = ["0","0"], k = 2
Output: "0"
Explanation:
The numbers in nums sorted in non-decreasing order are ["0","0"].
The 2nd largest integer in nums is "0".

 

Constraints:

  • 1 <= k <= nums.length <= 104
  • 1 <= nums[i].length <= 100
  • nums[i] consists of only digits.
  • nums[i] will not have any leading zeros.

Approach Overview

Problem Overview: You are given an array of integers represented as strings. The goal is to return the kth largest integer. Since values can exceed normal integer limits, comparison must be done using string length first, then lexicographic order.

Approach 1: Sort and Pick Approach (O(n log n) time, O(1)–O(n) space)

The simplest solution sorts the array of numeric strings in descending numeric order and returns the element at index k-1. Because the values are stored as strings, comparison works by checking length first (longer string means larger number). If two strings have the same length, compare them lexicographically. Most languages allow custom comparators during sorting, making this approach straightforward. This method relies heavily on sorting and works well when the array size is moderate and simplicity is preferred.

Approach 2: Min-Heap (Priority Queue) Approach (O(n log k) time, O(k) space)

This approach maintains a min-heap of size k. Iterate through the array and push each numeric string into the heap using the same comparison logic (length first, then lexicographic). If the heap size exceeds k, remove the smallest element. After processing all elements, the root of the heap is the kth largest number. This approach avoids sorting the entire array and is more efficient when k is much smaller than n. It uses a heap (priority queue) to track the top k largest values.

Approach 3: Quickselect (Average O(n) time, O(1) space)

A selection algorithm similar to quicksort can partition the array around a pivot and recursively search the side containing the kth largest element. Instead of fully sorting the array, Quickselect only processes the portion that contains the target rank. Comparisons still follow the numeric string rules (length then lexicographic). This approach uses ideas from divide and conquer. While the average time complexity is linear, the worst case can degrade to O(n²) without randomized pivots.

Recommended for interviews: The min-heap solution is usually the safest choice. It demonstrates understanding of heaps and efficiently handles large datasets with O(n log k) complexity. Sorting shows clear reasoning and is often accepted in interviews, but the heap approach highlights stronger algorithmic thinking when k is small relative to n.

Approach 1: Sort and Pick Approach

Sort and Pick Approach: The simplest approach is to sort the array of strings based on their numeric values (considering the differences in lengths and lexicographical order when required) and then pick the kth largest element from this sorted array. This approach takes advantage of built-in sort capabilities that can be customized for string comparison in terms of numeric values. After sorting the array in descending order, the kth element can be directly accessed.

The code uses the quicksort function qsort() with a custom comparator. The comparator first checks the lengths of the strings since a larger string length implies a larger number. If the lengths are equal, it compares the strings lexicographically but in reverse order to achieve descending sort. After sorting, it returns the kth element from the sorted array.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n log n) due to sorting, where n is the number of elements in nums.
Space Complexity: O(1) excluding the space required for sorting.

Try this approach in the editor →

Approach 2: Min-Heap (Priority Queue) Approach

Min-Heap Approach: This approach involves using a min-heap (or priority queue) to efficiently find the kth largest element. The idea is to maintain a heap of size k while iterating through the array of strings. By doing so, the smallest element in the heap will automatically become the kth largest once all numbers are processed. This method provides an optimal solution in terms of time complexity compared to sorting.

This C++ code uses a priority queue configured as a min-heap (due to custom comparator) where each string is inserted. If the heap exceeds size k, the smallest number is removed, ensuring the kth largest remains in the heap.

Code

C++JavaPythonJavaScript

C++

Java

Python

JavaScript

Complexity

Time Complexity: O(n log k), where n is the number of elements in nums.
Space Complexity: O(k), due to the heap storing k elements.

Try this approach in the editor →

Approach 3: Sorting or Quickselect

We can sort the strings in the nums array in descending order as integers, and then take the k-th element. Alternatively, we can use the quickselect algorithm to find the k-th largest integer.

The time complexity is O(n times log n) or O(n), where n is the length of the nums array. The space complexity is O(log n) or O(1).

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Sort and Pick Approach

Time Complexity: O(n log n) due to sorting, where n is the number of elements in nums.
Space Complexity: O(1) excluding the space required for sorting.

Min-Heap (Priority Queue) Approach

Time Complexity: O(n log k), where n is the number of elements in nums.
Space Complexity: O(k), due to the heap storing k elements.

Sorting or Quickselect—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Sort and PickO(n log n)O(1)–O(n)Best when simplicity matters and full sorting cost is acceptable
Min-Heap (Priority Queue)O(n log k)O(k)Efficient when k is small compared to n
QuickselectAverage O(n), Worst O(n²)O(1)Useful when you only need the kth element without sorting the entire array

Video Solution

Find the Kth Largest Integer in the Array - Leetcode Weekly Contest - 1985 Python • NeetCode • 15,570 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Find the Kth Largest Integer in the Array easy or hard?
Find the Kth Largest Integer in the Array is classified as a Medium problem. The main challenge comes from handling numbers stored as strings and choosing an efficient selection method such as a heap or Quickselect instead of brute-force comparisons.
Find the Kth Largest Integer in the Array Python/Java solution
In Python, the problem can be solved using sorting with a custom key based on string length and lexicographic order, or by maintaining a heap using heapq. In Java, you can use Arrays.sort with a comparator or a PriorityQueue to maintain the top k elements.
How to solve Find the Kth Largest Integer in the Array in O(n)?
An average O(n) solution uses the Quickselect algorithm. The array is partitioned around a pivot, similar to quicksort, and only the side containing the kth largest element is processed recursively. Comparisons must be done using string length first and lexicographic order for equal lengths.
What is the best approach for Find the Kth Largest Integer in the Array?
The min-heap (priority queue) approach is typically the best balance between simplicity and efficiency. It keeps only the k largest elements in a heap of size k while iterating through the array. This results in O(n log k) time complexity and O(k) space, which is more efficient than sorting when k is much smaller than n.
Is Find the Kth Largest Integer in the Array asked at Google/Amazon/Meta?
Kth element and top‑k style problems frequently appear in interviews at companies like Amazon, Google, and Meta. Variants involving heaps, Quickselect, or sorting are common because they test understanding of selection algorithms and data structures such as priority queues.
What data structure is used in Find the Kth Largest Integer in the Array?
The most common data structure used is a min-heap (priority queue). It maintains the k largest elements seen so far while scanning the array. Sorting algorithms and Quickselect also rely on array manipulation and custom comparison logic for numeric strings.
What is the time complexity of Find the Kth Largest Integer in the Array?
Time complexity depends on the chosen algorithm. Sorting the array takes O(n log n). A min-heap solution improves this to O(n log k). A Quickselect-based selection algorithm can achieve average O(n) time but may degrade to O(n²) in the worst case.

Ready to solve this problem?

Practice Find the Kth Largest Integer in the Array with our built-in code editor and test cases.

Practice on FleetCode
Previous

Kth Largest Element in an Array