> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# Make Lexicographically Smallest Array by

> Tested Python solution for LeetCode 2948 with 18 pytest cases. Generate a practice environment with lcpy.

LeetCode 2948, [Medium](/catalog/medium). Topics: [Array](/catalog/topics/array), [Union-Find](/catalog/topics/union-find), [Sorting](/catalog/topics/sorting). [View on LeetCode](https://leetcode.com/problems/make-lexicographically-smallest-array-by-swapping-elements/description/).

Generate this problem as a practice environment: tested reference solution, 18 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 2948   # by problem number
lcpy gen -s make_lexicographically_smallest_array_by_swapping_elements   # by problem name
```

## Problem

You are given a 0-indexed array of positive integers `nums` and a positive integer `limit`.

In one operation, you can choose any two indices `i` and `j` and swap `nums[i]` and `nums[j]` **if** `|nums[i] - nums[j]| <= limit`.

Return the lexicographically smallest array that can be obtained by performing the operation any number of times.

An array `a` is lexicographically smaller than an array `b` if in the first position where `a` and `b` differ, array `a` has an element that is less than the corresponding element in `b`. For example, the array `[2,10,3]` is lexicographically smaller than the array `[10,2,3]` because they differ at index `0` and `2 < 10`.

### Examples

```
Input: nums = [1,5,3,9,8], limit = 2
Output: [1,3,5,8,9]
Explanation: Apply the operation 2 times:
- Swap nums[1] with nums[2]. The array becomes [1,3,5,9,8]
- Swap nums[3] with nums[4]. The array becomes [1,3,5,8,9]
We cannot obtain a lexicographically smaller array by applying any more operations.
Note that it may be possible to get the same result by doing different operations.
```

```
Input: nums = [1,7,6,18,2,1], limit = 3
Output: [1,6,7,18,1,2]
Explanation: Apply the operation 3 times:
- Swap nums[1] with nums[2]. The array becomes [1,6,7,18,2,1]
- Swap nums[0] with nums[4]. The array becomes [2,6,7,18,1,1]
- Swap nums[0] with nums[5]. The array becomes [1,6,7,18,1,2]
We cannot obtain a lexicographically smaller array by applying any more operations.
```

```
Input: nums = [1,7,28,19,10], limit = 3
Output: [1,7,28,19,10]
Explanation: [1,7,28,19,10] is the lexicographically smallest array we can obtain because we cannot apply the operation on any two indices.
```

### Constraints

* `1 <= nums.length <= 10^5`
* `1 <= nums[i] <= 10^9`
* `1 <= limit <= 10^9`

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/make_lexicographically_smallest_array_by_swapping_elements/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/make_lexicographically_smallest_array_by_swapping_elements/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
from itertools import pairwise


class Solution:
    # Time: O(n log n)
    # Space: O(n)
    def lexicographically_smallest_array(self, nums: list[int], limit: int) -> list[int]:
        order = sorted(range(len(nums)), key=lambda i: nums[i])
        result: list[int] = [0] * len(nums)
        group: list[int] = [order[0]]
        for prev, idx in pairwise(order):
            if nums[idx] - nums[prev] > limit:
                self._assign_group(result, group, nums)
                group = []
            group.append(idx)
        self._assign_group(result, group, nums)
        return result

    def _assign_group(self, result: list[int], indices: list[int], nums: list[int]) -> None:
        values = sorted(nums[i] for i in indices)
        for pos, val in zip(sorted(indices), values, strict=True):
            result[pos] = val
```

## Complexity

| Time | Space |
| - | - |
| O(n log n) | O(n) |

## Tags

[NeetCode All](/catalog/neetcode).


This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.