Kth Largest Element in an Array

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        int target = nums.size() - k;
        int lo = 0, hi = nums.size() - 1;
        while (lo < hi) {
            int p = partition(nums, lo, hi);
            if (p == target) return nums[p];
            if (p < target) lo = p + 1; else hi = p - 1;
        }
        return nums[lo];
    }
private:
    int partition(vector<int>& a, int lo, int hi) {
        int pivot = a[hi];
        int i = lo;
        for (int j = lo; j < hi; ++j)
            if (a[j] < pivot) swap(a[i++], a[j]);
        swap(a[i], a[hi]);
        return i;
    }
};

func findKthLargest(nums []int, k int) int {
    target := len(nums) - k
    lo, hi := 0, len(nums)-1
    for lo < hi {
        p := partition(nums, lo, hi)
        if p == target {
            return nums[p]
        }
        if p < target {
            lo = p + 1
        } else {
            hi = p - 1
        }
    }
    return nums[lo]
}

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

from typing import List

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        target = len(nums) - k

        def partition(lo: int, hi: int) -> int:
            pivot = nums[hi]
            i = lo
            for j in range(lo, hi):
                if nums[j] < pivot:
                    nums[i], nums[j] = nums[j], nums[i]
                    i += 1
            nums[i], nums[hi] = nums[hi], nums[i]
            return i

        lo, hi = 0, len(nums) - 1
        while lo < hi:
            p = partition(lo, hi)
            if p == target:
                return nums[p]
            if p < target:
                lo = p + 1
            else:
                hi = p - 1
        return nums[lo]

function findKthLargest(nums, k) {
    const target = nums.length - k;
    let lo = 0, hi = nums.length - 1;
    while (lo < hi) {
        const p = partition(nums, lo, hi);
        if (p === target) return nums[p];
        if (p < target) lo = p + 1;
        else hi = p - 1;
    }
    return nums[lo];
}

function partition(a, lo, hi) {
    const pivot = a[hi];
    let i = lo;
    for (let j = lo; j < hi; j++) {
        if (a[j] < pivot) {
            [a[i], a[j]] = [a[j], a[i]];
            i++;
        }
    }
    [a[i], a[hi]] = [a[hi], a[i]];
    return i;
}

class Solution {
    public int findKthLargest(int[] nums, int k) {
        int target = nums.length - k;
        int lo = 0, hi = nums.length - 1;
        while (lo < hi) {
            int p = partition(nums, lo, hi);
            if (p == target) return nums[p];
            if (p < target) lo = p + 1;
            else hi = p - 1;
        }
        return nums[lo];
    }

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

function findKthLargest(nums: number[], k: number): number {
    const target = nums.length - k;
    let lo = 0, hi = nums.length - 1;
    while (lo < hi) {
        const p = partition(nums, lo, hi);
        if (p === target) return nums[p];
        if (p < target) lo = p + 1;
        else hi = p - 1;
    }
    return nums[lo];
}

function partition(a: number[], lo: number, hi: number): number {
    const pivot = a[hi];
    let i = lo;
    for (let j = lo; j < hi; j++) {
        if (a[j] < pivot) {
            [a[i], a[j]] = [a[j], a[i]];
            i++;
        }
    }
    [a[i], a[hi]] = [a[hi], a[i]];
    return i;
}