2948. Make Lexicographically Smallest Array by Swapping Elements

class Solution {
    public int[] lexicographicallySmallestArray(int[] nums, int limit) {
        int n = nums.length;
        
        // Step 1: index array banao aur value ke basis par sort karo
        Integer[] idx = new Integer[n];
        for (int i = 0; i < n; i++) idx[i] = i;
        Arrays.sort(idx, (a, b) -> nums[a] - nums[b]);
        
        int[] result = new int[n];
        
        // Step 2: Groups banao - consecutive sorted elements jinka diff <= limit
        int i = 0;
        while (i < n) {
            int j = i + 1;
            
            // Group extend karo jab tak consecutive sorted values ka diff <= limit
            while (j < n && nums[idx[j]] - nums[idx[j-1]] <= limit) {
                j++;
            }
            
            // Group: idx[i..j-1]
            // In indices ko sort karo (original positions)
            // Aur sorted values assign karo in sorted positions par
            
            // Group ke original indices nikalo
            List<Integer> groupIndices = new ArrayList<>();
            for (int k = i; k < j; k++) {
                groupIndices.add(idx[k]);
            }
            
            // Positions sort karo
            Collections.sort(groupIndices);
            
            // Sorted positions par sorted values assign karo
            for (int k = 0; k < groupIndices.size(); k++) {
                result[groupIndices.get(k)] = nums[idx[i + k]];
            }
            
            i = j;
        }
        
        return result;
    }
}

class Solution:
    def lexicographicallySmallestArray(self, nums, limit):
        n = len(nums)

        # Sort indices based on their values
        idx = list(range(n))
        idx.sort(key=lambda i: nums[i])

        result = [0] * n

        i = 0

        while i < n:
            j = i + 1

            # Find the current group
            while j < n and nums[idx[j]] - nums[idx[j - 1]] <= limit:
                j += 1

            # Get original positions
            group_indices = idx[i:j]
            group_indices.sort()

            # Assign sorted values to sorted positions
            for k in range(len(group_indices)):
                result[group_indices[k]] = nums[idx[i + k]]

            i = j

        return result

class Solution {
public:
    vector<int> lexicographicallySmallestArray(
        vector<int>& nums,
        int limit
    ) {
        int n = nums.size();

        // Sort indices based on values
        vector<int> idx(n);

        for (int i = 0; i < n; i++) {
            idx[i] = i;
        }

        sort(idx.begin(), idx.end(), [&](int a, int b) {
            return nums[a] < nums[b];
        });

        vector<int> result(n);

        int i = 0;

        while (i < n) {
            int j = i + 1;

            // Find the current group
            while (
                j < n &&
                nums[idx[j]] - nums[idx[j - 1]] <= limit
            ) {
                j++;
            }

            // Get original positions
            vector<int> groupIndices;

            for (int k = i; k < j; k++) {
                groupIndices.push_back(idx[k]);
            }

            // Sort original positions
            sort(groupIndices.begin(), groupIndices.end());

            // Assign sorted values
            for (int k = 0; k < groupIndices.size(); k++) {
                result[groupIndices[k]] = nums[idx[i + k]];
            }

            i = j;
        }

        return result;
    }
};

class Solution {
    lexicographicallySmallestArray(nums, limit) {
        const n = nums.length;

        // Sort indices based on values
        const idx = Array.from({ length: n }, (_, i) => i);

        idx.sort((a, b) => nums[a] - nums[b]);

        const result = new Array(n);

        let i = 0;

        while (i < n) {
            let j = i + 1;

            // Find the current group
            while (
                j < n &&
                nums[idx[j]] - nums[idx[j - 1]] <= limit
            ) {
                j++;
            }

            // Get original positions
            const groupIndices = idx.slice(i, j);

            // Sort original positions
            groupIndices.sort((a, b) => a - b);

            // Assign sorted values
            for (let k = 0; k < groupIndices.length; k++) {
                result[groupIndices[k]] = nums[idx[i + k]];
            }

            i = j;
        }

        return result;
    }
}