Kth Largest Element in an Array
title: Kth Largest Element in an Array tags: sort heap
Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.
Example 1:
Input: [3,2,1,5,6,4] and k = 2
Output: 5
Example 2:
Input: [3,2,3,1,2,4,5,5,6] and k = 4
Output: 4
Note: You may assume k is always valid, 1 ≤ k ≤ array’s length.
If the input is sorted:
1,2,3,4,5,6
We can access the element in O(1) time. O(1) time to access the kth largest element if we store it in min heap.
Solution Outline
 Create a min heap of size k (k is the invariant)
 Traverse through the input list and add the elements which are greater than the min element to the heap
 Extract the min element from the heap and return as the result.
[3,2,1,5,6,4]
 Create a max heap of size = k
 Traverse through the nums array
 Add first k elements into the heap
3
2
 1 < 3 skip the element
 5 > 3
We need a min heap so the minimum value gets kicked out to make room for the larger number.
Create a min heap of size = k
Traverse through the nums array
Add first k elements into the heap
2
3
 1 < 3 skip the element 1
 5 > 3
Add 5 to the heap
3
5
 6 > 5
Add 6 to the heap
5
6
 4 < 6 skip the element 4
Extract the first element in the heap. This is the kth largest element.




Tracing of the program:
n : 2
i: 0
Before insert: [3]
After insert: [2, 3]
Maintain k elements: [2, 3]
n : 1
i: 0
Before insert: [2, 3]
After insert: [1, 2, 3]
Maintain k elements: [2, 3]
n : 5
i: 2
Before insert: [2, 3]
After insert: [2, 3, 5]
Maintain k elements: [3, 5]
n : 6
i: 2
Before insert: [3, 5]
After insert: [3, 5, 6]
Maintain k elements: [5, 6]
n : 4
i: 0
Before insert: [5, 6]
After insert: [4, 5, 6]
Maintain k elements: [5, 6]
5
Define the Interface
Input: nums (array of integers), k (integer) Output: integer
Analyze the Input and Output
 The input is not sorted.
 The value of k must be between [1, nums.size]
 Duplicate numbers can be in the input
Identify the constraints
1. 1 <= k <= nums.length <= 10^4
2. 10^4 <= nums[i] <= 10^4
Search the Problem Space
 kth largest element => Heap
Solve the Problem by Hand
nums = [3,2,1,5,6,4], k = 2
If the input is in ascending order: [1,2,3,4,5,6], grab the kth largest element by looking from the end of the array.
Time: O(n log n) Space: O(1) This WRONG
Sorting algorithms can use extra space. O(N).
Analyze Time and Space Complexity
Sorting and accessing the kth element from the array.
Solution Outline
 Max heap
We will keep the largest at the top. You can get the largest number in O(1) time.
6 5
 Min heap
5 6
[3,2,1,5,6,4]
 Create a max heap of size = k
 Traverse through the nums array
 Add first k elements into the heap
3 2
 1 < 3 skip the element
 5 > 3
We need a min heap so the minimum value gets kicked out to make room for the larger number.
 Create a min heap of size = k
 Traverse through the nums array
 Add first k elements into the heap
2 3
 1 < 3 skip the element 1
 5 > 3
Add 5 to the heap
3 5
 6 > 5
Add 6 to the heap
5 6
 4 < 6 skip the element 4
