Kth Largest Element In An Array - Leetcode Solution

Problem:

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.

Solution:

This problem can be solved in multiple ways, some of the most common ones are:

1. Sorting: Sort the array in descending order and return the kth element.

2. Min Heap: Create a min heap of size k, iterate through the array and add each element to the heap. If the heap size exceeds k, remove the smallest element from the heap. The kth largest element will be the root of the heap.

3. Quick Select Algorithm: This is a modified version of Quick Sort algorithm where we only partition those elements that we care about i.e. the (n-k)th to n-1th elements where n is the length of the array. The pivot element after each partition gives us an idea about the position of the kth largest element. If the pivot element is at index n-k, we have found our answer.

In this solution, we will use the Quick Select Algorithm to solve this problem.

Algorithm:

1. Define a function partition that takes an array, a start index and an end index as input and returns the pivot index after partitioning the array.

   • Set the pivot index to the start index and the pivot value to the last element of the array.
   • Initialize the left index to the start index and the right index to the end index - 1.
   • Loop until the left index is less than or equal to the right index:
     • If the value at index left is less than or equal to the pivot value, increment left.
     • If the value at index right is greater than or equal to the pivot value, decrement right.
     • If the value at index left is greater than the pivot value and the value at index right is less than the pivot value, swap the values at indexes left and right.
   • Swap the pivot value with the value at index left.
   • Return the left index.

2. Define a function quickSelect that takes an array, a start index, an end index, and a k value as input and returns the kth largest element in the array.

   • If the start index is equal to the end index, return the value at index start.
   • Call the partition function with the array, start index, and end index, and store the result in a variable pivotIndex.
   • If the pivotIndex is equal to n - k, return the value at index pivotIndex.
   • If the pivotIndex is less than n - k, call the quickSelect function recursively on the right half of the array with the start index set to pivotIndex + 1.
   • If the pivotIndex is greater than n - k, call the quickSelect function recursively on the left half of the array with the end index set to pivotIndex - 1.

3. Call the quickSelect function with the input array, start index set to 0, end index set to the length of the array - 1, and k value set to the input k.

4. Return the result of the quickSelect function.

Time Complexity:

On average, the time complexity of this algorithm is O(n) where n is the length of the input array. However, in worst-case scenarios, the time complexity can be O(n^2) when the array is sorted in ascending or descending order.

Space Complexity:

The space complexity of this algorithm is O(1) as we are not using any extra data structures.

Code:

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        
        def partition(nums, start, end):
            pivotIndex = start
            pivotValue = nums[end]
            leftIndex = start
            rightIndex = end - 1
            
            while leftIndex <= rightIndex:
                if nums[leftIndex] <= pivotValue:
                    leftIndex += 1
                elif nums[rightIndex] >= pivotValue:
                    rightIndex -= 1
                elif nums[leftIndex] > pivotValue and nums[rightIndex] < pivotValue:
                    nums[leftIndex], nums[rightIndex] = nums[rightIndex], nums[leftIndex]
                    leftIndex += 1
                    rightIndex -= 1
                    
            nums[leftIndex], nums[end] = nums[end], nums[leftIndex]
            
            return leftIndex
        
        def quickSelect(nums, start, end, k):
            if start == end:
                return nums[start]
            
            pivotIndex = partition(nums, start, end)
            
            if pivotIndex == len(nums) - k:
                return nums[pivotIndex]
            elif pivotIndex < len(nums) - k:
                return quickSelect(nums, pivotIndex + 1, end, k)
            else:
                return quickSelect(nums, start, pivotIndex - 1, k)
        
        return quickSelect(nums, 0, len(nums) - 1, k)

1