Implement insertion sort and record its progress. Starting from index 1, take each element in turn and slide it left past every element that is strictly greater than it, so that the prefix nums[0..i] becomes sorted. After each element i = 1, 2, ..., n-1 has been inserted, append a copy of the whole list to the output.
Return the list of snapshots. For lists with fewer than two elements return []. Do not modify the input.
Examples
Input: nums = [3, 1, 2]
Output: [[1, 3, 2], [1, 2, 3]]
Explanation: Inserting 1 gives [1, 3, 2]; inserting 2 gives [1, 2, 3].
Input: nums = [2, 2, 1]
Output: [[2, 2, 1], [1, 2, 2]]
Explanation: The second 2 does not move past the first 2 (it is not strictly smaller).
Constraints
0 <= len(nums) <= 200- Exactly
max(0, n - 1)snapshots, each a full copy of the list at that moment. - Target complexity: O(n^2) comparisons, O(n^2) output size.
Goals
- Implement insertion sort by shifting larger elements to the right
- Record the state of the list after each insertion
- Keep equal elements in their original relative order