Hello frends, in this blog I teach you how to find k_th element in an array of size n. This blog is going be very advanced so please if you are new to progrmaming stay away.
eg. arr = {1, 3, 2, 9, 5, 6, 11} and k = 2 then programs must return 3
Approach:
Define dp(i, j, k) = number of inversions in the array formed by concatenating prefix arr[0 .. i] and arr[j .. n-1] such that the smaller number in the inversion pair is >= k (0 <= i < j < n)
The transitions is trivial, so I am skipping those.
then the answer can be found by returning the value of arr[k — 1]
sir you can just use quick select, it can be reduced to $$$O(n)$$$ and a variant of it (introselect) exists in C++ STL as
nth_elementNo madam, quickselect is very slow algrothm O(N^2) worst case. my algrothm works in O(1) worst case.
no sir if you really wanted queries on selecting kth elements you really should've better sorted the array
madam 😭