package list

import (
	"math/rand"
	"time"
)

func findKthLargest(nums []int, k int) int {
	rand.Seed(time.Now().UnixMilli())
	return quickSelect(nums, 0, len(nums)-1, len(nums)-k)
}

func quickSelect(nums []int, l, r, idx int) int {
	q := randomPartion(nums, l, r)
	if q == idx {
		return nums[q]
	} else if q < idx {
		return quickSelect(nums, q+1, r, idx)
	}

	return quickSelect(nums, l, q-1, idx)
}

func randomPartion(nums []int, l, r int) int {
	i := rand.Int()%(r-l+1) + l
	nums[i], nums[l] = nums[l], nums[i]
	return partition(nums, l, r)
}

func partition(nums []int, left, right int) int {
	pivot := left
	for {
		for left <= right && nums[left] <= nums[pivot] {
			left++
		}

		for left <= right && nums[right] >= nums[pivot] {
			right--
		}

		if left > right {
			break
		} else {
			nums[left], nums[right] = nums[right], nums[left]
		}
	}

	nums[pivot], nums[right] = nums[right], nums[pivot]
	return right
}

func partition2(nums []int, l, r int) int {
	x := nums[r]
	i := l - 1

	for j := l; j < r; j++ {
		if nums[j] <= x {
			i++
			nums[i], nums[j] = nums[j], nums[i]
		}
	}

	nums[i+1], nums[r] = nums[r], nums[i+1]

	return i + 1
}