Example in Python

results = []

a = [1,5,4,3,7,2]
a_new = [(1,0), (5,1), (4,2), (3,3), (7,4), (2,5)] #(5,1) -> 5:value and 1:index
sort a_new by value # e.g. mergesort O(nlogn)
start_index = 0
end_index = len(a_new) - 1
i = -1
j = -1
diff = 0

while true: # sequential search
    if(a_new[start_index][1] < a_new[end_index][1]): #compare i and j
        tmp_diff = a_new[end_index][0] - a_new[start_index][0]
        i = start_index
        j = end_index
        diff = tmp_diff
        results.append((I,j,diff)) #add a tuple in results_list
        end_index -= 1
    else: # a_new[start_index][1] > a_new[end_index][1]
        start_index += 1
      
    if start_index == end_index: break

sort results by diff and return results[k-1]

I hope this help. I can't check typing error.

My Idea is: max difference is -> max_possible_element_value - min_element_value

You could run 2 separate methods that finds the max and min of the corresponding arrays then find the difference.

OR

You can use your method of creating a new array that finds the difference of every single value THEN find the max of that array and output that.

Then use Array sort() method to reorder an array and print out the values of max differences when called by index+1

Pseudocode-wise, it could go this way :

You can sort the current array descending, then start your calculation like so :

diffList = {}

calculate(array,k) :

    if (k<=0) OR (array.length < 2) OR (k > 2^(array.length-1))
        return nothing // whatever behavior you want (exception or null Integer whatever suits you)
    else
        return kthLargest(k, 0 , array.length-1, array)
    end if

kthLargest(count, upperBound, lowerBound, array) :
    if count = 0
        if upperBound != lowerBound
            return max(array[upperBound]-array[lowerBound], max(sortDesc(diffList)))
        else
            return max(sort(diffList))
        end if
    else if upperBound = lowerBound
        sortDesc(diffList)
        return diffList[count]
    else
        topDiff = array[upperBound]-array[upperBound+1]
        botDiff = array[lowerBound-1]-array[lowerbound]
        if(topDiff > botDiff)
            add botDiff to diffList
            return kthLargest(count-1,upperBound,lowerBound-1,array)
        else
            add topDiff to diffList
            return kthLargest(count-1,upperBound+1,lowerBound,array)
        end if
    end if

Call calculate(array,k) and you're set.

This basically keeps track of a 'discarded pile' of differences while iterating and reducing bounds to always have your final largest difference be the current bounds' difference or a potential better value in that discarded pile.

Both sorts (omitted for brevity) should make this O(n log n).

You can substitute arrays for the most convenient collections, and unwrap this into an iterative solution also.

Corrections appreciated!

Sample:

results = []

a_new = [(1,0), (2,5), (3,3), (4,2), (5,1), (7,4)]

start_index = 0
end_index = len(a_new) - 1

i = -1
j = -1
diff = 0

while True:
    if(a_new[start_index][1] < a_new[end_index][1]):
        i = a_new[start_index][1]
        j = a_new[end_index][1]
        diff = a_new[end_index][0] - a_new[start_index][0]
        results.append((i, j, diff))
        end_index -= 1
    else:
        start_index -= -1

    if start_index == end_index: break

print(results)

Result:

[(0, 4, 6), (0, 1, 4), (0, 2, 3), (0, 3, 2), (0, 5, 1)]

you can sort the result array then get kth diff.

It can be done in complexity O( N * logN + N * logValMax ). First lets sort the array. After that we can build a function countSmallerDiffs( x ) which counts how many differences smaller or equal to x are in the array, this function has complexity O( N ) using two pointers. After that we can binary search the result in range minVal-maxVal. We need to find p such that satisfies countSmallerDiffs( p ) <= k < countSmallerDiffs( p + 1 ). The answer will be p.

Hope this helps you out! Good luck!