// 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
}# quick_select returns the k-th smallest element (0-indexed).
def quick_select(nums, k):
pass# quick_select returns the k-th smallest element (0-indexed).
def quick_select(nums, k):
# Like binary search, but we don't know the split point in advance — each
# partition step reveals it. Search the whole array to start.
pass# quick_select returns the k-th smallest element (0-indexed).
def quick_select(nums, k):
# 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# quick_select returns the k-th smallest element (0-indexed).
def quick_select(nums, k):
# 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.# quick_select returns the k-th smallest element (0-indexed).
def quick_select(nums, k):
# 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
while 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)# quick_select returns the k-th smallest element (0-indexed).
def quick_select(nums, k):
# 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
while 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.# quick_select returns the k-th smallest element (0-indexed).
def quick_select(nums, k):
# 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
while 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)
if p == k:
# p is exactly the rank we want, so nums[p] is the k-th smallest.
return nums[p]
elif p < k:
# The answer's rank is higher: discard the left part, search the right.
lo = p + 1
else:
# The answer's rank is lower: search only the left part.
hi = p - 1
return -1 # k out of range; average O(n) since we recurse into one side only# quick_select returns the k-th smallest element (0-indexed).
def quick_select(nums, k):
# 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
while 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)
if p == k:
# p is exactly the rank we want, so nums[p] is the k-th smallest.
return nums[p]
elif p < k:
# The answer's rank is higher: discard the left part, search the right.
lo = p + 1
else:
# The answer's rank is lower: search only the left part.
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.# quick_select returns the k-th smallest element (0-indexed).
def quick_select(nums, k):
# 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
while 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)
if p == k:
# p is exactly the rank we want, so nums[p] is the k-th smallest.
return nums[p]
elif p < k:
# The answer's rank is higher: discard the left part, search the right.
lo = p + 1
else:
# The answer's rank is lower: search only the left part.
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.
def partition(nums, lo, hi):
# 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# quick_select returns the k-th smallest element (0-indexed).
def quick_select(nums, k):
# 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
while 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)
if p == k:
# p is exactly the rank we want, so nums[p] is the k-th smallest.
return nums[p]
elif p < k:
# The answer's rank is higher: discard the left part, search the right.
lo = p + 1
else:
# The answer's rank is lower: search only the left part.
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.
def partition(nums, lo, hi):
# 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.# quick_select returns the k-th smallest element (0-indexed).
def quick_select(nums, k):
# 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
while 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)
if p == k:
# p is exactly the rank we want, so nums[p] is the k-th smallest.
return nums[p]
elif p < k:
# The answer's rank is higher: discard the left part, search the right.
lo = p + 1
else:
# The answer's rank is lower: search only the left part.
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.
def partition(nums, lo, hi):
# 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 in range(lo, hi):
if nums[j] < pivot:
nums[i], nums[j] = nums[j], nums[i]
i += 1# quick_select returns the k-th smallest element (0-indexed).
def quick_select(nums, k):
# 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
while 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)
if p == k:
# p is exactly the rank we want, so nums[p] is the k-th smallest.
return nums[p]
elif p < k:
# The answer's rank is higher: discard the left part, search the right.
lo = p + 1
else:
# The answer's rank is lower: search only the left part.
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.
def partition(nums, lo, hi):
# 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 in range(lo, hi):
if nums[j] < pivot:
nums[i], nums[j] = nums[j], nums[i]
i += 1
# Finally drop the pivot into the boundary slot — its true sorted position.# quick_select returns the k-th smallest element (0-indexed).
def quick_select(nums, k):
# 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
while 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)
if p == k:
# p is exactly the rank we want, so nums[p] is the k-th smallest.
return nums[p]
elif p < k:
# The answer's rank is higher: discard the left part, search the right.
lo = p + 1
else:
# The answer's rank is lower: search only the left part.
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.
def partition(nums, lo, hi):
# 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 in range(lo, hi):
if nums[j] < pivot:
nums[i], nums[j] = nums[j], nums[i]
i += 1
# Finally drop the pivot into the boundary slot — its true sorted position.
nums[i], nums[hi] = nums[hi], nums[i]
return i// quickSelect returns the k-th smallest element (0-indexed).
function quickSelect(nums, k) {
}// quickSelect returns the k-th smallest element (0-indexed).
function quickSelect(nums, k) {
// 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).
function quickSelect(nums, k) {
// Like binary search, but we don't know the split point in advance — each
// partition step reveals it. Search the whole array to start.
let lo = 0, hi = nums.length - 1;
}// quickSelect returns the k-th smallest element (0-indexed).
function quickSelect(nums, k) {
// Like binary search, but we don't know the split point in advance — each
// partition step reveals it. Search the whole array to start.
let lo = 0, hi = nums.length - 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).
function quickSelect(nums, k) {
// Like binary search, but we don't know the split point in advance — each
// partition step reveals it. Search the whole array to start.
let lo = 0, hi = nums.length - 1;
while (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.
const p = partition(nums, lo, hi);
}
}// quickSelect returns the k-th smallest element (0-indexed).
function quickSelect(nums, k) {
// Like binary search, but we don't know the split point in advance — each
// partition step reveals it. Search the whole array to start.
let lo = 0, hi = nums.length - 1;
while (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.
const 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).
function quickSelect(nums, k) {
// Like binary search, but we don't know the split point in advance — each
// partition step reveals it. Search the whole array to start.
let lo = 0, hi = nums.length - 1;
while (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.
const p = partition(nums, lo, hi);
if (p === k) {
// p is exactly the rank we want, so nums[p] is the k-th smallest.
return nums[p];
} else if (p < k) {
// The answer's rank is higher: discard the left part, search the right.
lo = p + 1;
} else {
// The answer's rank is lower: search only the left part.
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).
function quickSelect(nums, k) {
// Like binary search, but we don't know the split point in advance — each
// partition step reveals it. Search the whole array to start.
let lo = 0, hi = nums.length - 1;
while (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.
const p = partition(nums, lo, hi);
if (p === k) {
// p is exactly the rank we want, so nums[p] is the k-th smallest.
return nums[p];
} else if (p < k) {
// The answer's rank is higher: discard the left part, search the right.
lo = p + 1;
} else {
// The answer's rank is lower: search only the left part.
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).
function quickSelect(nums, k) {
// Like binary search, but we don't know the split point in advance — each
// partition step reveals it. Search the whole array to start.
let lo = 0, hi = nums.length - 1;
while (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.
const p = partition(nums, lo, hi);
if (p === k) {
// p is exactly the rank we want, so nums[p] is the k-th smallest.
return nums[p];
} else if (p < k) {
// The answer's rank is higher: discard the left part, search the right.
lo = p + 1;
} else {
// The answer's rank is lower: search only the left part.
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.
function partition(nums, lo, hi) {
// Use the last element as the pivot. i marks the boundary: everything in
// nums[lo..i) is known to be < pivot.
const pivot = nums[hi];
let i = lo;
}// quickSelect returns the k-th smallest element (0-indexed).
function quickSelect(nums, k) {
// Like binary search, but we don't know the split point in advance — each
// partition step reveals it. Search the whole array to start.
let lo = 0, hi = nums.length - 1;
while (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.
const p = partition(nums, lo, hi);
if (p === k) {
// p is exactly the rank we want, so nums[p] is the k-th smallest.
return nums[p];
} else if (p < k) {
// The answer's rank is higher: discard the left part, search the right.
lo = p + 1;
} else {
// The answer's rank is lower: search only the left part.
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.
function partition(nums, lo, hi) {
// Use the last element as the pivot. i marks the boundary: everything in
// nums[lo..i) is known to be < pivot.
const pivot = nums[hi];
let 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).
function quickSelect(nums, k) {
// Like binary search, but we don't know the split point in advance — each
// partition step reveals it. Search the whole array to start.
let lo = 0, hi = nums.length - 1;
while (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.
const p = partition(nums, lo, hi);
if (p === k) {
// p is exactly the rank we want, so nums[p] is the k-th smallest.
return nums[p];
} else if (p < k) {
// The answer's rank is higher: discard the left part, search the right.
lo = p + 1;
} else {
// The answer's rank is lower: search only the left part.
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.
function partition(nums, lo, hi) {
// Use the last element as the pivot. i marks the boundary: everything in
// nums[lo..i) is known to be < pivot.
const pivot = nums[hi];
let i = lo;
// Sweep j across the range; each value smaller than the pivot gets swapped
// to the boundary and grows the "< pivot" region.
for (let 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).
function quickSelect(nums, k) {
// Like binary search, but we don't know the split point in advance — each
// partition step reveals it. Search the whole array to start.
let lo = 0, hi = nums.length - 1;
while (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.
const p = partition(nums, lo, hi);
if (p === k) {
// p is exactly the rank we want, so nums[p] is the k-th smallest.
return nums[p];
} else if (p < k) {
// The answer's rank is higher: discard the left part, search the right.
lo = p + 1;
} else {
// The answer's rank is lower: search only the left part.
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.
function partition(nums, lo, hi) {
// Use the last element as the pivot. i marks the boundary: everything in
// nums[lo..i) is known to be < pivot.
const pivot = nums[hi];
let i = lo;
// Sweep j across the range; each value smaller than the pivot gets swapped
// to the boundary and grows the "< pivot" region.
for (let 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).
function quickSelect(nums, k) {
// Like binary search, but we don't know the split point in advance — each
// partition step reveals it. Search the whole array to start.
let lo = 0, hi = nums.length - 1;
while (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.
const p = partition(nums, lo, hi);
if (p === k) {
// p is exactly the rank we want, so nums[p] is the k-th smallest.
return nums[p];
} else if (p < k) {
// The answer's rank is higher: discard the left part, search the right.
lo = p + 1;
} else {
// The answer's rank is lower: search only the left part.
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.
function partition(nums, lo, hi) {
// Use the last element as the pivot. i marks the boundary: everything in
// nums[lo..i) is known to be < pivot.
const pivot = nums[hi];
let i = lo;
// Sweep j across the range; each value smaller than the pivot gets swapped
// to the boundary and grows the "< pivot" region.
for (let 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;
}// quickSelect returns the k-th smallest element (0-indexed).
function quickSelect(nums: number[], k: number): number {
}// quickSelect returns the k-th smallest element (0-indexed).
function quickSelect(nums: number[], k: number): number {
// 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).
function quickSelect(nums: number[], k: number): number {
// Like binary search, but we don't know the split point in advance — each
// partition step reveals it. Search the whole array to start.
let lo = 0, hi = nums.length - 1;
}// quickSelect returns the k-th smallest element (0-indexed).
function quickSelect(nums: number[], k: number): number {
// Like binary search, but we don't know the split point in advance — each
// partition step reveals it. Search the whole array to start.
let lo = 0, hi = nums.length - 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).
function quickSelect(nums: number[], k: number): number {
// Like binary search, but we don't know the split point in advance — each
// partition step reveals it. Search the whole array to start.
let lo = 0, hi = nums.length - 1;
while (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.
const p = partition(nums, lo, hi);
}
}// quickSelect returns the k-th smallest element (0-indexed).
function quickSelect(nums: number[], k: number): number {
// Like binary search, but we don't know the split point in advance — each
// partition step reveals it. Search the whole array to start.
let lo = 0, hi = nums.length - 1;
while (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.
const 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).
function quickSelect(nums: number[], k: number): number {
// Like binary search, but we don't know the split point in advance — each
// partition step reveals it. Search the whole array to start.
let lo = 0, hi = nums.length - 1;
while (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.
const p = partition(nums, lo, hi);
if (p === k) {
// p is exactly the rank we want, so nums[p] is the k-th smallest.
return nums[p];
} else if (p < k) {
// The answer's rank is higher: discard the left part, search the right.
lo = p + 1;
} else {
// The answer's rank is lower: search only the left part.
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).
function quickSelect(nums: number[], k: number): number {
// Like binary search, but we don't know the split point in advance — each
// partition step reveals it. Search the whole array to start.
let lo = 0, hi = nums.length - 1;
while (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.
const p = partition(nums, lo, hi);
if (p === k) {
// p is exactly the rank we want, so nums[p] is the k-th smallest.
return nums[p];
} else if (p < k) {
// The answer's rank is higher: discard the left part, search the right.
lo = p + 1;
} else {
// The answer's rank is lower: search only the left part.
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).
function quickSelect(nums: number[], k: number): number {
// Like binary search, but we don't know the split point in advance — each
// partition step reveals it. Search the whole array to start.
let lo = 0, hi = nums.length - 1;
while (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.
const p = partition(nums, lo, hi);
if (p === k) {
// p is exactly the rank we want, so nums[p] is the k-th smallest.
return nums[p];
} else if (p < k) {
// The answer's rank is higher: discard the left part, search the right.
lo = p + 1;
} else {
// The answer's rank is lower: search only the left part.
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.
function partition(nums: number[], lo: number, hi: number): number {
// Use the last element as the pivot. i marks the boundary: everything in
// nums[lo..i) is known to be < pivot.
const pivot = nums[hi];
let i = lo;
}// quickSelect returns the k-th smallest element (0-indexed).
function quickSelect(nums: number[], k: number): number {
// Like binary search, but we don't know the split point in advance — each
// partition step reveals it. Search the whole array to start.
let lo = 0, hi = nums.length - 1;
while (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.
const p = partition(nums, lo, hi);
if (p === k) {
// p is exactly the rank we want, so nums[p] is the k-th smallest.
return nums[p];
} else if (p < k) {
// The answer's rank is higher: discard the left part, search the right.
lo = p + 1;
} else {
// The answer's rank is lower: search only the left part.
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.
function partition(nums: number[], lo: number, hi: number): number {
// Use the last element as the pivot. i marks the boundary: everything in
// nums[lo..i) is known to be < pivot.
const pivot = nums[hi];
let 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).
function quickSelect(nums: number[], k: number): number {
// Like binary search, but we don't know the split point in advance — each
// partition step reveals it. Search the whole array to start.
let lo = 0, hi = nums.length - 1;
while (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.
const p = partition(nums, lo, hi);
if (p === k) {
// p is exactly the rank we want, so nums[p] is the k-th smallest.
return nums[p];
} else if (p < k) {
// The answer's rank is higher: discard the left part, search the right.
lo = p + 1;
} else {
// The answer's rank is lower: search only the left part.
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.
function partition(nums: number[], lo: number, hi: number): number {
// Use the last element as the pivot. i marks the boundary: everything in
// nums[lo..i) is known to be < pivot.
const pivot = nums[hi];
let i = lo;
// Sweep j across the range; each value smaller than the pivot gets swapped
// to the boundary and grows the "< pivot" region.
for (let 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).
function quickSelect(nums: number[], k: number): number {
// Like binary search, but we don't know the split point in advance — each
// partition step reveals it. Search the whole array to start.
let lo = 0, hi = nums.length - 1;
while (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.
const p = partition(nums, lo, hi);
if (p === k) {
// p is exactly the rank we want, so nums[p] is the k-th smallest.
return nums[p];
} else if (p < k) {
// The answer's rank is higher: discard the left part, search the right.
lo = p + 1;
} else {
// The answer's rank is lower: search only the left part.
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.
function partition(nums: number[], lo: number, hi: number): number {
// Use the last element as the pivot. i marks the boundary: everything in
// nums[lo..i) is known to be < pivot.
const pivot = nums[hi];
let i = lo;
// Sweep j across the range; each value smaller than the pivot gets swapped
// to the boundary and grows the "< pivot" region.
for (let 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).
function quickSelect(nums: number[], k: number): number {
// Like binary search, but we don't know the split point in advance — each
// partition step reveals it. Search the whole array to start.
let lo = 0, hi = nums.length - 1;
while (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.
const p = partition(nums, lo, hi);
if (p === k) {
// p is exactly the rank we want, so nums[p] is the k-th smallest.
return nums[p];
} else if (p < k) {
// The answer's rank is higher: discard the left part, search the right.
lo = p + 1;
} else {
// The answer's rank is lower: search only the left part.
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.
function partition(nums: number[], lo: number, hi: number): number {
// Use the last element as the pivot. i marks the boundary: everything in
// nums[lo..i) is known to be < pivot.
const pivot = nums[hi];
let i = lo;
// Sweep j across the range; each value smaller than the pivot gets swapped
// to the boundary and grows the "< pivot" region.
for (let 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;
}class Solution {
// quickSelect returns the k-th smallest element (0-indexed).
static int quickSelect(int[] nums, int k) {
}
}class Solution {
// quickSelect returns the k-th smallest element (0-indexed).
static int quickSelect(int[] nums, int k) {
// Like binary search, but we don't know the split point in advance — each
// partition step reveals it. Search the whole array to start.
}
}class Solution {
// quickSelect returns the k-th smallest element (0-indexed).
static int quickSelect(int[] nums, int k) {
// Like binary search, but we don't know the split point in advance — each
// partition step reveals it. Search the whole array to start.
int lo = 0, hi = nums.length - 1;
}
}class Solution {
// quickSelect returns the k-th smallest element (0-indexed).
static int quickSelect(int[] nums, int k) {
// Like binary search, but we don't know the split point in advance — each
// partition step reveals it. Search the whole array to start.
int lo = 0, hi = nums.length - 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.
}
}class Solution {
// quickSelect returns the k-th smallest element (0-indexed).
static int quickSelect(int[] nums, int k) {
// Like binary search, but we don't know the split point in advance — each
// partition step reveals it. Search the whole array to start.
int lo = 0, hi = nums.length - 1;
while (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.
int p = partition(nums, lo, hi);
}
}
}class Solution {
// quickSelect returns the k-th smallest element (0-indexed).
static int quickSelect(int[] nums, int k) {
// Like binary search, but we don't know the split point in advance — each
// partition step reveals it. Search the whole array to start.
int lo = 0, hi = nums.length - 1;
while (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.
int 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.
}
}
}class Solution {
// quickSelect returns the k-th smallest element (0-indexed).
static int quickSelect(int[] nums, int k) {
// Like binary search, but we don't know the split point in advance — each
// partition step reveals it. Search the whole array to start.
int lo = 0, hi = nums.length - 1;
while (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.
int p = partition(nums, lo, hi);
if (p == k) {
// p is exactly the rank we want, so nums[p] is the k-th smallest.
return nums[p];
} else if (p < k) {
// The answer's rank is higher: discard the left part, search the right.
lo = p + 1;
} else {
// The answer's rank is lower: search only the left part.
hi = p - 1;
}
}
return -1; // k out of range; average O(n) since we recurse into one side only
}
}class Solution {
// quickSelect returns the k-th smallest element (0-indexed).
static int quickSelect(int[] nums, int k) {
// Like binary search, but we don't know the split point in advance — each
// partition step reveals it. Search the whole array to start.
int lo = 0, hi = nums.length - 1;
while (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.
int p = partition(nums, lo, hi);
if (p == k) {
// p is exactly the rank we want, so nums[p] is the k-th smallest.
return nums[p];
} else if (p < k) {
// The answer's rank is higher: discard the left part, search the right.
lo = p + 1;
} else {
// The answer's rank is lower: search only the left part.
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.
}class Solution {
// quickSelect returns the k-th smallest element (0-indexed).
static int quickSelect(int[] nums, int k) {
// Like binary search, but we don't know the split point in advance — each
// partition step reveals it. Search the whole array to start.
int lo = 0, hi = nums.length - 1;
while (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.
int p = partition(nums, lo, hi);
if (p == k) {
// p is exactly the rank we want, so nums[p] is the k-th smallest.
return nums[p];
} else if (p < k) {
// The answer's rank is higher: discard the left part, search the right.
lo = p + 1;
} else {
// The answer's rank is lower: search only the left part.
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.
private static int partition(int[] nums, int lo, int hi) {
// Use the last element as the pivot. i marks the boundary: everything in
// nums[lo..i) is known to be < pivot.
int pivot = nums[hi];
int i = lo;
}
}class Solution {
// quickSelect returns the k-th smallest element (0-indexed).
static int quickSelect(int[] nums, int k) {
// Like binary search, but we don't know the split point in advance — each
// partition step reveals it. Search the whole array to start.
int lo = 0, hi = nums.length - 1;
while (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.
int p = partition(nums, lo, hi);
if (p == k) {
// p is exactly the rank we want, so nums[p] is the k-th smallest.
return nums[p];
} else if (p < k) {
// The answer's rank is higher: discard the left part, search the right.
lo = p + 1;
} else {
// The answer's rank is lower: search only the left part.
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.
private static int partition(int[] nums, int lo, int hi) {
// Use the last element as the pivot. i marks the boundary: everything in
// nums[lo..i) is known to be < pivot.
int pivot = nums[hi];
int i = lo;
// Sweep j across the range; each value smaller than the pivot gets swapped
// to the boundary and grows the "< pivot" region.
}
}class Solution {
// quickSelect returns the k-th smallest element (0-indexed).
static int quickSelect(int[] nums, int k) {
// Like binary search, but we don't know the split point in advance — each
// partition step reveals it. Search the whole array to start.
int lo = 0, hi = nums.length - 1;
while (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.
int p = partition(nums, lo, hi);
if (p == k) {
// p is exactly the rank we want, so nums[p] is the k-th smallest.
return nums[p];
} else if (p < k) {
// The answer's rank is higher: discard the left part, search the right.
lo = p + 1;
} else {
// The answer's rank is lower: search only the left part.
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.
private static int partition(int[] nums, int lo, int hi) {
// Use the last element as the pivot. i marks the boundary: everything in
// nums[lo..i) is known to be < pivot.
int pivot = nums[hi];
int i = lo;
// Sweep j across the range; each value smaller than the pivot gets swapped
// to the boundary and grows the "< pivot" region.
for (int j = lo; j < hi; j++) {
if (nums[j] < pivot) {
int tmp = nums[i]; nums[i] = nums[j]; nums[j] = tmp;
i++;
}
}
}
}class Solution {
// quickSelect returns the k-th smallest element (0-indexed).
static int quickSelect(int[] nums, int k) {
// Like binary search, but we don't know the split point in advance — each
// partition step reveals it. Search the whole array to start.
int lo = 0, hi = nums.length - 1;
while (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.
int p = partition(nums, lo, hi);
if (p == k) {
// p is exactly the rank we want, so nums[p] is the k-th smallest.
return nums[p];
} else if (p < k) {
// The answer's rank is higher: discard the left part, search the right.
lo = p + 1;
} else {
// The answer's rank is lower: search only the left part.
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.
private static int partition(int[] nums, int lo, int hi) {
// Use the last element as the pivot. i marks the boundary: everything in
// nums[lo..i) is known to be < pivot.
int pivot = nums[hi];
int i = lo;
// Sweep j across the range; each value smaller than the pivot gets swapped
// to the boundary and grows the "< pivot" region.
for (int j = lo; j < hi; j++) {
if (nums[j] < pivot) {
int tmp = nums[i]; nums[i] = nums[j]; nums[j] = tmp;
i++;
}
}
// Finally drop the pivot into the boundary slot — its true sorted position.
}
}class Solution {
// quickSelect returns the k-th smallest element (0-indexed).
static int quickSelect(int[] nums, int k) {
// Like binary search, but we don't know the split point in advance — each
// partition step reveals it. Search the whole array to start.
int lo = 0, hi = nums.length - 1;
while (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.
int p = partition(nums, lo, hi);
if (p == k) {
// p is exactly the rank we want, so nums[p] is the k-th smallest.
return nums[p];
} else if (p < k) {
// The answer's rank is higher: discard the left part, search the right.
lo = p + 1;
} else {
// The answer's rank is lower: search only the left part.
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.
private static int partition(int[] nums, int lo, int hi) {
// Use the last element as the pivot. i marks the boundary: everything in
// nums[lo..i) is known to be < pivot.
int pivot = nums[hi];
int i = lo;
// Sweep j across the range; each value smaller than the pivot gets swapped
// to the boundary and grows the "< pivot" region.
for (int j = lo; j < hi; j++) {
if (nums[j] < pivot) {
int tmp = nums[i]; nums[i] = nums[j]; nums[j] = tmp;
i++;
}
}
// Finally drop the pivot into the boundary slot — its true sorted position.
int last = nums[i]; nums[i] = nums[hi]; nums[hi] = last;
return i;
}
}public class Solution {
// QuickSelect returns the k-th smallest element (0-indexed).
public static int QuickSelect(int[] nums, int k) {
}
}public class Solution {
// QuickSelect returns the k-th smallest element (0-indexed).
public static int QuickSelect(int[] nums, int k) {
// Like binary search, but we don't know the split point in advance — each
// partition step reveals it. Search the whole array to start.
}
}public class Solution {
// QuickSelect returns the k-th smallest element (0-indexed).
public static int QuickSelect(int[] nums, int k) {
// Like binary search, but we don't know the split point in advance — each
// partition step reveals it. Search the whole array to start.
int lo = 0, hi = nums.Length - 1;
}
}public class Solution {
// QuickSelect returns the k-th smallest element (0-indexed).
public static int QuickSelect(int[] nums, int k) {
// Like binary search, but we don't know the split point in advance — each
// partition step reveals it. Search the whole array to start.
int lo = 0, hi = nums.Length - 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.
}
}public class Solution {
// QuickSelect returns the k-th smallest element (0-indexed).
public static int QuickSelect(int[] nums, int k) {
// Like binary search, but we don't know the split point in advance — each
// partition step reveals it. Search the whole array to start.
int lo = 0, hi = nums.Length - 1;
while (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.
int p = Partition(nums, lo, hi);
}
}
}public class Solution {
// QuickSelect returns the k-th smallest element (0-indexed).
public static int QuickSelect(int[] nums, int k) {
// Like binary search, but we don't know the split point in advance — each
// partition step reveals it. Search the whole array to start.
int lo = 0, hi = nums.Length - 1;
while (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.
int 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.
}
}
}public class Solution {
// QuickSelect returns the k-th smallest element (0-indexed).
public static int QuickSelect(int[] nums, int k) {
// Like binary search, but we don't know the split point in advance — each
// partition step reveals it. Search the whole array to start.
int lo = 0, hi = nums.Length - 1;
while (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.
int p = Partition(nums, lo, hi);
if (p == k) {
// p is exactly the rank we want, so nums[p] is the k-th smallest.
return nums[p];
} else if (p < k) {
// The answer's rank is higher: discard the left part, search the right.
lo = p + 1;
} else {
// The answer's rank is lower: search only the left part.
hi = p - 1;
}
}
return -1; // k out of range; average O(n) since we recurse into one side only
}
}public class Solution {
// QuickSelect returns the k-th smallest element (0-indexed).
public static int QuickSelect(int[] nums, int k) {
// Like binary search, but we don't know the split point in advance — each
// partition step reveals it. Search the whole array to start.
int lo = 0, hi = nums.Length - 1;
while (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.
int p = Partition(nums, lo, hi);
if (p == k) {
// p is exactly the rank we want, so nums[p] is the k-th smallest.
return nums[p];
} else if (p < k) {
// The answer's rank is higher: discard the left part, search the right.
lo = p + 1;
} else {
// The answer's rank is lower: search only the left part.
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.
}public class Solution {
// QuickSelect returns the k-th smallest element (0-indexed).
public static int QuickSelect(int[] nums, int k) {
// Like binary search, but we don't know the split point in advance — each
// partition step reveals it. Search the whole array to start.
int lo = 0, hi = nums.Length - 1;
while (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.
int p = Partition(nums, lo, hi);
if (p == k) {
// p is exactly the rank we want, so nums[p] is the k-th smallest.
return nums[p];
} else if (p < k) {
// The answer's rank is higher: discard the left part, search the right.
lo = p + 1;
} else {
// The answer's rank is lower: search only the left part.
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.
private static int Partition(int[] nums, int lo, int hi) {
// Use the last element as the pivot. i marks the boundary: everything in
// nums[lo..i) is known to be < pivot.
int pivot = nums[hi];
int i = lo;
}
}public class Solution {
// QuickSelect returns the k-th smallest element (0-indexed).
public static int QuickSelect(int[] nums, int k) {
// Like binary search, but we don't know the split point in advance — each
// partition step reveals it. Search the whole array to start.
int lo = 0, hi = nums.Length - 1;
while (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.
int p = Partition(nums, lo, hi);
if (p == k) {
// p is exactly the rank we want, so nums[p] is the k-th smallest.
return nums[p];
} else if (p < k) {
// The answer's rank is higher: discard the left part, search the right.
lo = p + 1;
} else {
// The answer's rank is lower: search only the left part.
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.
private static int Partition(int[] nums, int lo, int hi) {
// Use the last element as the pivot. i marks the boundary: everything in
// nums[lo..i) is known to be < pivot.
int pivot = nums[hi];
int i = lo;
// Sweep j across the range; each value smaller than the pivot gets swapped
// to the boundary and grows the "< pivot" region.
}
}public class Solution {
// QuickSelect returns the k-th smallest element (0-indexed).
public static int QuickSelect(int[] nums, int k) {
// Like binary search, but we don't know the split point in advance — each
// partition step reveals it. Search the whole array to start.
int lo = 0, hi = nums.Length - 1;
while (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.
int p = Partition(nums, lo, hi);
if (p == k) {
// p is exactly the rank we want, so nums[p] is the k-th smallest.
return nums[p];
} else if (p < k) {
// The answer's rank is higher: discard the left part, search the right.
lo = p + 1;
} else {
// The answer's rank is lower: search only the left part.
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.
private static int Partition(int[] nums, int lo, int hi) {
// Use the last element as the pivot. i marks the boundary: everything in
// nums[lo..i) is known to be < pivot.
int pivot = nums[hi];
int i = lo;
// Sweep j across the range; each value smaller than the pivot gets swapped
// to the boundary and grows the "< pivot" region.
for (int j = lo; j < hi; j++) {
if (nums[j] < pivot) {
int tmp = nums[i]; nums[i] = nums[j]; nums[j] = tmp;
i++;
}
}
}
}public class Solution {
// QuickSelect returns the k-th smallest element (0-indexed).
public static int QuickSelect(int[] nums, int k) {
// Like binary search, but we don't know the split point in advance — each
// partition step reveals it. Search the whole array to start.
int lo = 0, hi = nums.Length - 1;
while (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.
int p = Partition(nums, lo, hi);
if (p == k) {
// p is exactly the rank we want, so nums[p] is the k-th smallest.
return nums[p];
} else if (p < k) {
// The answer's rank is higher: discard the left part, search the right.
lo = p + 1;
} else {
// The answer's rank is lower: search only the left part.
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.
private static int Partition(int[] nums, int lo, int hi) {
// Use the last element as the pivot. i marks the boundary: everything in
// nums[lo..i) is known to be < pivot.
int pivot = nums[hi];
int i = lo;
// Sweep j across the range; each value smaller than the pivot gets swapped
// to the boundary and grows the "< pivot" region.
for (int j = lo; j < hi; j++) {
if (nums[j] < pivot) {
int tmp = nums[i]; nums[i] = nums[j]; nums[j] = tmp;
i++;
}
}
// Finally drop the pivot into the boundary slot — its true sorted position.
}
}public class Solution {
// QuickSelect returns the k-th smallest element (0-indexed).
public static int QuickSelect(int[] nums, int k) {
// Like binary search, but we don't know the split point in advance — each
// partition step reveals it. Search the whole array to start.
int lo = 0, hi = nums.Length - 1;
while (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.
int p = Partition(nums, lo, hi);
if (p == k) {
// p is exactly the rank we want, so nums[p] is the k-th smallest.
return nums[p];
} else if (p < k) {
// The answer's rank is higher: discard the left part, search the right.
lo = p + 1;
} else {
// The answer's rank is lower: search only the left part.
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.
private static int Partition(int[] nums, int lo, int hi) {
// Use the last element as the pivot. i marks the boundary: everything in
// nums[lo..i) is known to be < pivot.
int pivot = nums[hi];
int i = lo;
// Sweep j across the range; each value smaller than the pivot gets swapped
// to the boundary and grows the "< pivot" region.
for (int j = lo; j < hi; j++) {
if (nums[j] < pivot) {
int tmp = nums[i]; nums[i] = nums[j]; nums[j] = tmp;
i++;
}
}
// Finally drop the pivot into the boundary slot — its true sorted position.
int last = nums[i]; nums[i] = nums[hi]; nums[hi] = last;
return i;
}
}// Declared up front so quickSelect can call it before it is
// defined further down.
static int partition(int* nums, int lo, int hi);
// quickSelect returns the k-th smallest element of nums[0..numsSize) (0-indexed).
int quickSelect(int* nums, int numsSize, int k) {
}// Declared up front so quickSelect can call it before it is
// defined further down.
static int partition(int* nums, int lo, int hi);
// quickSelect returns the k-th smallest element of nums[0..numsSize) (0-indexed).
int quickSelect(int* nums, int numsSize, int k) {
// Like binary search, but we don't know the split point in advance — each
// partition step reveals it. Search the whole array to start.
}// Declared up front so quickSelect can call it before it is
// defined further down.
static int partition(int* nums, int lo, int hi);
// quickSelect returns the k-th smallest element of nums[0..numsSize) (0-indexed).
int quickSelect(int* nums, int numsSize, int k) {
// Like binary search, but we don't know the split point in advance — each
// partition step reveals it. Search the whole array to start.
int lo = 0, hi = numsSize - 1;
}// Declared up front so quickSelect can call it before it is
// defined further down.
static int partition(int* nums, int lo, int hi);
// quickSelect returns the k-th smallest element of nums[0..numsSize) (0-indexed).
int quickSelect(int* nums, int numsSize, int k) {
// Like binary search, but we don't know the split point in advance — each
// partition step reveals it. Search the whole array to start.
int lo = 0, hi = numsSize - 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.
}// Declared up front so quickSelect can call it before it is
// defined further down.
static int partition(int* nums, int lo, int hi);
// quickSelect returns the k-th smallest element of nums[0..numsSize) (0-indexed).
int quickSelect(int* nums, int numsSize, int k) {
// Like binary search, but we don't know the split point in advance — each
// partition step reveals it. Search the whole array to start.
int lo = 0, hi = numsSize - 1;
while (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.
int p = partition(nums, lo, hi);
}
}// Declared up front so quickSelect can call it before it is
// defined further down.
static int partition(int* nums, int lo, int hi);
// quickSelect returns the k-th smallest element of nums[0..numsSize) (0-indexed).
int quickSelect(int* nums, int numsSize, int k) {
// Like binary search, but we don't know the split point in advance — each
// partition step reveals it. Search the whole array to start.
int lo = 0, hi = numsSize - 1;
while (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.
int 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.
}
}// Declared up front so quickSelect can call it before it is
// defined further down.
static int partition(int* nums, int lo, int hi);
// quickSelect returns the k-th smallest element of nums[0..numsSize) (0-indexed).
int quickSelect(int* nums, int numsSize, int k) {
// Like binary search, but we don't know the split point in advance — each
// partition step reveals it. Search the whole array to start.
int lo = 0, hi = numsSize - 1;
while (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.
int p = partition(nums, lo, hi);
if (p == k) {
// p is exactly the rank we want, so nums[p] is the k-th smallest.
return nums[p];
} else if (p < k) {
// The answer's rank is higher: discard the left part, search the right.
lo = p + 1;
} else {
// The answer's rank is lower: search only the left part.
hi = p - 1;
}
}
return -1; // k out of range; average O(n) since we recurse into one side only
}// Declared up front so quickSelect can call it before it is
// defined further down.
static int partition(int* nums, int lo, int hi);
// quickSelect returns the k-th smallest element of nums[0..numsSize) (0-indexed).
int quickSelect(int* nums, int numsSize, int k) {
// Like binary search, but we don't know the split point in advance — each
// partition step reveals it. Search the whole array to start.
int lo = 0, hi = numsSize - 1;
while (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.
int p = partition(nums, lo, hi);
if (p == k) {
// p is exactly the rank we want, so nums[p] is the k-th smallest.
return nums[p];
} else if (p < k) {
// The answer's rank is higher: discard the left part, search the right.
lo = p + 1;
} else {
// The answer's rank is lower: search only the left part.
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.
// Declared up front so quickSelect can call it before it is
// defined further down.
static int partition(int* nums, int lo, int hi);
// quickSelect returns the k-th smallest element of nums[0..numsSize) (0-indexed).
int quickSelect(int* nums, int numsSize, int k) {
// Like binary search, but we don't know the split point in advance — each
// partition step reveals it. Search the whole array to start.
int lo = 0, hi = numsSize - 1;
while (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.
int p = partition(nums, lo, hi);
if (p == k) {
// p is exactly the rank we want, so nums[p] is the k-th smallest.
return nums[p];
} else if (p < k) {
// The answer's rank is higher: discard the left part, search the right.
lo = p + 1;
} else {
// The answer's rank is lower: search only the left part.
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.
static int partition(int* nums, int lo, int hi) {
// Use the last element as the pivot. i marks the boundary: everything in
// nums[lo..i) is known to be < pivot.
int pivot = nums[hi];
int i = lo;
}// Declared up front so quickSelect can call it before it is
// defined further down.
static int partition(int* nums, int lo, int hi);
// quickSelect returns the k-th smallest element of nums[0..numsSize) (0-indexed).
int quickSelect(int* nums, int numsSize, int k) {
// Like binary search, but we don't know the split point in advance — each
// partition step reveals it. Search the whole array to start.
int lo = 0, hi = numsSize - 1;
while (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.
int p = partition(nums, lo, hi);
if (p == k) {
// p is exactly the rank we want, so nums[p] is the k-th smallest.
return nums[p];
} else if (p < k) {
// The answer's rank is higher: discard the left part, search the right.
lo = p + 1;
} else {
// The answer's rank is lower: search only the left part.
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.
static int partition(int* nums, int lo, int hi) {
// Use the last element as the pivot. i marks the boundary: everything in
// nums[lo..i) is known to be < pivot.
int pivot = nums[hi];
int i = lo;
// Sweep j across the range; each value smaller than the pivot gets swapped
// to the boundary and grows the "< pivot" region.
}// Declared up front so quickSelect can call it before it is
// defined further down.
static int partition(int* nums, int lo, int hi);
// quickSelect returns the k-th smallest element of nums[0..numsSize) (0-indexed).
int quickSelect(int* nums, int numsSize, int k) {
// Like binary search, but we don't know the split point in advance — each
// partition step reveals it. Search the whole array to start.
int lo = 0, hi = numsSize - 1;
while (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.
int p = partition(nums, lo, hi);
if (p == k) {
// p is exactly the rank we want, so nums[p] is the k-th smallest.
return nums[p];
} else if (p < k) {
// The answer's rank is higher: discard the left part, search the right.
lo = p + 1;
} else {
// The answer's rank is lower: search only the left part.
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.
static int partition(int* nums, int lo, int hi) {
// Use the last element as the pivot. i marks the boundary: everything in
// nums[lo..i) is known to be < pivot.
int pivot = nums[hi];
int i = lo;
// Sweep j across the range; each value smaller than the pivot gets swapped
// to the boundary and grows the "< pivot" region.
for (int j = lo; j < hi; j++) {
if (nums[j] < pivot) {
int tmp = nums[i]; nums[i] = nums[j]; nums[j] = tmp;
i++;
}
}
}// Declared up front so quickSelect can call it before it is
// defined further down.
static int partition(int* nums, int lo, int hi);
// quickSelect returns the k-th smallest element of nums[0..numsSize) (0-indexed).
int quickSelect(int* nums, int numsSize, int k) {
// Like binary search, but we don't know the split point in advance — each
// partition step reveals it. Search the whole array to start.
int lo = 0, hi = numsSize - 1;
while (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.
int p = partition(nums, lo, hi);
if (p == k) {
// p is exactly the rank we want, so nums[p] is the k-th smallest.
return nums[p];
} else if (p < k) {
// The answer's rank is higher: discard the left part, search the right.
lo = p + 1;
} else {
// The answer's rank is lower: search only the left part.
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.
static int partition(int* nums, int lo, int hi) {
// Use the last element as the pivot. i marks the boundary: everything in
// nums[lo..i) is known to be < pivot.
int pivot = nums[hi];
int i = lo;
// Sweep j across the range; each value smaller than the pivot gets swapped
// to the boundary and grows the "< pivot" region.
for (int j = lo; j < hi; j++) {
if (nums[j] < pivot) {
int tmp = nums[i]; nums[i] = nums[j]; nums[j] = tmp;
i++;
}
}
// Finally drop the pivot into the boundary slot — its true sorted position.
}// Declared up front so quickSelect can call it before it is
// defined further down.
static int partition(int* nums, int lo, int hi);
// quickSelect returns the k-th smallest element of nums[0..numsSize) (0-indexed).
int quickSelect(int* nums, int numsSize, int k) {
// Like binary search, but we don't know the split point in advance — each
// partition step reveals it. Search the whole array to start.
int lo = 0, hi = numsSize - 1;
while (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.
int p = partition(nums, lo, hi);
if (p == k) {
// p is exactly the rank we want, so nums[p] is the k-th smallest.
return nums[p];
} else if (p < k) {
// The answer's rank is higher: discard the left part, search the right.
lo = p + 1;
} else {
// The answer's rank is lower: search only the left part.
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.
static int partition(int* nums, int lo, int hi) {
// Use the last element as the pivot. i marks the boundary: everything in
// nums[lo..i) is known to be < pivot.
int pivot = nums[hi];
int i = lo;
// Sweep j across the range; each value smaller than the pivot gets swapped
// to the boundary and grows the "< pivot" region.
for (int j = lo; j < hi; j++) {
if (nums[j] < pivot) {
int tmp = nums[i]; nums[i] = nums[j]; nums[j] = tmp;
i++;
}
}
// Finally drop the pivot into the boundary slot — its true sorted position.
int last = nums[i]; nums[i] = nums[hi]; nums[hi] = last;
return i;
}#include <vector>
using namespace std;
// Declared up front so quickSelect can call it below. Named
// partitionRange because "using namespace std" also puts
// std::partition in scope — same name, different algorithm.
int partitionRange(vector<int>& nums, int lo, int hi);
// quickSelect returns the k-th smallest element (0-indexed).
int quickSelect(vector<int>& nums, int k) {
}#include <vector>
using namespace std;
// Declared up front so quickSelect can call it below. Named
// partitionRange because "using namespace std" also puts
// std::partition in scope — same name, different algorithm.
int partitionRange(vector<int>& nums, int lo, int hi);
// quickSelect returns the k-th smallest element (0-indexed).
int quickSelect(vector<int>& nums, int k) {
// Like binary search, but we don't know the split point in advance — each
// partition step reveals it. Search the whole array to start.
}#include <vector>
using namespace std;
// Declared up front so quickSelect can call it below. Named
// partitionRange because "using namespace std" also puts
// std::partition in scope — same name, different algorithm.
int partitionRange(vector<int>& nums, int lo, int hi);
// quickSelect returns the k-th smallest element (0-indexed).
int quickSelect(vector<int>& nums, int k) {
// Like binary search, but we don't know the split point in advance — each
// partition step reveals it. Search the whole array to start.
int lo = 0, hi = (int)nums.size() - 1;
}#include <vector>
using namespace std;
// Declared up front so quickSelect can call it below. Named
// partitionRange because "using namespace std" also puts
// std::partition in scope — same name, different algorithm.
int partitionRange(vector<int>& nums, int lo, int hi);
// quickSelect returns the k-th smallest element (0-indexed).
int quickSelect(vector<int>& nums, int k) {
// Like binary search, but we don't know the split point in advance — each
// partition step reveals it. Search the whole array to start.
int lo = 0, hi = (int)nums.size() - 1;
// partitionRange rearranges nums[lo..hi] and returns the final index p of
// the pivot: everything left of p is smaller, everything right is larger.
}#include <vector>
using namespace std;
// Declared up front so quickSelect can call it below. Named
// partitionRange because "using namespace std" also puts
// std::partition in scope — same name, different algorithm.
int partitionRange(vector<int>& nums, int lo, int hi);
// quickSelect returns the k-th smallest element (0-indexed).
int quickSelect(vector<int>& nums, int k) {
// Like binary search, but we don't know the split point in advance — each
// partition step reveals it. Search the whole array to start.
int lo = 0, hi = (int)nums.size() - 1;
while (lo <= hi) {
// partitionRange rearranges nums[lo..hi] and returns the final index p of
// the pivot: everything left of p is smaller, everything right is larger.
int p = partitionRange(nums, lo, hi);
}
}#include <vector>
using namespace std;
// Declared up front so quickSelect can call it below. Named
// partitionRange because "using namespace std" also puts
// std::partition in scope — same name, different algorithm.
int partitionRange(vector<int>& nums, int lo, int hi);
// quickSelect returns the k-th smallest element (0-indexed).
int quickSelect(vector<int>& nums, int k) {
// Like binary search, but we don't know the split point in advance — each
// partition step reveals it. Search the whole array to start.
int lo = 0, hi = (int)nums.size() - 1;
while (lo <= hi) {
// partitionRange rearranges nums[lo..hi] and returns the final index p of
// the pivot: everything left of p is smaller, everything right is larger.
int p = partitionRange(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.
}
}#include <vector>
using namespace std;
// Declared up front so quickSelect can call it below. Named
// partitionRange because "using namespace std" also puts
// std::partition in scope — same name, different algorithm.
int partitionRange(vector<int>& nums, int lo, int hi);
// quickSelect returns the k-th smallest element (0-indexed).
int quickSelect(vector<int>& nums, int k) {
// Like binary search, but we don't know the split point in advance — each
// partition step reveals it. Search the whole array to start.
int lo = 0, hi = (int)nums.size() - 1;
while (lo <= hi) {
// partitionRange rearranges nums[lo..hi] and returns the final index p of
// the pivot: everything left of p is smaller, everything right is larger.
int p = partitionRange(nums, lo, hi);
if (p == k) {
// p is exactly the rank we want, so nums[p] is the k-th smallest.
return nums[p];
} else if (p < k) {
// The answer's rank is higher: discard the left part, search the right.
lo = p + 1;
} else {
// The answer's rank is lower: search only the left part.
hi = p - 1;
}
}
return -1; // k out of range; average O(n) since we recurse into one side only
}#include <vector>
using namespace std;
// Declared up front so quickSelect can call it below. Named
// partitionRange because "using namespace std" also puts
// std::partition in scope — same name, different algorithm.
int partitionRange(vector<int>& nums, int lo, int hi);
// quickSelect returns the k-th smallest element (0-indexed).
int quickSelect(vector<int>& nums, int k) {
// Like binary search, but we don't know the split point in advance — each
// partition step reveals it. Search the whole array to start.
int lo = 0, hi = (int)nums.size() - 1;
while (lo <= hi) {
// partitionRange rearranges nums[lo..hi] and returns the final index p of
// the pivot: everything left of p is smaller, everything right is larger.
int p = partitionRange(nums, lo, hi);
if (p == k) {
// p is exactly the rank we want, so nums[p] is the k-th smallest.
return nums[p];
} else if (p < k) {
// The answer's rank is higher: discard the left part, search the right.
lo = p + 1;
} else {
// The answer's rank is lower: search only the left part.
hi = p - 1;
}
}
return -1; // k out of range; average O(n) since we recurse into one side only
}
// partitionRange (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.
#include <vector>
using namespace std;
// Declared up front so quickSelect can call it below. Named
// partitionRange because "using namespace std" also puts
// std::partition in scope — same name, different algorithm.
int partitionRange(vector<int>& nums, int lo, int hi);
// quickSelect returns the k-th smallest element (0-indexed).
int quickSelect(vector<int>& nums, int k) {
// Like binary search, but we don't know the split point in advance — each
// partition step reveals it. Search the whole array to start.
int lo = 0, hi = (int)nums.size() - 1;
while (lo <= hi) {
// partitionRange rearranges nums[lo..hi] and returns the final index p of
// the pivot: everything left of p is smaller, everything right is larger.
int p = partitionRange(nums, lo, hi);
if (p == k) {
// p is exactly the rank we want, so nums[p] is the k-th smallest.
return nums[p];
} else if (p < k) {
// The answer's rank is higher: discard the left part, search the right.
lo = p + 1;
} else {
// The answer's rank is lower: search only the left part.
hi = p - 1;
}
}
return -1; // k out of range; average O(n) since we recurse into one side only
}
// partitionRange (Lomuto) puts nums[hi] at its final sorted position and returns it.
int partitionRange(vector<int>& nums, int lo, int hi) {
// Use the last element as the pivot. i marks the boundary: everything in
// nums[lo..i) is known to be < pivot.
int pivot = nums[hi];
int i = lo;
}#include <vector>
using namespace std;
// Declared up front so quickSelect can call it below. Named
// partitionRange because "using namespace std" also puts
// std::partition in scope — same name, different algorithm.
int partitionRange(vector<int>& nums, int lo, int hi);
// quickSelect returns the k-th smallest element (0-indexed).
int quickSelect(vector<int>& nums, int k) {
// Like binary search, but we don't know the split point in advance — each
// partition step reveals it. Search the whole array to start.
int lo = 0, hi = (int)nums.size() - 1;
while (lo <= hi) {
// partitionRange rearranges nums[lo..hi] and returns the final index p of
// the pivot: everything left of p is smaller, everything right is larger.
int p = partitionRange(nums, lo, hi);
if (p == k) {
// p is exactly the rank we want, so nums[p] is the k-th smallest.
return nums[p];
} else if (p < k) {
// The answer's rank is higher: discard the left part, search the right.
lo = p + 1;
} else {
// The answer's rank is lower: search only the left part.
hi = p - 1;
}
}
return -1; // k out of range; average O(n) since we recurse into one side only
}
// partitionRange (Lomuto) puts nums[hi] at its final sorted position and returns it.
int partitionRange(vector<int>& nums, int lo, int hi) {
// Use the last element as the pivot. i marks the boundary: everything in
// nums[lo..i) is known to be < pivot.
int pivot = nums[hi];
int i = lo;
// Sweep j across the range; each value smaller than the pivot gets swapped
// to the boundary and grows the "< pivot" region.
}#include <vector>
using namespace std;
// Declared up front so quickSelect can call it below. Named
// partitionRange because "using namespace std" also puts
// std::partition in scope — same name, different algorithm.
int partitionRange(vector<int>& nums, int lo, int hi);
// quickSelect returns the k-th smallest element (0-indexed).
int quickSelect(vector<int>& nums, int k) {
// Like binary search, but we don't know the split point in advance — each
// partition step reveals it. Search the whole array to start.
int lo = 0, hi = (int)nums.size() - 1;
while (lo <= hi) {
// partitionRange rearranges nums[lo..hi] and returns the final index p of
// the pivot: everything left of p is smaller, everything right is larger.
int p = partitionRange(nums, lo, hi);
if (p == k) {
// p is exactly the rank we want, so nums[p] is the k-th smallest.
return nums[p];
} else if (p < k) {
// The answer's rank is higher: discard the left part, search the right.
lo = p + 1;
} else {
// The answer's rank is lower: search only the left part.
hi = p - 1;
}
}
return -1; // k out of range; average O(n) since we recurse into one side only
}
// partitionRange (Lomuto) puts nums[hi] at its final sorted position and returns it.
int partitionRange(vector<int>& nums, int lo, int hi) {
// Use the last element as the pivot. i marks the boundary: everything in
// nums[lo..i) is known to be < pivot.
int pivot = nums[hi];
int i = lo;
// Sweep j across the range; each value smaller than the pivot gets swapped
// to the boundary and grows the "< pivot" region.
for (int j = lo; j < hi; j++) {
if (nums[j] < pivot) {
swap(nums[i], nums[j]);
i++;
}
}
}#include <vector>
using namespace std;
// Declared up front so quickSelect can call it below. Named
// partitionRange because "using namespace std" also puts
// std::partition in scope — same name, different algorithm.
int partitionRange(vector<int>& nums, int lo, int hi);
// quickSelect returns the k-th smallest element (0-indexed).
int quickSelect(vector<int>& nums, int k) {
// Like binary search, but we don't know the split point in advance — each
// partition step reveals it. Search the whole array to start.
int lo = 0, hi = (int)nums.size() - 1;
while (lo <= hi) {
// partitionRange rearranges nums[lo..hi] and returns the final index p of
// the pivot: everything left of p is smaller, everything right is larger.
int p = partitionRange(nums, lo, hi);
if (p == k) {
// p is exactly the rank we want, so nums[p] is the k-th smallest.
return nums[p];
} else if (p < k) {
// The answer's rank is higher: discard the left part, search the right.
lo = p + 1;
} else {
// The answer's rank is lower: search only the left part.
hi = p - 1;
}
}
return -1; // k out of range; average O(n) since we recurse into one side only
}
// partitionRange (Lomuto) puts nums[hi] at its final sorted position and returns it.
int partitionRange(vector<int>& nums, int lo, int hi) {
// Use the last element as the pivot. i marks the boundary: everything in
// nums[lo..i) is known to be < pivot.
int pivot = nums[hi];
int i = lo;
// Sweep j across the range; each value smaller than the pivot gets swapped
// to the boundary and grows the "< pivot" region.
for (int j = lo; j < hi; j++) {
if (nums[j] < pivot) {
swap(nums[i], nums[j]);
i++;
}
}
// Finally drop the pivot into the boundary slot — its true sorted position.
}#include <vector>
using namespace std;
// Declared up front so quickSelect can call it below. Named
// partitionRange because "using namespace std" also puts
// std::partition in scope — same name, different algorithm.
int partitionRange(vector<int>& nums, int lo, int hi);
// quickSelect returns the k-th smallest element (0-indexed).
int quickSelect(vector<int>& nums, int k) {
// Like binary search, but we don't know the split point in advance — each
// partition step reveals it. Search the whole array to start.
int lo = 0, hi = (int)nums.size() - 1;
while (lo <= hi) {
// partitionRange rearranges nums[lo..hi] and returns the final index p of
// the pivot: everything left of p is smaller, everything right is larger.
int p = partitionRange(nums, lo, hi);
if (p == k) {
// p is exactly the rank we want, so nums[p] is the k-th smallest.
return nums[p];
} else if (p < k) {
// The answer's rank is higher: discard the left part, search the right.
lo = p + 1;
} else {
// The answer's rank is lower: search only the left part.
hi = p - 1;
}
}
return -1; // k out of range; average O(n) since we recurse into one side only
}
// partitionRange (Lomuto) puts nums[hi] at its final sorted position and returns it.
int partitionRange(vector<int>& nums, int lo, int hi) {
// Use the last element as the pivot. i marks the boundary: everything in
// nums[lo..i) is known to be < pivot.
int pivot = nums[hi];
int i = lo;
// Sweep j across the range; each value smaller than the pivot gets swapped
// to the boundary and grows the "< pivot" region.
for (int j = lo; j < hi; j++) {
if (nums[j] < pivot) {
swap(nums[i], nums[j]);
i++;
}
}
// Finally drop the pivot into the boundary slot — its true sorted position.
swap(nums[i], nums[hi]);
return i;
}Tap the left half to go back, the right half to go forward.
Arrow keys or space to navigate · Esc to exit.