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]