Make Lexicographically Smallest Array by Swapping Elements

class Solution {
public:
    vector<int> smallestLexicalOrder(vector<int>& arr, int maxDiff) {
        vector<int> sortedArr(arr);
        sort(sortedArr.begin(), sortedArr.end());
        
        int currentGroup = 0;
        unordered_map<int, int> elementToGroup;
        elementToGroup.insert(make_pair(sortedArr[0], currentGroup));

        unordered_map<int, list<int>> groupToElements;
        groupToElements[currentGroup] = list<int>{sortedArr[0]};

        for (int i = 1; i < arr.size(); ++i){
            if (abs(sortedArr[i] - sortedArr[i-1]) > maxDiff) {
                currentGroup++;
            }

            elementToGroup[sortedArr[i]] = currentGroup;
            
            if (groupToElements.find(currentGroup) == groupToElements.end()){
                groupToElements[currentGroup] = list<int>();
            }
            groupToElements[currentGroup].push_back(sortedArr[i]);
        }

        for (int j = 0; j < arr.size(); ++j){
            int element = arr[j];
            int group = elementToGroup[element];
            arr[j] = groupToElements[group].front();
            groupToElements[group].pop_front();
        }

        return arr;
    }
};

The solution involves creating the lexicographically smallest array possible by swapping elements based on a specified maximum difference maxDiff between elements. The code is written in C++ and operates on a vector of integers.

Start by sorting a copy of the input array, sortedArr in non-decreasing order. This helps identify groups of elements that can be swapped. Each group corresponds to elements that are within the maxDiff difference of each other.

• Create a mapping, elementToGroup, that links each element to a group identifier.
• Use another map, groupToElements, to link each group identifier to a list of elements in that group.

Iterate through sortedArr and assign group identifiers. If the difference between consecutive elements exceeds maxDiff, a new group is started. For each element in sortedArr, update elementToGroup and groupToElements accordingly.

Once the groups are established, iterate through the original array. For each element:

1. Retrieve its group using elementToGroup.
2. Swap the current element with the front element of the corresponding group list in groupToElements.
3. Remove that element from the group list to maintain the swapped state.

Finally, return the modified array, which should now be in its lexicographically smallest form achievable within the constraints provided by maxDiff.

This technique ensures that each element is placed in the lowest possible position in the array based on the allowed differences, thus achieving the desired lexicographic order.

class Solution {

    public int[] smallestLexicographicalArray(int[] arr, int threshold) {
        int[] sortedArray = new int[arr.length];
        for (int idx = 0; idx < arr.length; idx++) sortedArray[idx] = arr[idx];
        Arrays.sort(sortedArray);

        int groupNumber = 0;
        HashMap<Integer, Integer> valueToGroupMap = new HashMap<>();
        valueToGroupMap.put(sortedArray[0], groupNumber);

        HashMap<Integer, LinkedList<Integer>> groupToValuesMap = new HashMap<>();
        groupToValuesMap.put(
            groupNumber,
            new LinkedList<Integer>(Arrays.asList(sortedArray[0]))
        );

        for (int idx = 1; idx < arr.length; idx++) {
            if (Math.abs(sortedArray[idx] - sortedArray[idx - 1]) > threshold) {
                groupNumber++;
            }

            valueToGroupMap.put(sortedArray[idx], groupNumber);

            if (!groupToValuesMap.containsKey(groupNumber)) {
                groupToValuesMap.put(groupNumber, new LinkedList<Integer>());
            }
            groupToValuesMap.get(groupNumber).add(sortedArray[idx]);
        }

        for (int idx = 0; idx < arr.length; idx++) {
            int value = arr[idx];
            int group = valueToGroupMap.get(value);
            arr[idx] = groupToValuesMap.get(group).pop();
        }

        return arr;
    }
}

The provided Java solution addresses the problem of rearranging an array to produce the lexicographically smallest array possible, given a specific threshold that determines allowable swaps. The critical aspect of the program is managing swaps that do not exceed a defined threshold between the differences of element values.

Here's how the logic of the solution flows:

• Start by copying and sorting the original array elements into a new array, sortedArray, which aids in the grouping process.
• Utilize two hash maps:
  • valueToGroupMap stores the group assignment for each value based on the sorted sequence.
  • groupToValuesMap maps each group number to a list of values that belong to this group.
• The array values are grouped based on the difference between consecutive elements in the sorted array. If the difference exceeds the threshold, a new group starts.
• Each value in the original array is replaced sequentially using the smallest available element (popped from the linked list) from the corresponding group, which ensures the smallest lexicographical order based on allowed swaps.

By maintaining a threshold-defined grouping of array values, the solution strategically swaps elements within groups to achieve the smallest lexicographical sequence. This uses the arrangement properties of sorted arrays and the swift access and modification capabilities of hash maps and linked lists. Consequently, the output array is reformed to reflect these swaps, resulting in the desired smallest form.

class Solution:
    def smallestLexArray(self, numbers, threshold):
        sorted_numbers = sorted(numbers)

        current_index = 0
        number_to_index = {}
        number_to_index[sorted_numbers[0]] = current_index

        index_to_deque = {}
        index_to_deque[current_index] = deque([sorted_numbers[0]])

        for j in range(1, len(numbers)):
            if abs(sorted_numbers[j] - sorted_numbers[j - 1]) > threshold:
                # increment index
                current_index += 1

            # map current number to the corresponding index
            number_to_index[sorted_numbers[j]] = current_index

            # add current number to the appropriate deque
            if current_index not in index_to_deque:
                index_to_deque[current_index] = deque()
            index_to_deque[current_index].append(sorted_numbers[j])

        # replace original numbers with dequeued elements
        for k in range(len(numbers)):
            element = numbers[k]
            idx = number_to_index[element]
            numbers[k] = index_to_deque[idx].popleft()

        return numbers

The provided Python3 solution focuses on creating the lexicographically smallest array possible, based on a specific swapping process governed by a given threshold. The task is accomplished by managing sortable elements with constraints. Below, the key operations of the solution are detailed:

• Sort the given array to facilitate ordered access to elements.
• Initialize mappings to correlate sorted elements to their original positions, making use of a dictionary for number-to-index mapping and a deque for ordered element retrieval based on indexes.
• Iterate over the sorted numbers:
  • Evaluate the difference between consecutive sorted elements to determine if it surpasses the specified threshold. If true, proceed with incrementing the index marker, segregating elements into deques where their differences do not exceed the threshold.
  • Maintain a dictionary mapping from each element's value to its index and another mapping from each index to a deque containing the elements.
• Replace the elements in the original array by sequentially popping elements from the corresponding deques, ensuring elements are placed smallest to largest within constraints set by the threshold.

By following these steps, the function reads and adjusts the input array, ensuring that it generates the smallest lexicographical order possible under the constraints provided. This technique effectively leverages sorting, dictionary mappings, and deques to achieve the desired array arrangement.