# O(N) with Quick Select

• This is a classic quick select problem.

Note:

There is a notable improvements to randomised inputs. I forgot to shuffle the `nums` in my first attempt, ending up 2000+ms. Then I added the shuffle method, getting 98ms.

A little wrap-up for myself:

1. In this case, without shuffling, it's O(N) average, but O(N^2) in worst case. With shuffling, it guarantees O(N) in worst case.
2. Always remember to shuffle when using the 'quick' family algorithms
``````  def find_kth_largest(nums, k)
shuffle!(nums)

k -= 1
# kth largest is the (length-1-k)th smallest
k = nums.count - 1 - k

lo, hi = 0, nums.count-1

loop do
break if lo >= hi
j = partition(nums, lo, hi)

if j == k
return nums[k]
elsif j < k
lo = j + 1
else
hi = j - 1
end
end

nums[k]
end

def shuffle!(nums)
(1..nums.count-1).each do |i|
j = rand(i+1)
swap(nums, i, j)
end
end

def partition(array, lo, hi)
v = lo
i, j = lo, hi+1

loop do
loop do
i += 1
break if i == hi or array[i] >= array[v]
end

loop do
j -= 1
break if j == lo or array[j] <= array[v]
end

break if i >= j
swap(array, i, j)
end

swap(array, j, v)
return j
end

def swap(array, i, j)
t = array[i]; array[i] = array[j]; array[j] = t
end

``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.