Kth Greatest Element in Prefixes - Atlassian IIT Roorkee Online Assessment OA

Problem Preview

"### Problem You are given a permutation of integers from 1 to n stored in an array arr, and an integer k. The ith greatest element of an array is the ith element when sorted in decreasing order. For each prefix of the array of length i (where i ranges from k to n), find the kth greatest element. ### Hint: Try to think about min-heap ### Input - int arr[n] : a permutation of n integers - int k : the rank of the element to find ### Output - int[n - k + 1] : answers for each ith prefix in the range [k, n]. ### Example n = 4 k = 2 arr = [4, 2, 1, 3] Find the 2nd greatest element for each prefix of size i ≥ k: - i = 2, arr = [4, 2] → The 2nd greatest element is 2 - i = 3, arr = [4, 2, 1] → The 2nd greatest element is 2 - i = 4, arr = [4, 2, 1, 3] → The 2nd greatest element is 3 Return the array [2, 2, 3]."