Welcome to Subscribe On Youtube

215. Kth Largest Element in an Array

Description

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 <= 105
  • -104 <= nums[i] <= 104

Solutions

Solution 1: Sorting

We can sort the array $nums$ in ascending order, and then get $nums[n-k]$.

The time complexity is $O(n \times \log n)$, where $n$ is the length of the array $nums$.

Solution 2: Partition

We notice that it is not always necessary for the entire array to be in an ordered state. We only need local order. That is to say, if the elements in the position $[0..k)$ are sorted in descending order, then we can determine the result. Here we use quick sort.

Quick sort has a characteristic that at the end of each loop, it can be determined that the $partition$ is definitely at the index position it should be. Therefore, based on it, we know whether the result value is in the left array or in the right array, and then sort that array.

The time complexity is $O(n)$, where $n$ is the length of the array $nums$.

Why Swap nums[lo] with nums[r] and Not nums[l]?

The critical reason for using nums[lo], nums[r] = nums[r], nums[lo] instead of nums[lo], nums[l] = nums[l], nums[lo] in the partition method is related to the guarantees provided by the partitioning process about the elements relative to the pivot’s final position.

Understanding the Partition Process:

The partition function’s goal is to rearrange elements in nums[lo:hi+1] such that all elements greater than pivot come before pivot and all elements less than pivot come after it. The final position of pivot is then returned.

  • Pivot Initialization: The pivot is chosen as the first element in the range (nums[lo]).
  • Pointers l and r Movement: The pointers l (initialized to lo+1) and r (initialized to hi) move towards each other. l moves right past elements greater than or equal to pivot because they are correctly placed relative to pivot for a descending sort (since we’re looking for the k-th largest element). Similarly, r moves left past elements less than or equal to pivot.
  • Swapping l and r: If l points to an element less than pivot and r points to an element greater than pivot, they are out of place for the intended descending order, so nums[l] and nums[r] are swapped.

After the while loop terminates, the pointer l has either moved past r or is pointing to an element not less than pivot (due to the condition that increments l), and r is pointing at an element that is less than or equal to pivot (because r decrements when nums[r] <= pivot). Swapping pivot with nums[r] ensures that pivot is placed just before the first element greater than itself encountered from the right. This is the correct final position of pivot in a descending order partitioning since everything to the left of pivot is greater or equal, and everything to the right of pivot is less or equal.

Example Illustration:

Let’s consider an example with nums = [3, 5, 2, 1, 4] and k = 2 (looking for the 2nd largest element).

  • Initial call to partition: pivot = 3, nums = [3, 5, 2, 1, 4].
  • After partitioning: nums could be rearranged to [4, 5, 3, 1, 2] with r pointing to 3.
  • Swapping nums[lo] with nums[r] results in [3, 5, 4, 1, 2], where 3 is correctly placed in its final position for a descending order sorting. The returned index would be where 3 is placed, and since we’re looking for the k-th largest, we adjust lo and hi based on this index.

If you had swapped with nums[l] instead, you could end up placing a number less than pivot in pivot’s initial position, breaking the partitioning invariant, or you might not properly position the pivot relative to all other elements, potentially causing incorrect behavior or infinite loops in the algorithm’s logic.

  • class Solution {
    public int findKthLargest(int[] nums, int k) {
        int n = nums.length;
        return quickSort(nums, 0, n - 1, n - k);
    }

    private int quickSort(int[] nums, int left, int right, int k) {
        if (left == right) {
            return nums[left];
        }
        int i = left - 1, j = right + 1;
        int x = nums[(left + right) >>> 1];
        while (i < j) {
            while (nums[++i] < x)
                ;
            while (nums[--j] > x)
                ;
            if (i < j) {
                int t = nums[i];
                nums[i] = nums[j];
                nums[j] = t;
            }
        }
        if (j < k) {
            return quickSort(nums, j + 1, right, k);
        }
        return quickSort(nums, left, j, k);
    }
}

  • class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        int n = nums.size();
        return quickSort(nums, 0, n - 1, n - k);
    }

    int quickSort(vector<int>& nums, int left, int right, int k) {
        if (left == right) return nums[left];
        int i = left - 1, j = right + 1;
        int x = nums[left + right >> 1];
        while (i < j) {
            while (nums[++i] < x)
                ;
            while (nums[--j] > x)
                ;
            if (i < j) swap(nums[i], nums[j]);
        }
        return j < k ? quickSort(nums, j + 1, right, k) : quickSort(nums, left, j, k);
    }
};

  • class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        lo, hi = 0, len(nums) - 1

        while lo <= hi:
            pos = self.partition(nums, lo, hi)
            if pos == k - 1: # pos starting from 0, so -1
                return nums[pos]  # partially sorted, desc
            elif pos > k - 1:
                hi = pos - 1
            else:  # pos < k - 1
                lo = pos + 1

        return -1  # or raise exception

    def partition(self, nums: List[int], lo: int, hi: int) -> int:
        pivot, l, r = nums[lo], lo + 1, hi
        while l <= r:
            if nums[l] < pivot and nums[r] > pivot:
                # larger num at left of pivot, easier to count for k-th lagest
                nums[l], nums[r] = nums[r], nums[l]
                l += 1
                r -= 1
            if nums[l] >= pivot:
                l += 1
            if nums[r] <= pivot:
                r -= 1
        # use nums[l] will lead to infinate looping
        nums[lo], nums[r] = nums[r], nums[lo]
        # possible there is duplicated num, but will be covered here
        return r

