NeetCode #801LC-2948MediumGreedy
← Back to All Problems#801 · #2948 · Make Lexicographically Smallest Array by Swapping Elements(交换得到字典序最小的数组)
📌 Problem Statement & Constraints
Given an array
nums and an integer limit, you may swap nums[i] and nums[j] any number of times if |nums[i] - nums[j]| <= limit. Return the lexicographically smallest array obtainable. Constraints: 1 <= nums.length <= 10^5, 1 <= nums[i], limit <= 10^9.💡 Core Algorithmic Approaches
- Two values are mutually swappable if the difference is at most
limit; swaps chain, so the reachable set is a connected component under this relation. - Sort the values; a run of values where each consecutive gap is at most
limitforms one component. - Within a component, any permutation is reachable, so the smallest values should go to the smallest original positions.
- Assign the component's sorted values to the component's sorted original indices.
💻 Benchmark Python3 Implementation
class Solution:
def lexicographicallySmallestArray(self, nums: List[int], limit: int) -> List[int]:
n = len(nums)
order = sorted(range(n), key=lambda i: nums[i])
res = [0] * n
i = 0
while i < n:
j = i
while j + 1 < n and nums[order[j + 1]] - nums[order[j]] <= limit:
j += 1
group = sorted(order[i:j + 1]) # original indices, ascending
vals = sorted(nums[k] for k in order[i:j + 1])
for pos, v in zip(group, vals):
res[pos] = v
i = j + 1
return res⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n log n): sorting the indices and the groups.
💾 Space Complexity
O(n): the index order and result arrays.
⚠️ Interview Pitfalls & Follow-ups
- Grouping by value difference from the component minimum: the relation is transitive through chains, so consecutive gaps define the components.
- Sorting the values but not the original positions: the smallest value must land on the smallest index within the component.
- Assuming any two values within a component are directly swappable: only chains connect them, but the chain argument still allows any permutation.
- Mutating
numsin place and reading stale values: build the result in a separate array.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.