Make Lexicographically Smallest Array by Swapping Elements — LeetCode 2948 Python Solution
MediumUnion FindArraySorting
- Problem
- #2948
- Pattern
- Union-Find
- Reading time
- 3 min
- Source
- leetcode.com
The 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.
Example
- Input
- nums = [1,5,3,9,8], limit = 2
- Output
- [1,3,5,8,9]
- Explanation
- Apply the operation 2 times:
Python solution
Python
class Solution:
def lexicographicallySmallestArray(self, nums: List[int], limit: int) -> List[int]:
n = len(nums)
arr = sorted(zip(nums, range(n)))
ans = [0] * n
i = 0
while i < n:
j = i + 1
while j < n and arr[j][0] - arr[j - 1][0] <= limit:
j += 1
idx = sorted(k for _, k in arr[i:j])
for k, (x, _) in zip(idx, arr[i:j]):
ans[k] = x
i = j
return ansComplexity
| Measure | Complexity |
|---|---|
| Time | Near O(n) (amortized) |
| Space | O(n) auxiliary |
Pattern: Union-Find
Merge groups and ask whether two things are connected, both in near-constant time. LeetCode 2948. Make Lexicographically Smallest Array by Swapping Elements is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Union Find.
The union-find guide has the Python template for the pattern and the 83 LeetCode problems that use it.
Related problems
Frequently asked questions
- How hard is LeetCode 2948. Make Lexicographically Smallest Array by Swapping Elements?
- LeetCode 2948. Make Lexicographically Smallest Array by Swapping Elements is rated Medium on LeetCode.
- What is the time complexity of LeetCode 2948. Make Lexicographically Smallest Array by Swapping Elements?
- The Python solution on this page runs in Near O(n) (amortized).
- What is the space complexity of LeetCode 2948. Make Lexicographically Smallest Array by Swapping Elements?
- The Python solution on this page uses O(n) auxiliary space.
- What topics does LeetCode 2948. Make Lexicographically Smallest Array by Swapping Elements cover?
- LeetCode 2948. Make Lexicographically Smallest Array by Swapping Elements is tagged Union Find, Array and Sorting on LeetCode.