2948. Make Lexicographically Smallest Array by Swapping Elements

[mah-shamim]

Topics: Array, Union Find, Sorting

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.

Example 1:

• 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.

Example 2:

• 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.

Example 3:

• 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 <= 105
• 1 <= nums[i] <= 109
• 1 <= limit <= 109

Hint:

1. Construct a virtual graph where all elements in nums are nodes and the pairs satisfying the condition have an edge between them.
2. Instead of constructing all edges, we only care about the connected components.
3. Can we use DSU?
4. Sort nums. Now we just need to consider if the consecutive elements have an edge to check if they belong to the same connected component. Hence, all connected components become a list of position-consecutive elements after sorting.
5. For each index of nums from 0 to nums.length - 1 we can change it to the current minimum value we have in its connected component and remove that value from the connected component.

[mah-shamim]

The problem asks us to find the lexicographically smallest array by swapping elements of an array, subject to a condition. Specifically, we can only swap two elements nums[i] and nums[j] if the absolute difference between them (|nums[i] - nums[j]|) is less than or equal to a given limit.

Key Points

1. Lexicographical Order: An array a is lexicographically smaller than b if at the first differing index, a[i] < b[i].
2. Swapping Condition: Swaps are only allowed if the difference between the numbers being swapped is ≤ limit.
3. Efficient Grouping: By using Disjoint Set Union (DSU) or sorting techniques, we can group elements that are connected by valid swaps.
4. Optimal Arrangement: For each group, sort the indices and values to achieve the smallest order.

Approach

1. Construct Groups: Treat the array as a virtual graph, where valid swaps define the edges. Use sorting to identify connected groups or DSU to group indices efficiently.
2. Sort Groups: Within each group of connected indices, rearrange the elements in lexicographical order.
3. Output Construction: Place the sorted values back into their respective positions.

Plan

1. Extract (value, index) pairs and sort them by value to enable efficient group detection.
2. Iterate through sorted values to form groups of indices that are connected based on the limit condition.
3. For each group:
   • Sort indices and values independently.
   • Reassign values to their original positions in lexicographical order.
4. Return the modified array.

Let's implement this solution in PHP: 2948. Make Lexicographically Smallest Array by Swapping Elements

<?php
/**
 * @param Integer[] $nums
 * @param Integer $limit
 * @return Integer[]
 */
function lexicographicallySmallestArray($nums, $limit) {
    $n = count($nums);
    $ans = array_fill(0, $n, 0);

    // Get pairs of (num, index), sorted by num
    $numAndIndexes = $this->getNumAndIndexes($nums);

    // Groups of [(num, index)] where the difference between numbers <= limit
    $numAndIndexesGroups = [];

    foreach ($numAndIndexes as $numAndIndex) {
        if (empty($numAndIndexesGroups) ||
            $numAndIndex[0] - end($numAndIndexesGroups[count($numAndIndexesGroups) - 1])[0] > $limit) {
            // Start a new group
            $numAndIndexesGroups[] = [$numAndIndex];
        } else {
            // Append to the existing group
            $numAndIndexesGroups[count($numAndIndexesGroups) - 1][] = $numAndIndex;
        }
    }

    // Sort each group and place the values in the correct positions
    foreach ($numAndIndexesGroups as $numAndIndexesGroup) {
        $sortedNums = [];
        $sortedIndices = [];

        foreach ($numAndIndexesGroup as $pair) {
            $sortedNums[] = $pair[0];
            $sortedIndices[] = $pair[1];
        }

        // Sort the indices and the values independently
        sort($sortedNums);
        sort($sortedIndices);

        // Assign sorted values to the respective indices in the answer
        for ($i = 0; $i < count($sortedNums); $i++) {
            $ans[$sortedIndices[$i]] = $sortedNums[$i];
        }
    }

    return $ans;
}

/**
 * @param $nums
 * @return array
 */
function getNumAndIndexes($nums) {
    $numAndIndexes = [];
    foreach ($nums as $index => $num) {
        $numAndIndexes[] = [$num, $index];
    }
    usort($numAndIndexes, function($a, $b) {
        return $a[0] <=> $b[0];
    });
    return $numAndIndexes;
}

// Example usage:
$nums1 = [1, 5, 3, 9, 8];
$limit1 = 2;
print_r(lexicographicallySmallestArray($nums1, $limit1)); // Output: [1, 3, 5, 8, 9]

$nums2 = [1, 7, 6, 18, 2, 1];
$limit2 = 3;
print_r(lexicographicallySmallestArray($nums2, $limit2)); // Output: [1, 6, 7, 18, 1, 2]

$nums3 = [1, 7, 28, 19, 10];
$limit3 = 3;
print_r(lexicographicallySmallestArray($nums3, $limit3)); // Output: [1, 7, 28, 19, 10]

$nums4 = [1, 60, 34, 84, 62, 56, 39, 76, 49, 38];
$limit4 = 4;
print_r(lexicographicallySmallestArray($nums4, $limit4)); // Output: [1, 56, 34, 84, 60, 62, 38, 76, 49, 39]
?>

Explanation:

1. Extracting and Sorting (getNumAndIndexes):

   • Combine values and indices into pairs for easy reference.
   • Sort the pairs by value to enable efficient grouping of connected components.

2. Grouping Logic:

   • Traverse the sorted pairs. If the difference between consecutive values is ≤ limit, add them to the same group; otherwise, start a new group.

3. Sorting and Reassigning:

   • For each group:
     • Extract the indices and values.
     • Sort both lists to ensure the smallest values are placed in the smallest indices.
     • Reassign the sorted values to their respective positions in the answer array.

4. Result Construction:

   • After processing all groups, return the updated array.

Example Walkthrough

Example 1

Input: nums = [1,5,3,9,8], limit = 2

1. Extract and Sort:

   • Pairs: [(1, 0), (5, 1), (3, 2), (9, 3), (8, 4)]
   • Sorted Pairs: [(1, 0), (3, 2), (5, 1), (8, 4), (9, 3)]

2. Grouping:

   • Group 1: [(1, 0)]
   • Group 2: [(3, 2), (5, 1)]
   • Group 3: [(8, 4), (9, 3)]

3. Sorting Groups:

   • Group 1: No change ([1])
   • Group 2: Values = [3, 5], Indices = [1, 2] → Result: [1, 3, 5]
   • Group 3: Values = [8, 9], Indices = [3, 4] → Result: [8, 9]

4. Final Result: [1, 3, 5, 8, 9]

Time Complexity

1. Sorting: Sorting the nums array takes O(n log n).
2. Grouping: Linear traversal through the sorted array takes O(n).
3. Sorting Groups: Sorting indices and values for each group takes O(k log k), where k is the group size. Summed over all groups, this is O(n log n).

Overall Time Complexity: O(n log n)

Output for Examples

Example 2

Input: nums = [1,7,6,18,2,1], limit = 3
Output: [1,6,7,18,1,2]

Example 3

Input: nums = [1,7,28,19,10], limit = 3
Output: [1,7,28,19,10]

This approach efficiently handles the problem by using sorting to identify connected components and rearranging values within each component to achieve the lexicographically smallest array. By leveraging sorting and group processing, we ensure an optimal solution with O(n log n) complexity.

[kovatz]

Thanks for solving the problem of "Make Lexicographically Smallest Array by Swapping Elements"

[mah-shamim]

Thanks