1 day ago6 min read

215. Kth Largest Element in an Array - LeetCode Fastest Solution

Hello Code Recipian! In this we will solve LeetCode problem 215. Kth Largest Element in an Array using the heap data structure. This article is part of our LeetCode problem solutions series—be sure to explore the rest of the series once you’ve finished reading this one!

Brace yourself—it's time to tackle the problem statement!

Problem Statement: Kth Largest Element in an Array

Given an array of integers nums and an integer k, return the kth largest element in the array.

Note: You have to return the kth largest element in the sorted order, not kth distinct element.

Example 1:

Input: nums = [3, 2, 1, 5, 6, 4], k = 2

Output: 5

Example 2:

Input: nums = [3,2,3,1,2,4,5,5,6], k = 4 Output: 4

Constraints:

1 <= k <= nums.length <= 10^5
-10^4 <= nums[i] <= 10^4

Solution

This problem is classified as medium difficulty on LeetCode. While it can be easily solved using a sorting-based approach, the time complexity of this solution is O(n log n).

We can achieve a better time complexity using the max heap data structure. Since the max heap data structure maintains the largest elements at the top, the idea is to build a max heap using the given array and if we extract k elements from max heap we will get the kth largest element.

Many programming languages offer built-in heap libraries that can be easily imported and used in our code. However, in this solution, we will implement our own heap. Doing so will deepen our understanding of both the problem and the heap data structure, while also enhancing our preparation for coding interviews.

What is a Max Heap?

A max heap data structure is a binary tree, in which value of the parent node is always greater than that of its children and this property applies for all nodes in the tree. This property of max heap ensures that the largest element is always at the root.

Heap Representation using an Array

A heap can be efficiently represented using an array:

Root of the heap is at index 0.
For a node at index i:
- The left child is located at index 2 * i + 1 in the array.
- The right child is located at index 2 * i + 2.
- Parent is located at index (i-1)/2.

For example the max heap given below:

can be represented in array form as:

[10, 7, 8, 5, 6, 3, 4]

This simplifies heap operations as we can directly calculate parent, child indices using formulas.

Quick Glance: Heap Operations

Heapify Down:
Heapify down ensures that the heap property is maintained/restored, after we delete or modify elements in a max heap. Given the index of the node, heapify down pushes a node down to its correct position in the heap.
Extract or Delete:
In a heap, extraction/deletion is always performed on the root node.. In order to extract a value from heap:
1. First copy the root value to be deleted into a temporary variable.
2. Copy the value of the bottom-rightmost node (last node) into the root node.
3. Finally, heapify down the newly copied root value to restore the heap property.

Algorithm

Here is a detailed explanation of how the algorithm works:

Initialization:
Get the length of nums array and store it in a variable, let's call it n.
Build max heap from array: Next, we convert the given nums array into a max heap. We do this by repeatedly calling heapify down on every node value in nums. As a slight optimization, we can call heapify down only non-leaf nodes (since leaf nodes does not have children, heapify down does not make sense for a leaf node). For an array represented as a heap, the (n/2 - 1)th element points to the last non-leaf node.
Heapify down function:
The job of the heapify function in a max heap is to compare the parent node value with the maximum of left and right child value, and push it down the heap if needed to its correct position to maintain the heap property.
1. The heapifyDown function takes 3 arguments:
  1. nums array.
  2. i the index of the node which needs to be heapified.
  3. n length of nums array.
2. Initially, we assume the current index i to be the index which has the largest value, let's call this index variable largestIdx.
3. Calculate left and right child indices using the formulas described earlier. Let's call this leftChildIdx and rightChildIdx.
4. Find the largest of left and right child and compare it with the parent.
  1. If max(left child, right child) > parent, then we swap it with the parent. Assign largestIdx as the current index i (for next iteration).
  2. If max(left child, right child) <= parent, it means current element at index i is already in its correct position in max heap. Therefore, we stop and come out of the heapify function.
5. Repeat steps b to d until the required element is pushed down to its correct position in heap.
Extract heap elements:
At this point we have the nums array converted to a max heap. Now extract k-1 elements from heap. To extract an element from max heap, perform the following steps:
1. Copy the last heap element to the root.
2. Either remove the last element from nums or simply decrement n.
3. Call heapify down function for index 0 (to place the element copied to root in in its correct position in heap).
4. Repeat steps a to c, k-1 times.
Return final result: Now that we have extracted k-1 elements, the kth largest element is at the root of the heap (0th index in array). Therefore return the 0th index as result.

Simulation

Here is a visual representation of how the algorithm works:

Above diagram shows how heapifyDown systematically pushes a particular element down the tree (observe the nodes marked with green) to restore/maintain max heap property.

Want to master coding? Looking to upskill and crack interviews? We suggest you check out

these specially designed courses:

Code

Go Solution

Python Solution

Java Solution

JavaScript Solution

TypeScript Solution

C++ Solution

C# Solution

C Solution

PHP Solution

Kotlin Solution

Swift Solution

Ruby Solution

Scala Solution

Rust Solution

Complexity Analysis

Time Complexity

Building the max heap:

For building the max heap, we call heapifyDown on all non-leaf nodes. Each call to heapifyDown takes O(log n) time. In a binary tree there can be approximately n/2 non-leaf nodes.

From the above analysis, it might appear that the time for building the heap is O(n/2 log n) or O(n log n). However in reality it takes an overall linear time to build a heap.

The intuition is that, even though a single heapify might take O(log n) time, the number of operations required decreases drastically as we move up the tree, leading to an overall linear time.

At lower levels the heapify operation is cheaper (because nodes at lower level have less children below them) but applied more often (because we start heapify from the bottom of the tree).

At higher levels the heapify operation is more expensive (because nodes at higher level have more nodes below them) but applied less often (since we start heapify from bottom of the tree, the initial heapify calls would have already put the nodes at its correct position by the time heapify reaches higher level nodes).

Therefore time complexity for building a heap from an array is O(n).

Extracting k elements from max heap:

The algorithm extracts k elements from heap for finding the kth largest element. Each extract operation makes a call to heapifyDown which have a O(log n) time complexity. Hence the time complexity for this step is O(k log n).

Overall time complexity:

Combining the above two points, the overall time complexity of this algorithm is O(n) + O(k log n) = O(n + k log n).

Space Complexity

The algorithm operates in place and uses only a constant amount of extra space. Therefore, the space complexity is O(1).

That concludes this article. We truly appreciate the time you've spent reading it. If you have any questions, feel free to leave them in the comments below. We're happy to assist and will gladly respond to your queries.

If you found this article helpful, consider subscribing to our website and Youtube channel. Your support motivates us to create more insightful articles in the future.

Limited Time Offer from Code Recipe: Enjoy a 100% discount on the Code Recipe Membership Plan. Sign up now to access exclusive premium content for free. Act fast—this offer is only available for a limited time - Join now. Follow us: YouTube, Facebook, Twitter, LinkedIn, Tumblr, Instagram.