Given 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].

```
func findMinArray(arr: [Int], k: Int) -> [Int] {
var newArray = arr
var newK = k
// iterate through the number of swaps available
while newK > 0 {
// find the minimum available element from first index to kth index
var minimumElement = Int.max
for current in 1...newK {
print(current)
if current < newArray.count && newArray[current] < minimumElement {
minimumElement = newArray[current]
}
}
print("newK", newK)
// important
// swap this minimum element with the previous element
// since we can only swap adjacent elements
if newK < newArray.count {
newArray.swapAt(newK-1, newK)
}
newK -= 1
}
return newArray;
}
var arr = [5,3,1]
//var arr = [8, 9, 11, 2, 1]
print(findMinArray(arr: arr, k: 3))
```

## Leave a Reply