Find The Kth Largest Integer In The Array - Leetcode Solution

Problem Statement:

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

Note that the kth largest integer in the array is unique.

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

Solution:

To find the kth largest integer in the given array of integers, we can use a min-heap. We can create a max-heap of size k and then traverse through the given array. For each element in the array, we will check if it is greater than the smallest element in the max-heap. If it is greater than the smallest element in the max-heap, then we will remove the smallest element from the max-heap and add the current element to the max-heap.

At the end of the traversal, the kth largest integer will be the top element of the max-heap.

Steps to find the kth largest integer in the array:

1. Create a max-heap of size k.
2. Traverse through the given array.
3. Check if the current element is greater than the smallest element in the max-heap.
4. If it is greater than the smallest element in the max-heap, then remove the smallest element from the max-heap and add the current element to the max-heap.
5. At the end of the traversal, the top element of the max-heap will be the kth largest integer in the array.

Implementation:

To implement the above approach, we can use the built-in Python module heapq to create a max-heap of size k.

Here is the Python code for the solution:

import heapq

def findKthLargest(nums, k): heap = [] for num in nums: if len(heap) < k: heapq.heappush(heap, num) else: if num > heap[0]: heapq.heappushpop(heap, num) return heap[0]

nums = [3, 2, 1, 5, 6, 4] k = 2 print(findKthLargest(nums, k)) # Output: 5

nums = [3, 2, 3, 1, 2, 4, 5, 5, 6] k = 4 print(findKthLargest(nums, k)) # Output: 4

Time Complexity: O(nlogk)

In our solution, we are traversing through the given array of integers once and for each element in the array, we are performing push and pop operations on the_heap_, which takes logarithmic time. Therefore, the time complexity of the algorithm is O(nlogk), where n is the length of the given array and k is the size of the max-heap.

1