215. Kth Largest Element in an Array

Problem¶

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

Note that it is the kth largest element in the sorted order, not the kth 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

Solve¶

Quick select - similarity to quick sort¶

Using same ideal of quick sort, we chose a target, split the nums array to 3 subarray base on the comparing result of target and nums[i], which is

[smaller] [equal] [bigger]

To find any k‘th largest position, we select in the range that k in, which mean:

k in [bigger] sub array If k <= len(bigger)
k in [equal] sub array If len(bigger) < k <= len(bigger) + len(equal)
k in [smaller] sub array If len(bigger) + len(equal) < k

Base on where k is, we narrow down the finding process. Stop if k in [equal] sub array and return target.

By randomly chose the target, we effectively preventing bad input (already sorted) array.

Time Submitted	Status	Runtime	Memory	Language
08/14/2023 14:59	Accepted	6347 ms	29.7 MB	python3
08/14/2023 14:58	Accepted	2348 ms	30 MB	python3

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        remain = nums.copy()
        pos = k
        while len(remain) > 0:
            target = remain[randrange(0, len(remain))]
            # target = remain[0]
            bigger = []
            equad = []
            i = 0
            while i < len(remain):
                if remain[i] > target:
                    bigger.append(remain.pop(i))
                elif remain[i] == target:
                    equad.append(remain.pop(i))
                else:
                    i += 1
            # print(remain, equad, bigger, pos)
            if  pos <= len(equad) + len(bigger):
                if pos <= len(bigger):
                    remain = bigger
                else:
                    return target
            else:
                pos = pos - len(bigger) - len(equad)
        return 0

Sorting - Counting sort¶

Counting sort could give the best way to sort a low range of number value (`-104 <= nums[i] <= 104)

Base on sort result, we can easily get the k’th largest result

Time Submitted	Status	Runtime	Memory	Language
08/14/2023 15:32	Accepted	403 ms	29.5 MB	python3

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        count = [0] * 20001
        for n in nums:
            count[n + 10000] += 1
        pos = 0
        for `-1]`:
            pos += c
            if pos >= k:
                return 10000 - i
        return 0

There isn’t negative for array value, while you can use dict, it quite slower.

`c` implementation¶

While I hate how you [[pass around variable|pass around variable]] in c language, and how hard it is to set up a proper project folder.

This is me trying to implement the quick select solution. But we don’t want to implement Vector like (Using Linked list) or hard code allocating [0..10**5] length array like python code, I try implement O(1) memory space solution

Final file: https://github.com/ylsama/leetcode/blob/main/215/c/src/main.c

Quick sort¶

To implement quick select, it is likely require you to know how to implement quicksort algorithms. By sorting, we can just then return the k'th largest value to finish the problem.

Time Submitted	Status	Runtime	Memory	Language
08/14/2023 20:03	Accepted	210 ms	11.2 MB	c

void swap(int *x, int *y) {
  int tmp = *x;
  *x = *y;
  *y = tmp;
}

int partition(int *nums, int low, int high) {
  int pivot = nums[high];
  int i = (low - 1);

  for (int j = low; j <= high - 1; j++) {
    if (nums[j] <= pivot) {
      i++;
      swap(&nums[i], &nums[j]);
    }
  }
  swap(&nums[i + 1], &nums[high]);
  return (i + 1);
}

void quicksort(int *nums, int low, int high) {
  if (low < high) {
    int pivotIndex = partition(nums, low, high);
    quicksort(nums, low, pivotIndex - 1);
    quicksort(nums, pivotIndex + 1, high);
  }
}

int findKthLargest(int *nums, int numsSize, int k) {
  quicksort(nums, 0, numsSize - 1);
  return nums[numsSize - k];
}

Quick select¶

Quick select in O(1) space is just us effectively sort the nums array only in needed part.

Time Submitted	Status	Runtime	Memory	Language
08/14/2023 19:47	Accepted	91 ms	11.5 MB	c

void swap(int *x, int *y) {
  int tmp = *x;
  *x = *y;
  *y = tmp;
}

int partition(int *nums, int low, int high) {
  int pivot = nums[high];
  int i = (low - 1);

  for (int j = low; j <= high - 1; j++) {
    if (nums[j] <= pivot) {
      i++;
      swap(&nums[i], &nums[j]);
    }
  }
  swap(&nums[i + 1], &nums[high]);
  return (i + 1);
}

int quickSellect(int *nums, int low, int high, int pos) {
  if (low < high) {
    int pivotIndex = partition(nums, low, high);
    if (pivotIndex == pos) {
      return nums[pivotIndex];
    } else if (pivotIndex > pos) {
      return quickSellect(nums, low, pivotIndex - 1, pos);
    } else {
      return quickSellect(nums, pivotIndex + 1, high, pos);
    }
  } else if (low == pos) {
      return nums[low];
  }
  return -1;
}

int findKthLargest(int *nums, int numsSize, int k) {
  int res = quickSellect(nums, 0, numsSize - 1, numsSize - k);
  return res;
}

`rust` implementation¶

OOP in rust is quite weird (meaning I mean I haven’t done in it enough), while rust does provide self, it not being used here.

impl Solution {
    fn partition(nums: &mut [i32], low: usize, high: usize) -> usize {
        let pivot = nums[high];
        let mut i = low as isize - 1;

        for j in low..high {
            if nums[j] <= pivot {
                i += 1;
                nums.swap(i as usize, j);
            }
        }
        nums.swap((i + 1) as usize, high);
        (i + 1) as usize
    }

    fn quick_select(nums: &mut [i32], low: usize, high: usize, pos: usize) -> i32 {
        if low < high {
            let pivot_index = Solution::partition(nums, low, high);
            if pivot_index == pos {
                return nums[pivot_index];
            } else if pivot_index > pos {
                return Solution::quick_select(nums, low, pivot_index - 1, pos);
            } else {
                return Solution::quick_select(nums, pivot_index + 1, high, pos);
            }
        } else if low == pos {
            return nums[low];
        }
        -1
    }

    pub fn find_kth_largest(nums: Vec<i32>, k: i32) -> i32 {
        let mut nums_mut = nums.to_vec();
        Solution::quick_select(&mut nums_mut, 0, nums.len() - 1, nums.len() - k as usize)
    }
}

Last update : September 23, 2023
Created : August 16, 2023