Smallest Array Reachable Through Value-Limited Swaps
Company: Goldman Sachs
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Other
# Smallest Array Reachable Through Value-Limited Swaps
You are given a 0-indexed array of positive integers `nums` and a positive integer `limit`.
In one operation, choose any two indices `i` and `j` and swap their current values if `|nums[i] - nums[j]| <= limit`. The indices need not be adjacent.
Return the lexicographically smallest array obtainable after any number of operations, including zero. An array is lexicographically smaller than another if its value is smaller at the first position where they differ.
### Examples
**Example 1**
```text
Input: nums = [8,2,6,4], limit = 2
Output: [2,4,6,8]
```
A legal sequence is `[8,2,6,4] -> [6,2,8,4] -> [4,2,8,6] -> [2,4,8,6] -> [2,4,6,8]`. Each swapped pair differs by exactly `2`. Although `8` and `2` cannot be swapped directly, intermediate values allow the globally sorted array to be reached, which is lexicographically minimal.
**Example 2**
```text
Input: nums = [9,3,8,1,12], limit = 2
Output: [8,1,9,3,12]
```
Swap values `9` and `8`, then values `3` and `1`. The values `1` and `3` can occupy only indices `1` and `3`; values `8` and `9` can occupy only indices `0` and `2`; `12` cannot exchange with any other value. Putting each smaller value at the earlier available index gives the result.
### Constraints
- `1 <= nums.length <= 10^5`.
- `1 <= nums[i] <= 10^9`.
- `1 <= limit <= 10^9`.
### Clarifying Questions
- Are only adjacent positions eligible? No; any two indices may be chosen if their current values meet the difference condition.
- Is equality with `limit` allowed? Yes; the comparison is inclusive.
- Is eligibility determined once from original positions? No; each operation uses the values currently at the chosen positions.
- Can equal values occur? Yes; no uniqueness guarantee is given.
- Is an in-place result required? The source asks for a returned array and specifies no in-place requirement; retain the original C++ interface.
### C++ Interface
```cpp
class Solution {
public:
vector<int> lexicographicallySmallestArray(vector<int>& nums, int limit) {
}
};
```
### Reasoning Checkpoints
- Distinguish a directly legal swap from values that can exchange positions through intermediate operations.
- Justify which values can reach each original position.
- Explain why the returned arrangement is lexicographically minimal while preserving all values and multiplicities.
```hint Connect values rather than fixed positions
Treat each element occurrence as a token with a fixed value. Two tokens can exchange their current positions if their values differ by at most limit. Sort values to identify the connected groups, then consider which values should occupy each group's earliest indices.
```
Overview: Return the lexicographically smallest array reachable by swapping any two current values whose absolute difference is at most the given positive limit.