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.