Solve classic LeetCode problems

Question

LeetCode 215. Kth Largest Element in an Array LeetCode 249. Group Shifted Strings Variant of LeetCode 56. Merge Intervals extended to 2-D rectangles LeetCode 938. Range Sum of BST

https://leetcode.com/problems/kth-largest-element-in-an-array/description/ https://leetcode.com/problems/group-shifted-strings/description/ https://leetcode.com/problems/merge-intervals/description/ https://leetcode.com/problems/range-sum-of-bst/description/

Kth Largest Element in Array

Given an integer array nums and an integer k (1-indexed), return the k-th largest element in the array. The k-th largest element is the element that would appear at index len(nums) - k if nums were sorted in nondecreasing order. Duplicates count as separate elements.

Constraints

• 1 <= len(nums) <= 200000
• -10^9 <= nums[i] <= 10^9
• 1 <= k <= len(nums)

Examples

Example 1

Input: nums = [3,2,1,5,6,4], k = 2
Output: 5

Explanation: Sorted order is [1,2,3,4,5,6]; the 2nd largest is 5.

Example 2

Input: nums = [3,2,3,1,2,4,5,5,6], k = 4
Output: 4

Explanation: Sorted order is [1,2,2,3,3,4,5,5,6]; the 4th largest is 4.

Hints

1. Maintain a min-heap of size k to track the k largest elements.
2. Alternatively, use Quickselect (Hoare's selection) to achieve average O(n) time.
3. Transform k-th largest to (n - k)-th index in ascending order.

Approach

Quickselect repeatedly partitions the array around a pivot so that elements smaller than the pivot go left and larger go right (ascending partition). The target index for the k-th largest is n - k. After each partition, it narrows the search range to the side containing the target index until the pivot lands exactly at that index.

• Time complexity: O(n) on average; O(n^2) worst-case
• Space complexity: O(1) extra