Kth Largest Element in an Array - Practice Coding Problems

Kth Largest Element in an Array - Problem

Given an integer array nums and an integer k, return the k-th largest element in the array.

Note that it is the k-th largest element in the sorted order, not the k-th distinct element.

Can you solve it without sorting?

Input & Output

Example 1 — Basic Case

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

› Output: 5

💡 Note: The array sorted in descending order is [6,5,4,3,2,1]. The 2nd largest element is 5.

Example 2 — Different K

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

› Output: 4

💡 Note: The sorted array is [6,5,5,4,3,3,2,2,1]. The 4th largest element is 4.

Example 3 — Minimum Size

$ Input: nums = [1], k = 1

› Output: 1

💡 Note: There's only one element, so the 1st largest is 1.

Constraints

1 ≤ k ≤ nums.length ≤ 10⁵
-10⁴ ≤ nums[i] ≤ 10⁴

Visualization

Tap to expand

Understanding the Visualization

Input

Array [3,2,1,5,6,4] and k=2

Find Position

Use partitioning to locate 2nd largest position

Output

Return the element at k-th largest position: 5

Key Takeaway

🎯 Key Insight: Use partitioning techniques like Quickselect to find the k-th element in O(n) average time instead of O(n log n) sorting

Asked in

f Facebook 65 a Amazon 58 in LinkedIn 42 🍎 Apple 38 G Google 35

The key insight is that we don't need to sort the entire array - we only need to find the k-th position. The optimal approach is Quickselect with average O(n) time complexity, though a min-heap approach with O(n log k) is also efficient when k is small. Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Quickselect Algorithm	O(n)	O(1)	Use partition-based selection to find k-th largest in average O(n) time
Min-Heap Approach	O(n log k)	O(k)	Use a min-heap of size k to track the k largest elements
Sort and Index	O(n log n)	O(1)	Sort the entire array and return the k-th largest element

Quickselect Algorithm — Algorithm Steps

Choose a pivot and partition array
If pivot is at position k-1, return it
If pivot > k-1, search left partition
If pivot < k-1, search right partition

Visualization

Tap to expand

Step-by-Step Walkthrough

Choose Pivot

Pick a random element as pivot and partition

Partition

Move larger elements left, smaller right

Recurse

Search only the side containing k-th position

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

int partition(int* nums, int left, int right, int pivotIdx) {
    int pivot = nums[pivotIdx];
    swap(&nums[pivotIdx], &nums[right]);
    
    int storeIdx = left;
    for (int i = left; i < right; i++) {
        if (nums[i] > pivot) {
            swap(&nums[storeIdx], &nums[i]);
            storeIdx++;
        }
    }
    
    swap(&nums[right], &nums[storeIdx]);
    return storeIdx;
}

int quickselect(int* nums, int left, int right, int kSmallest) {
    if (left == right) {
        return nums[left];
    }
    
    int pivotIdx = left + rand() % (right - left + 1);
    pivotIdx = partition(nums, left, right, pivotIdx);
    
    if (kSmallest == pivotIdx) {
        return nums[kSmallest];
    } else if (kSmallest < pivotIdx) {
        return quickselect(nums, left, pivotIdx - 1, kSmallest);
    } else {
        return quickselect(nums, pivotIdx + 1, right, kSmallest);
    }
}

int solution(int* nums, int numsSize, int k) {
    srand(time(NULL));
    return quickselect(nums, 0, numsSize - 1, k - 1);
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array
    int nums[10000];
    int numsSize = 0;
    char* token = strtok(line, "[,]\n");
    while(token != NULL) {
        if(strlen(token) > 0 && token[0] != '[' && token[0] != ']') {
            nums[numsSize++] = atoi(token);
        }
        token = strtok(NULL, "[,]\n");
    }
    
    int k;
    scanf("%d", &k);
    
    int result = solution(nums, numsSize, k);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Average case partitions reduce problem size by half each time, giving O(n + n/2 + n/4 + ...) = O(n)

✓ Linear Growth

Space Complexity

O(1)

Uses constant extra space, partitions array in-place

✓ Linear Space

78.0K Views

High Frequency

~15 min Avg. Time

1.9K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Quickselect Algorithm — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler