Find the lexicographically smallest sequence achievable

Question

Here's the problem statement

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.

I'm trying to wrap my head around the what the phrase "lexicographically smaller" implies based on the above note. As I understand the English meaning of it, we are basically talking about a dictionary order. Let me explain my question with an example.

Here an example

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.

The above example came with the problem statement. But wouldn't the lexicographically smallest sequence instead be [1, 3 , 5] instead of the provided answer (output) [1, 4, 3]?

Here's another

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

Again, the answer I can see in this case is [1, 2, 8, 11, 9] (after three swaps), which is the smallest lexicographic ally and the provided answer is output = [2, 8, 9, 11, 1].

Am I reading the the problem statement incorrectly?

Answer 1

The problem statement says that we are allowed to make at most k swaps of consecutive elements in the process to get a lexicographically smallest sequence. The following explanation can help us understand it better. [NOTE: keep in mind that you can only swap consecutive elements]

1. n = 3
   k = 2
   arr = [5, 3, 1]
   output = [1, 5, 3]
   Approach:
   swap 1: swap 3 and 1 (3<->1) ====> [5,1,3]
   swap 2: swap 5 and 1 (5<->1) ====> [1,5,3] #RESULT
   
2. n = 5
   k = 3
   arr = [8, 9, 11, 2, 1]
   output = [2, 8, 9, 11, 1]
   Approach:
   swap 1: swap 11 and 2 (11<->2) ===> [8, 9, 2, 11, 1]
   swap 2: swap 9 and 2 (9<->2) ===> [8, 2, 9, 11, 1]
   swap 2: swap 8 and 2 (9<->2) ===> [2, 8, 9, 11, 1] #RESULT
   

So, you can never get [1, 2, 8, 11, 9] with 3 swaps of consecutive elements. 2 is the smallest element that you can move to the first index with at most 3 swaps of consecutive elements, but yes if k=4 then we can bring 1 to the first position.

So, the thing that you are missing is that the rule is you are allowed to swap at most k elements but the elements those you swap should be consecutive to each other.