⚡Flashcard Drill➔
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

  1. 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.
  2. Sort the values; a run of values where each consecutive gap is at most limit forms one component.
  3. Within a component, any permutation is reachable, so the smallest values should go to the smallest original positions.
  4. 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 nums in 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.
🎯 Drill This Card Now➔

🧩 Related Greedy Problems