SDE - 1

You have been given an array/list ARR consisting of ‘N’ integers. You are also given a positive integer ‘K’.

Your task is to find the lexicographically smallest ARR that can be obtained by swapping at most K consecutive elements.

An array/list P is lexicographically smaller than its permutation Q if and only if, for the earliest index at which P and Q differ, P's element at that index is smaller than Q's element at that index. Example, P = [1, 12, 4, 7, 8] is lexicographically smaller than Q = [1, 12, 8, 4, 7].

For example, if ARR = [70, 60, 90, 21, 11] and K = 3, then-

Swap 1: We swap adjacent elements 90 and 21. So, ARR after one swap is [70, 60, 21, 90, 11].
Swap 2: We swap adjacent elements 60 and 21. So, ARR after one swap is [70, 21, 60, 90, 11].
Swap 3: We swap adjacent elements 70 and 21. So, ARR after one swap is [21, 70, 60, 90, 11].
The lexicographically smallest ARR after K = 3 swaps is [21, 70, 60, 90, 11].

Who is your role model?

Why should we hire you?