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.