Problem

Given a list, sort it using this method: reverse(lst, i, j), which sorts lst from i to j.

Examples

Example 1

1
2
3

Input: lst = [4, 3, 2, 1]
Output: [1, 2, 3, 4]
Explanation: By reversing the entire list ([4, 3, 2, 1]), we get [1, 2, 3, 4]

Example 2

1
2
3

Input: lst = [1, 3, 2, 4]
Output: [1, 2, 3, 4]
Explanation: Reverse the sublist from index 1 to 2 ([1, 3, 2, 4] => [1, 2, 3, 4])

Solution

Method 1 - Help reach smallest or largest element reach right position

To sort a list using only the reverse(lst, i, j) method, we can leverage the properties of the reversal operation to repeatedly find and place the smallest or largest elements in their correct positions. This approach is similar to performing a selection sort but using the provided reversal operation.

Approach

  1. Iterate through the List: For each position in the list, find the correct element to place at that position.
  2. Find Minimum Element: Locate the minimum element from the remaining unsorted portion of the list.
  3. Reverse Sublist: Use the reverse method to move the minimum element to its correct position.
  4. Repeat: Continue this process for the next positions until the entire list is sorted.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

class Solution {
    public void sortList(List<Integer> lst) {
        int n = lst.size();
        for (int i = 0; i < n - 1; i++) {
            int minIdx = i;
            for (int j = i + 1; j < n; j++) {
                if (lst.get(j) < lst.get(minIdx)) {
                    minIdx = j;
                }
            }
            reverse(lst, i, minIdx);
        }
    }

    private void reverse(List<Integer> lst, int i, int j) {
        while (i < j) {
            Collections.swap(lst, i, j);
            i++;
            j--;
        }
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        List<Integer> lst1 = new ArrayList<>(List.of(4, 3, 2, 1));
        sol.sortList(lst1);
        System.out.println(lst1); // Output: [1, 2, 3, 4]

        List<Integer> lst2 = new ArrayList<>(List.of(1, 3, 2, 4));
        sol.sortList(lst2);
        System.out.println(lst2); // Output: [1, 2, 3, 4]
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class Solution:
    def sortList(self, lst: List[int]) -> None:
        n = len(lst)
        for i in range(n - 1):
            min_idx = i
            for j in range(i + 1, n):
                if lst[j] < lst[min_idx]:
                    min_idx = j
            self.reverse(lst, i, min_idx)
    
    def reverse(self, lst: List[int], i: int, j: int) -> None:
        while i < j:
            lst[i], lst[j] = lst[j], lst[i]
            i += 1
            j -= 1

# Example usage
sol = Solution()
lst1 = [4, 3, 2, 1]
sol.sortList(lst1)
print(lst1)  # Output: [1, 2, 3, 4]

lst2 = [1, 3, 2, 4]
sol.sortList(lst2)
print(lst2)  # Output: [1, 2, 3, 4]

Complexity

  • ⏰ Time complexity: O(n^2), where n is the length of the list, due to the nested loops to find the minimum element and reverse operations.
  • 🧺 Space complexity: O(1), since we are sorting the list in place without using additional space.