// quickSelect returns the k-th smallest element (0-indexed).
func quickSelect(nums []int, k int) int {
}// quickSelect returns the k-th smallest element (0-indexed).
func quickSelect(nums []int, k int) int {
// Like binary search, but we don't know the split point in advance — each
// partition step reveals it. Search the whole array to start.
}// quickSelect returns the k-th smallest element (0-indexed).
func quickSelect(nums []int, k int) int {
// Like binary search, but we don't know the split point in advance — each
// partition step reveals it. Search the whole array to start.
lo, hi := 0, len(nums)-1
}// quickSelect returns the k-th smallest element (0-indexed).
func quickSelect(nums []int, k int) int {
// Like binary search, but we don't know the split point in advance — each
// partition step reveals it. Search the whole array to start.
lo, hi := 0, len(nums)-1
// partition rearranges nums[lo..hi] and returns the final index p of the
// pivot: everything left of p is smaller, everything right is larger.
}// quickSelect returns the k-th smallest element (0-indexed).
func quickSelect(nums []int, k int) int {
// Like binary search, but we don't know the split point in advance — each
// partition step reveals it. Search the whole array to start.
lo, hi := 0, len(nums)-1
for lo <= hi {
// partition rearranges nums[lo..hi] and returns the final index p of the
// pivot: everything left of p is smaller, everything right is larger.
p := partition(nums, lo, hi)
}
}// quickSelect returns the k-th smallest element (0-indexed).
func quickSelect(nums []int, k int) int {
// Like binary search, but we don't know the split point in advance — each
// partition step reveals it. Search the whole array to start.
lo, hi := 0, len(nums)-1
for lo <= hi {
// partition rearranges nums[lo..hi] and returns the final index p of the
// pivot: everything left of p is smaller, everything right is larger.
p := partition(nums, lo, hi)
// p is exactly the rank we want, so nums[p] is the k-th smallest.
// The answer's rank is higher: discard the left part, search the right.
// The answer's rank is lower: search only the left part.
}
}// quickSelect returns the k-th smallest element (0-indexed).
func quickSelect(nums []int, k int) int {
// Like binary search, but we don't know the split point in advance — each
// partition step reveals it. Search the whole array to start.
lo, hi := 0, len(nums)-1
for lo <= hi {
// partition rearranges nums[lo..hi] and returns the final index p of the
// pivot: everything left of p is smaller, everything right is larger.
p := partition(nums, lo, hi)
switch {
// p is exactly the rank we want, so nums[p] is the k-th smallest.
case p == k:
return nums[p]
// The answer's rank is higher: discard the left part, search the right.
case p < k:
lo = p + 1
// The answer's rank is lower: search only the left part.
default:
hi = p - 1
}
}
return -1 // k out of range; average O(n) since we recurse into one side only
}// quickSelect returns the k-th smallest element (0-indexed).
func quickSelect(nums []int, k int) int {
// Like binary search, but we don't know the split point in advance — each
// partition step reveals it. Search the whole array to start.
lo, hi := 0, len(nums)-1
for lo <= hi {
// partition rearranges nums[lo..hi] and returns the final index p of the
// pivot: everything left of p is smaller, everything right is larger.
p := partition(nums, lo, hi)
switch {
// p is exactly the rank we want, so nums[p] is the k-th smallest.
case p == k:
return nums[p]
// The answer's rank is higher: discard the left part, search the right.
case p < k:
lo = p + 1
// The answer's rank is lower: search only the left part.
default:
hi = p - 1
}
}
return -1 // k out of range; average O(n) since we recurse into one side only
}
// partition (Lomuto) puts nums[hi] at its final sorted position and returns it.
// Use the last element as the pivot. i marks the boundary: everything in
// nums[lo..i) is known to be < pivot.// quickSelect returns the k-th smallest element (0-indexed).
func quickSelect(nums []int, k int) int {
// Like binary search, but we don't know the split point in advance — each
// partition step reveals it. Search the whole array to start.
lo, hi := 0, len(nums)-1
for lo <= hi {
// partition rearranges nums[lo..hi] and returns the final index p of the
// pivot: everything left of p is smaller, everything right is larger.
p := partition(nums, lo, hi)
switch {
// p is exactly the rank we want, so nums[p] is the k-th smallest.
case p == k:
return nums[p]
// The answer's rank is higher: discard the left part, search the right.
case p < k:
lo = p + 1
// The answer's rank is lower: search only the left part.
default:
hi = p - 1
}
}
return -1 // k out of range; average O(n) since we recurse into one side only
}
// partition (Lomuto) puts nums[hi] at its final sorted position and returns it.
func partition(nums []int, lo, hi int) int {
// Use the last element as the pivot. i marks the boundary: everything in
// nums[lo..i) is known to be < pivot.
pivot := nums[hi]
i := lo
}// quickSelect returns the k-th smallest element (0-indexed).
func quickSelect(nums []int, k int) int {
// Like binary search, but we don't know the split point in advance — each
// partition step reveals it. Search the whole array to start.
lo, hi := 0, len(nums)-1
for lo <= hi {
// partition rearranges nums[lo..hi] and returns the final index p of the
// pivot: everything left of p is smaller, everything right is larger.
p := partition(nums, lo, hi)
switch {
// p is exactly the rank we want, so nums[p] is the k-th smallest.
case p == k:
return nums[p]
// The answer's rank is higher: discard the left part, search the right.
case p < k:
lo = p + 1
// The answer's rank is lower: search only the left part.
default:
hi = p - 1
}
}
return -1 // k out of range; average O(n) since we recurse into one side only
}
// partition (Lomuto) puts nums[hi] at its final sorted position and returns it.
func partition(nums []int, lo, hi int) int {
// Use the last element as the pivot. i marks the boundary: everything in
// nums[lo..i) is known to be < pivot.
pivot := nums[hi]
i := lo
// Sweep j across the range; each value smaller than the pivot gets swapped
// to the boundary and grows the "< pivot" region.
}// quickSelect returns the k-th smallest element (0-indexed).
func quickSelect(nums []int, k int) int {
// Like binary search, but we don't know the split point in advance — each
// partition step reveals it. Search the whole array to start.
lo, hi := 0, len(nums)-1
for lo <= hi {
// partition rearranges nums[lo..hi] and returns the final index p of the
// pivot: everything left of p is smaller, everything right is larger.
p := partition(nums, lo, hi)
switch {
// p is exactly the rank we want, so nums[p] is the k-th smallest.
case p == k:
return nums[p]
// The answer's rank is higher: discard the left part, search the right.
case p < k:
lo = p + 1
// The answer's rank is lower: search only the left part.
default:
hi = p - 1
}
}
return -1 // k out of range; average O(n) since we recurse into one side only
}
// partition (Lomuto) puts nums[hi] at its final sorted position and returns it.
func partition(nums []int, lo, hi int) int {
// Use the last element as the pivot. i marks the boundary: everything in
// nums[lo..i) is known to be < pivot.
pivot := nums[hi]
i := lo
// Sweep j across the range; each value smaller than the pivot gets swapped
// to the boundary and grows the "< pivot" region.
for j := lo; j < hi; j++ {
if nums[j] < pivot {
nums[i], nums[j] = nums[j], nums[i]
i++
}
}
}// quickSelect returns the k-th smallest element (0-indexed).
func quickSelect(nums []int, k int) int {
// Like binary search, but we don't know the split point in advance — each
// partition step reveals it. Search the whole array to start.
lo, hi := 0, len(nums)-1
for lo <= hi {
// partition rearranges nums[lo..hi] and returns the final index p of the
// pivot: everything left of p is smaller, everything right is larger.
p := partition(nums, lo, hi)
switch {
// p is exactly the rank we want, so nums[p] is the k-th smallest.
case p == k:
return nums[p]
// The answer's rank is higher: discard the left part, search the right.
case p < k:
lo = p + 1
// The answer's rank is lower: search only the left part.
default:
hi = p - 1
}
}
return -1 // k out of range; average O(n) since we recurse into one side only
}
// partition (Lomuto) puts nums[hi] at its final sorted position and returns it.
func partition(nums []int, lo, hi int) int {
// Use the last element as the pivot. i marks the boundary: everything in
// nums[lo..i) is known to be < pivot.
pivot := nums[hi]
i := lo
// Sweep j across the range; each value smaller than the pivot gets swapped
// to the boundary and grows the "< pivot" region.
for j := lo; j < hi; j++ {
if nums[j] < pivot {
nums[i], nums[j] = nums[j], nums[i]
i++
}
}
// Finally drop the pivot into the boundary slot — its true sorted position.
}// quickSelect returns the k-th smallest element (0-indexed).
func quickSelect(nums []int, k int) int {
// Like binary search, but we don't know the split point in advance — each
// partition step reveals it. Search the whole array to start.
lo, hi := 0, len(nums)-1
for lo <= hi {
// partition rearranges nums[lo..hi] and returns the final index p of the
// pivot: everything left of p is smaller, everything right is larger.
p := partition(nums, lo, hi)
switch {
// p is exactly the rank we want, so nums[p] is the k-th smallest.
case p == k:
return nums[p]
// The answer's rank is higher: discard the left part, search the right.
case p < k:
lo = p + 1
// The answer's rank is lower: search only the left part.
default:
hi = p - 1
}
}
return -1 // k out of range; average O(n) since we recurse into one side only
}
// partition (Lomuto) puts nums[hi] at its final sorted position and returns it.
func partition(nums []int, lo, hi int) int {
// Use the last element as the pivot. i marks the boundary: everything in
// nums[lo..i) is known to be < pivot.
pivot := nums[hi]
i := lo
// Sweep j across the range; each value smaller than the pivot gets swapped
// to the boundary and grows the "< pivot" region.
for j := lo; j < hi; j++ {
if nums[j] < pivot {
nums[i], nums[j] = nums[j], nums[i]
i++
}
}
// Finally drop the pivot into the boundary slot — its true sorted position.
nums[i], nums[hi] = nums[hi], nums[i]
return i
}Tap the left half to go back, the right half to go forward.
Arrow keys or space to navigate · Esc to exit.