Find k-th largest element in array

You are given an unsorted array of integers nums and a positive integer k.

Design an efficient algorithm to find the k-th largest element in the array. The k-th largest element is the element that would appear in position len(nums) - k if the array were sorted in non-decreasing order.

• Example:
  • Input: nums = [3, 2, 1, 5, 6, 4], k = 2
  • Output: 5 (the sorted array is [1, 2, 3, 4, 5, 6], so the 2nd largest is 5)

Assumptions and requirements:

• 1 <= k <= len(nums).
• The array may contain duplicate values.
• Aim for an algorithm with good average-case time complexity (better than fully sorting the array if possible).

Tasks:

1. Describe the algorithm you would use to find the k-th largest element, ideally using an in-place partitioning approach inspired by quicksort.
2. Write the core logic in code (in the language of your choice).
3. Analyze the average-case time complexity and space complexity of your algorithm, and briefly explain why the average-case complexity holds.

Find K-th Largest Element in an Array

You are given an unsorted array of integers nums and a positive integer k. Return the k-th largest element in the array, where duplicates count as separate elements. In other words, if the array were sorted in non-decreasing order, you should return the value at index len(nums) - k.

You should aim for an efficient algorithm using an in-place partitioning strategy inspired by quicksort (Quickselect), rather than fully sorting the array.

Constraints

• 1 <= len(nums) <= 100000
• -1000000000 <= nums[i] <= 1000000000
• 1 <= k <= len(nums)
• The array may contain duplicate values

Hints

1. The k-th largest element is the same as the element at index len(nums) - k in the array sorted in ascending order.
2. Use a partition step like quicksort: place one pivot in its final sorted position, then continue only on the side that contains the target index.