Kth Largest Element in an Array

LeetCode 215 | Difficulty: Medium

Medium

Problem Description

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?

Example 1:

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

Example 2:

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

Constraints:

- `1 <= k <= nums.length <= 10^5`

- `-10^4 <= nums[i] <= 10^4`

Topics: Array, Divide and Conquer, Sorting, Heap (Priority Queue), Quickselect

---

Approach

Sorting

Sort the input to bring related elements together or enable binary search. Consider: does sorting preserve the answer? What property does sorting give us?

When to use

Grouping, finding closest pairs, interval problems, enabling two-pointer or binary search.

---

Solutions

Solution 1: C# (Best: 135 ms)

Metric	Value
Runtime	135 ms
Memory	38.4 MB
Date	2022-02-14

Solution

public class Solution {
    public int FindKthLargest(int[] nums, int k)
{
    int n = nums.Length;
    k = n-k;
    int start = 0, end = n-1;
    while(start<=end)
    {
        int pivot = partition(nums, start, end);
        if(pivot == k)
        {
            return nums[pivot];
        }
        else if(pivot < k)
        {
            start = pivot+1;
        }
        else
        {
            end = pivot-1;
        }
    }
    return -1;

    }
public int partition(int[] array, int start, int end)
{
    int lo = start, hi = end-1, pivot = end;
    while (lo <= hi)
    {
        if (array[lo] > array[pivot] && array[hi] < array[pivot])
        {
            swap(array, lo, hi);
        }
        if (array[lo] <= array[pivot])
        {
            lo++;
        }
        if (array[hi] >= array[pivot])
        {
            hi--;
        }
    }
    swap(array, lo, pivot);
    return lo;
}

public void swap(int[] array, int l, int r)
{
    int temp = array[l];
    array[l] = array[r];
    array[r] = temp;
}

    }

📜 4 more C# submission(s)

Submission (2019-12-04) — 172 ms, 24.3 MB

public class Solution {
    public int FindKthLargest(int[] nums, int k)
{
    k = nums.Length - k;
    int lo = 0, hi = nums.Length - 1;
    while (lo < hi)
    {       
        int j = partition(nums, lo, hi);
        if (j < k)
            lo = j + 1;
        else if (j > k)
            hi = j - 1;
        else break;
    }
    return nums[k];
}

int partition(int[] nums, int lo, int hi)
{
    int pivot = nums[hi];
    int i = lo;
    for (int j = lo; j < hi; j++)
    {
        if (nums[j] <= pivot)
        {
            swap(nums, i, j);
            i++;
        }
    }
    swap(nums, i, hi);
    return i;
}

    private void swap(int[] nums, int i, int j)
    {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }


}

Submission (2019-12-04) — 176 ms, 24.7 MB

public class Solution {
    public int FindKthLargest(int[] nums, int k)
{
    k = nums.Length - k;
    int lo = 0, hi = nums.Length - 1;
    while (lo < hi)
    {       
        int j = partition(nums, lo, hi);
        if (j < k)
            lo = j + 1;
        else if (j > k)
            hi = j - 1;
        else break;
    }
    return nums[k];
}

int partition(int[] nums, int lo, int hi)
{
    int pivot = nums[hi];
    int i = lo;
    for (int j = lo; j < hi; j++)
    {
        if (nums[j] <= pivot)
        {
            swap(nums, i, j);
            i++;
        }
    }
    swap(nums, i, hi);
    return i;
}

    private void swap(int[] nums, int i, int j)
    {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }


}

Submission (2022-02-14) — 184 ms, 38.3 MB

public class Solution {
    public int FindKthLargest(int[] nums, int k)
{
    int n = nums.Length;
    k = n-k;
    int start = 0, end = n-1;
    while(start<=end)
    {
        int pivot = partition(nums, start, end);
        if(pivot == k)
        {
            return nums[pivot];
        }
        else if(pivot < k)
        {
            start = pivot+1;
        }
        else
        {
            end = pivot-1;
        }
    }
    return -1;

    }
public int partition(int[] array, int start, int end)
{
    int lo = start, hi = end-1, pivot = end;
    while (lo <= hi)
    {
        if (array[lo] > array[pivot] && array[hi] < array[pivot])
        {
            swap(array, lo, hi);
        }
        if (array[lo] <= array[pivot])
        {
            lo++;
        }
        if (array[hi] >= array[pivot])
        {
            hi--;
        }
    }
    swap(array, lo, pivot);
    return lo;
}

public void swap(int[] array, int l, int r)
{
    int temp = array[l];
    array[l] = array[r];
    array[r] = temp;
}

    }

Submission (2017-11-08) — 235 ms, N/A

public class Solution {
   int partition(int[] ar, int lo, int hi)
{
    int i = lo;
    int j = hi + 1;
    int pivot = ar[lo];
    while (true)
    {
        while (ar[++i] < pivot)
            if (i == hi) break;
        while (pivot < ar[--j])
            if (j == lo) break;
        if (i >= j) break;
        swap(ar, i, j);
    }
    swap(ar, lo, j);
    return j;
}

private void swap(int[] ar, int i, int j)
{
    int temp = ar[i];
    ar[i] = ar[j];
    ar[j] = temp;
}

public int FindKthLargest(int[] nums, int k)
{
    k = nums.Length - k;
    int lo = 0, hi = nums.Length - 1;
    while (lo < hi)
    {
        int j = partition(nums, lo, hi);
        if (j < k)
            lo = j + 1;
        else if (j > k)
            hi = j - 1;
        else break;
    }
    return nums[k];
}
}

---

Complexity Analysis

Approach	Time	Space
Sort + Process	$O(n log n)$	$O(1) to O(n)$

---

Interview Tips

Key Points

• Discuss the brute force approach first, then optimize. Explain your thought process.