Find k-th largest element in array

Q: Find k-th largest element in array

This question evaluates array manipulation, selection algorithms, in-place partitioning techniques, and complexity analysis within the domain of coding and algorithms.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

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:

Describe the algorithm you would use to find the k-th largest element, ideally using an in-place partitioning approach inspired by quicksort.
Write the core logic in code (in the language of your choice).
Analyze the average-case time complexity and space complexity of your algorithm, and briefly explain why the average-case complexity holds.

Find k-th largest element in array

Overview

Comments (0)