Solve classic LeetCode problems
Company: Meta
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Onsite
##### 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/
Quick Answer: This question evaluates proficiency with core data structures and algorithmic techniques including array selection and ordering, string pattern grouping, interval/rectangle merging, and binary search tree range queries.
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)
Solution
from typing import List
import random
def kth_largest(nums: List[int], k: int) -> int:
n = len(nums)
target = n - k
left, right = 0, n - 1
while left <= right:
pivot_index = random.randint(left, right)
pivot_value = nums[pivot_index]
nums[pivot_index], nums[right] = nums[right], nums[pivot_index]
store = left
for i in range(left, right):
if nums[i] < pivot_value:
nums[store], nums[i] = nums[i], nums[store]
store += 1
nums[store], nums[right] = nums[right], nums[store]
if store == target:
return nums[store]
elif store < target:
left = store + 1
else:
right = store - 1
return nums[target]
Explanation
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.
Hints
- Maintain a min-heap of size k to track the k largest elements.
- Alternatively, use Quickselect (Hoare's selection) to achieve average O(n) time.
- Transform k-th largest to (n - k)-th index in ascending order.