Given an integer array nums and an integer k, return the kth largest element in the array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

Function Signature:

from typing import List

def find_kth_largest(nums: List[int], k: int) -> int:
    """
    Find the kth largest element in the array.

    Parameters:
    - nums: A list of integers.
    - k: An integer representing the position of the largest element to find.

    Returns:
    - int: The kth largest element in the array.
    """
    # Your code here

Example:

result = find_kth_largest([3, 2, 1, 5, 6, 4], 2)
print(result)  # Output: 5
# Explanation: The 2nd largest element is 5.

result = find_kth_largest([3, 2, 3, 1, 2, 4, 5, 5, 6], 4)
print(result)  # Output: 4
# Explanation: The 4th largest element is 4.

Note:

  • You may assume k is always valid, 1 <= k <= len(nums).

Instructions:

  • Write the find_kth_largest function to solve the problem.
  • Implement your solution in Python.
  • Provide clear comments in your code.
  • Discuss the time and space complexity of your solution.

As always, we’ll share our solution to this problem tomorrow. Stay tuned 😊