We will create a heap of size = k.
T: O(n log k) S: O(k)
```ruby
# @param {Integer[]} nums
# @param {Integer} k
# @return {Integer}
def find_kth_largest(nums, k)
min_heap = [nums[0]]
nums[1..1].each do n
i = min_heap.bsearch_index{y y >= n }  min_heap.size
min_heap.insert(i, n)
# heap size is always = k
if min_heap.size > k
min_heap.shift
end
end
min_heap.first
end
Define the Terms
Define the Interface Input: nums (array of integers), k (integer) Output: integer
Analyze the Input and Output
The input is not sorted. The value of k must be between [1, nums.size] Duplicate numbers can be in the input
Identify the Invariants
Identify the constraints
 1 <= k <= nums.length <= 104
 104 <= nums[i] <= 104
Search the Problem Space
 kth largest element => Heap
Classify the Problem
Analyze the Examples
Solve the Problem by Hand
nums = [3,2,1,5,6,4], k = 2
Input in ascending order: [1,2,3,4,5,6] Grab the kth largest element by looking from the end of the array.
Time: O(n log n) Space: O(1) This WRONG
Sorting algorithm can use extra space. O(N).
Describe the Pattern
Distill the Observations to Create Insights
Brute Force Approach
Analyze Time and Space Complexity
Sorting and accessing the kth element from the array.
Outline the Solution
Max heap We will keep the largest at the top. You can get largest number in O(1) time.
6 5
Min heap
5 6
[3,2,1,5,6,4]
Create a max heap of size = k Traverse through the nums array
 Add first k elements into the heap
3 2
 1 < 3 skip the element
 5 > 3
We need a min heap so the minimum value gets kicked out to make room for the larger number.
Create a min heap of size = k Traverse through the nums array
 Add first k elements into the heap
2 3
1 < 3 skip the element 1
5 > 3 Add 5 to the heap
3 5
 6 > 5
Add 6 to the heap
5
6
 4 < 6 skip the element 4
We will create a heap of size = k.
Key Takeaways


To find the kth largest element without sorting the array, you can utilize the heap data structure. A minheap will be perfect for this problem.
Here’s the idea:
 Create a minheap and insert the first k elements from the array into the heap.
 Iterate through the remaining elements in the array. For each element, compare it with the smallest element in the heap (the root of the minheap).
 If the current element is larger than the root of the heap, pop the root from the heap and insert the current element.
 The root of the heap will always contain the kth largest element since we are maintaining only k elements in the heap at any time.
Here’s a Python code snippet to illustrate this solution:


This code snippet uses a minheap to store the largest k elements seen so far. By the end of the loop, the heap will contain the k largest elements, and the root will contain the kth largest element, which is the result.
Key takeaways:
 Minheap is used to keep track of the k largest elements.
 The complexity of this solution is O(n log k) where n is the length of the input array, and k is the value provided as input. It avoids sorting the entire array, which would be O(n log n).
Identifying Problem Isomorphism
“Find K Pairs with Smallest Sums” is an approximate isomorphism for “Kth Largest Element in an Array”. Both involve dealing with a ‘k’ parameter and require knowledge of sorting and heap data structures.
In “Kth Largest Element in an Array”, you need to find the kth largest element in an unsorted array. This might involve sorting the array or using a heap to efficiently find the kth largest element.
In “Find K Pairs with Smallest Sums”, you are given two integer arrays nums1 and nums2, and you are supposed to find the k pairs (u, v), where u is in nums1 and v is in nums2, that they have the smallest sums. This problem is more complex than the “Kth Largest Element in an Array” as you need to consider pairs of elements, not individual ones, and work with two separate arrays. It’s also likely to involve using a minheap to keep track of the pairs with the smallest sums.
“Kth Largest Element in an Array” is simpler because you only need to focus on finding the kth largest element in one array, while “Find K Pairs with Smallest Sums” involves dealing with two arrays and finding pairs, which increases complexity.


Problem Classification
The problem can be classified as follows:
Sorting/Ranking: The problem is about finding the kth largest element, which essentially involves sorting or ranking elements in a particular order (descending in this case). The term “kth largest” implies an ordering of the elements.
Array Manipulation: The given data structure in this problem is an array. Manipulation and analysis of this array is required to solve the problem.
Selection: The task involves selecting a specific element (the kth largest one) from the array, which can be classified as a selection problem.
Parameterized Complexity: The complexity of the problem depends on an external parameter (k), apart from the size of the input array.
Search: This problem involves searching for a particular element in the array (the kth largest), which fits into the search problem category.
The actual solution may involve different algorithmic techniques like QuickSelect (variation of QuickSort), heap data structure, or sorting, but these are implementation details.
Language Agnostic Coding Drills
Conditional Checks: Checking for conditions to validate inputs or variables. For example, checking if a list is empty or if a variable meets a certain criteria.
List Operations: Creating lists and adding elements to lists.
Loops: Iterating over a list using a for loop.
Heap Operations: Using a heap data structure, adding elements to a heap, and retrieving elements from a heap. In Python, the heapq module is often used for this purpose.
Negation Operation: Using negative numbers to switch between min heap and max heap in Python’s heapq module which supports min heap natively.
Returning Values from Functions: Returning a result from a function.
Organized by increasing level of difficulty, they can be presented as follows:
 Conditional Checks: Understand how to use conditional checks to validate input data or to control program flow.
 List Operations: Learn to create lists, add elements to lists, and access list elements.
 Loops: Master the usage of for loops to iterate over a list.
 Returning Values from Functions: Learn how to return a result from a function.
 Negation Operation: Understand the usage of negation operation in the context of transforming max heap to min heap.
 Heap Operations: Understand the concept of heap, and learn how to use heap operations like push and pop.
The concepts learned from these smaller units can then be combined to solve the larger problem presented in the code: finding the kth largest element in a list.
Targeted Drills in Python
Conditional Checks
Goal: Write a function that checks if a list is empty or not. The function should return
True
if the list is empty andFalse
otherwise.1 2 3 4 5
def is_empty(lst): # your code here print(is_empty([])) # should return True print(is_empty([1, 2, 3])) # should return False
List Operations
Goal: Create a list and add elements to it. Print the list before and after adding elements.
1 2
my_list = [] # your code here to add elements to the list
Loops
Goal: Write a function that accepts a list of numbers and prints each number in the list.
1 2 3 4
def print_numbers(lst): # your code here print_numbers([1, 2, 3, 4, 5]) # should print each number
Returning Values from Functions
Goal: Write a function that returns the square of a number.
1 2 3 4
def square(n): # your code here print(square(5)) # should print 25
Negation Operation
Goal: Write a function that accepts a list of numbers and returns a new list with each number negated.
1 2 3 4
def negate_list(lst): # your code here print(negate_list([1, 2, 3])) # should print [1, 2, 3]
Heap Operations
Goal: Create a min heap using
heapq
module in Python, add some numbers to it, and print the smallest number without popping it.1 2 3 4
import heapq heap = [] # your code here to add numbers and print the smallest one
After practicing each of these drills, you should have a deeper understanding of the various concepts embedded within the code sample. Each of these drills isolates a particular concept, allowing you to focus on understanding and mastering it. Once you are comfortable with these concepts, you can then combine them as demonstrated in the initial code sample.