Here is the question at hand
Given a sequence of n integers arr, find the smallest possible lexicographic sequence that can be obtained after performing a maximum of k element swaps, where each swap involves two consecutive elements in the sequence.
Note: For two lists x and y of equal length, x is considered lexicographically smaller than y if, at the earliest differing index between the two lists, x's element at that index is smaller than y's element at that index.
I am trying to understand the concept of being "lexicographically smaller" based on the explanation provided above. From what I comprehend, it seems to refer to an order similar to how words are arranged in a dictionary. To illustrate my question further, let's consider an example.
Let's take a look at this instance
Example 1
n = 3
k = 2
arr = [5, 3, 1]
output = [1, 5, 3]
By swapping the 2nd and 3rd elements first, followed by the 1st and 2nd elements, we arrive at the sequence [1, 5, 3]. This represents the lexicographically smallest sequence achievable within a limit of 2 swaps.
The given example raised a question for me. Shouldn't the lexicographically smallest sequence actually be [1, 3 , 5] instead of the suggested output [1, 5, 3]?
Another scenario to consider
Example 2
n = 5
k = 3
arr = [8, 9, 11, 2, 1]
output = [2, 8, 9, 11, 1]
Through the swaps [11, 2], [9, 2], and [8, 2], we reach the final sequence [2, 8, 9, 11, 1].
In this case as well, after three swaps, the smallest lexicographic sequence appears to be [1, 2, 8, 11, 9] despite the specified output being [2, 8, 9, 11, 1].
Could there be a misinterpretation in my understanding of the problem statement?