##############

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        def quick_sort(left, right, k):
            if left == right:
                return nums[left]
            i, j = left - 1, right + 1
            x = nums[(left + right) >> 1]
            while i < j:
                while 1:
                    i += 1
                    if nums[i] >= x:
                        break
                while 1:
                    j -= 1
                    if nums[j] <= x:
                        break
                if i < j:
                    nums[i], nums[j] = nums[j], nums[i]
            if j < k:
                return quick_sort(j + 1, right, k)
            return quick_sort(left, j, k)

        n = len(nums)
        return quick_sort(0, n - 1, n - k)

############


class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        def quick_sort(left, right, k):
            if left == right:
                return nums[left]
            i, j = left - 1, right + 1
            x = nums[(left + right) >> 1]
            while i < j:
                while 1:
                    i += 1
                    if nums[i] >= x:
                        break
                while 1:
                    j -= 1
                    if nums[j] <= x:
                        break
                if i < j:
                    nums[i], nums[j] = nums[j], nums[i]
            if j < k:
                return quick_sort(j + 1, right, k)
            return quick_sort(left, j, k)

        n = len(nums)
        return quick_sort(0, n - 1, n - k)


  • func findKthLargest(nums []int, k int) int {
	n := len(nums)
	return quickSort(nums, 0, n-1, n-k)
}

func quickSort(nums []int, left, right, k int) int {
	if left == right {
		return nums[left]
	}
	i, j := left-1, right+1
	x := nums[(left+right)>>1]
	for i < j {
		for {
			i++
			if nums[i] >= x {
				break
			}
		}
		for {
			j--
			if nums[j] <= x {
				break
			}
		}
		if i < j {
			nums[i], nums[j] = nums[j], nums[i]
		}
	}
	if j < k {
		return quickSort(nums, j+1, right, k)
	}
	return quickSort(nums, left, j, k)
}

  • function findKthLargest(nums: number[], k: number): number {
    const n = nums.length;
    const swap = (i: number, j: number) => {
        [nums[i], nums[j]] = [nums[j], nums[i]];
    };
    const sort = (l: number, r: number) => {
        if (l + 1 > k || l >= r) {
            return;
        }
        swap(l, l + Math.floor(Math.random() * (r - l)));
        const num = nums[l];
        let mark = l;
        for (let i = l + 1; i < r; i++) {
            if (nums[i] > num) {
                mark++;
                swap(i, mark);
            }
        }
        swap(l, mark);

        sort(l, mark);
        sort(mark + 1, r);
    };
    sort(0, n);
    return nums[k - 1];
}


  • use rand::Rng;

impl Solution {
    pub fn find_kth_largest(mut nums: Vec<i32>, k: i32) -> i32 {
        let k = k as usize;
        let n = nums.len();
        let mut l = 0;
        let mut r = n;
        while l <= k - 1 && l < r {
            nums.swap(l, rand::thread_rng().gen_range(l, r));
            let num = nums[l];
            let mut mark = l;
            for i in l..r {
                if nums[i] > num {
                    mark += 1;
                    nums.swap(i, mark);
                }
            }
            nums.swap(l, mark);
            if mark + 1 <= k {
                l = mark + 1;
            } else {
                r = mark;
            }
        }
        nums[k - 1]
    }
}

All Problems

All Solutions