Categories

Element SwappingGiven a sequence of n integers arr, determine the lexicographically smallest sequence which may be obtained from it after performing at most k element swaps, each involving a pair of consecutive elements in the sequence.Note: A list x is lexicographically smaller than a different equal-length list y if and only if, for the earliest index at which the two lists differ, x’s element at that index is smaller than y’s element at that index.

### Signature

int[] findMinArray(int[] arr, int k)

### Input

n is in the range [1, 1000]. Each element of arr is in the range [1, 1,000,000]. k is in the range [1, 1000].

### Output

Return an array of n integers output, the lexicographically smallest sequence achievable after at most k swaps.

### Example 1

n = 3 k = 2 arr = [5, 3, 1] output = [1, 5, 3]We can swap the 2nd and 3rd elements, followed by the 1st and 2nd elements, to end up with the sequence [1, 5, 3]. This is the lexicographically smallest sequence achievable after at most 2 swaps.

### Example 2

n = 5 k = 3 arr = [8, 9, 11, 2, 1] output = [2, 8, 9, 11, 1]We can swap [11, 2], followed by [9, 2], then [8, 2].

``````   function findMinArray(array \$arr, int \$k) : array
{
#arr = [5, 3, 1]
# k:2, 1
while(\$k >= 1)
{

# swapping
\$temp = \$arr[\$k];        # temp 1      ; 1
\$arr[\$k] = \$arr[\$k - 1]; # \$arr[2] = 3; \$arr[1] = 5
\$arr[\$k - 1] = \$temp;    # \$arr[1] = 1; \$arr[0] = 1

#arr = [5, 1, 3]
#arr = [1, 5, 3]
\$k--; #1 #0
}

return \$arr;

}``````