Make Lexicographically Smallest Array by Swapping Elements

Problem Statement

  • Aapko ek 0-indexed array of positive integers nums aur ek positive integer limit diya gaya hai.

    Permissible Operation:

    Ek operation mein aapko nums ke kisi bhi do indices i aur j ko choose karke nums[i] aur nums[j] ko swap karna hai, agar |nums[i] - nums[j]| <= limit.

    Objective:

    Aapko operations kis bhi number of times perform karke lexicographically smallest array return karna hain.

    Lexicographically Smaller Explanation:

    Agar koi do arrays a aur b ko compare kiya jaye aur unka pehla different position p ho, jahan a[p] b[p] se chhota ho, tab array a lexicographically smaller hota hai. For example, array [2, 10, 3] array [10, 2, 3] se lexicographically smaller hai kyunki wo index 0 pe differ karte hain aur 2 < 10.

    Examples:

    Example 1:

    Input: nums = [1, 5, 3, 9, 8], limit = 2 Output: [1, 3, 5, 8, 9] Explanation: Operations 2 baar apply hoti hain:

    • nums[1] ko nums[2] se swap karte hain. Array: [1, 3, 5, 9, 8]

    • nums[3] ko nums[4] se swap karte hain. Array: [1, 3, 5, 8, 9]

    • Ye array aage aur smaller nahi ho sakta operations se.

    Example 2:

    Input: nums = [1, 7, 6, 18, 2, 1], limit = 3 Output: [1, 6, 7, 18, 1, 2] Explanation: Operations 3 baar apply hoti hain:

    • nums[1] ko nums[2] se swap karte hain. Array: [1, 6, 7, 18, 2, 1]

    • nums[0] ko nums[4] se swap karte hain. Array: [2, 6, 7, 18, 1, 1]

    • nums[0] ko nums[5] se swap karte hain. Array: [1, 6, 7, 18, 1, 2]

    • Ye array aage aur smaller nahi ho sakta operations se.

    Example 3:

    Input: nums = [1, 7, 28, 19, 10], limit = 3 Output: [1, 7, 28, 19, 10] Explanation: [1, 7, 28,19, 10] already lexicographically smallest hai kyunki koi bhi indices pe operation apply nahi ho sakti.

    Constraints:

    • 1 <= nums.length <= 10^5

    • 1 <= nums[i] <= 10^9

    • 1 <= limit <= 10^9

  •  

Make Lexicographically Smallest Array by Swapping Elements

Group Numbers Together: Imagine karo ki aapke paas ek list of numbers hai aur aap do numbers ko sirf tabhi swap kar sakte ho jab unka difference limit se chhota ya equal ho. Sabse chhota possible order paane ke liye, un numbers ko group mein club karo jo ek-dusre se swap kiye ja sakte hain.

Sort Each Group: Har group ko individually sort karo. Sorting ka matlab hai ki har group ke numbers ko ascending order mein arrange karna.

Place in Earliest Positions: Ab har sorted group ko list ke starting se earliest positions par rakh do, taaki lexicographically smallest array mil sake.

Original Positions Track Karo: Sabse pehle, har number ke asli index ko track karo. Yeh zaroori hota hai taaki baad mein unko unki sahi jagah par wapas rakha ja sake.

Sort by Value: Uske baad, numbers ko smallest se largest tak sort karo. Sorting ke baad, humari madad hogi values ko ascending order mein arrange karne mei.

Group by Limit: Ab aap sorted numbers ko aise groups mein divide karo jahan consecutive numbers ka difference limit ke andar ho. Matlab, ek group banate hain jin numbers ko aapas mein swap kar sakte hain.

Sort Group Indices: Har group ke liye, un numbers ke original positions ko sort karo. Yeh zaroori hota hai taaki sorted values ko sahi positions mein wapas rakha ja sake.

Fill Sorted Values: Akhir mein, sorted values ko in sorted positions mein place karo. Matlab, har group ke sorted values ko unke sorted positions pe wapas rakhte hain. Is tarike se final list ko lexicographically smallest banaya jata hai.

Time Complexity: O(n log n)
  • Is problem mein, humko phela step hai array ke elements ko sort karna. Sorting operation ka time complexity O(n log n) hota hai.

  • Uske baad, groups of indices ko bhi sort karna hota hai jo ki O(n log n) mein hota hai.

  • O(n log n) ka combination ek efficient sorting algorithm jaisa ki Timsort ya Merge Sort hoti hain jo stable sorting provide karti hain.

Space Complexity: O(n)
  • Is problem mein, space complexity O(n) hoti hai kyunki hume pairs of values aur unke original indices ko store karna hota hai.

  • Har index ke strictly ek pair maintain karna padta hai jo overall O(n) extra space consume karta hai.

Solution

				
					function lexicographicallySmallestArray(nums, limit) {
    let n = nums.length;
    if (n === 0) return [];

    // Step 1: Har number ko uski original index ke sath pair karo
    let sortedPairs = [];
    for (let i = 0; i < n; i++) {
        sortedPairs.push([nums[i], i]);
    }
    
    // Step 2: Numbers ko sort karo unki value ke hisaab se
    sortedPairs.sort((a, b) => a[0] - b[0]);

    let result = new Array(n);
    let groupStart = 0;

    for (let i = 0; i < n; i++) {
        // Step 3: Check karo agar current group yahan khatam hota hai
        if (i === n - 1 || sortedPairs[i + 1][0] - sortedPairs[i][0] > limit) {
            // Step 4: Original indices ko collect aur sort karo
            let indices = [];
            for (let j = groupStart; j <= i; j++) {
                indices.push(sortedPairs[j][1]);
            }
            indices.sort((a, b) => a - b);
            
            // Step 5: Sorted values ko sorted indices pe assign karo
            for (let j = 0; j < indices.length; j++) {
                result[indices[j]] = sortedPairs[groupStart + j][0];
            }
            
            groupStart = i + 1; // Agla group current ke baad start hota hai
        }
    }

    return result;
}

				
			

Original Index Tracking: Har number ka asli position track karo by pairing it with its index. Iska matlab har number ke sath uska index rakhna important hai.

Sort by Values: Uske baad, numbers ko unki values ke hisaab se sort karo. Matlab har pair ko number ki value ke according ascending order mein arrange karo.

Group Formation: Phir, sorted numbers ko groups mein divide karo jahan consecutive numbers ka difference limit ke andar ho. Matlab, ek group banate hain jin numbers ko ek-dusre se swap kar sakte hain.

Sort Original Positions: Har group ke liye, un numbers ke asli positions ko sort karo. Yeh zaroori hota hai taaki sorted values ko asli jagah par wapas rakh sakein.

Place Sorted Values: Akhir mein, sorted values ko unke sorted positions mein place karo. Har group mein jo sorted numbers hain, unko starting se rakho. Isse lexicographically smallest array milta hai.

Solution

				
					#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    // Function to get the lexicographically smallest array
    vector<int> lexicographicallySmallestArray(vector<int>& nums, int limit) {
        int n = nums.size(); // Array size find kartein hain
        if (n == 0) return {}; // Agar array empty hai, return empty

        // Step 1: Har number ko uski asli index ke sath pair kartein hain
        vector<pair<int, int>> sortedPairs;
        for (int i = 0; i < n; ++i) 
            sortedPairs.emplace_back(nums[i], i); // Pairing elements with their indices
        
        // Step 2: Numbers ko unki value ke hisaab se sort kartein hain
        sort(sortedPairs.begin(), sortedPairs.end());
        
        vector<int> result(n); // Resultant array for final answer
        int groupStart = 0; // Initial group start point

        for (int i = 0; i < n; ++i) {
            // Step 3: Check kartein hain agar current group yahan khatam hota hai
            if (i == n-1 || sortedPairs[i+1].first - sortedPairs[i].first > limit) {
                // Step 4: Original indices ko collect aur sort kartein hain
                vector<int> indices;
                for (int j = groupStart; j <= i; ++j)
                    indices.push_back(sortedPairs[j].second);
                sort(indices.begin(), indices.end()); // Original indices ko sort kartein hain
                
                // Step 5: Sorted values ko sorted indices par assign kartein hain
                for (int j = 0; j < indices.size(); ++j) 
                    result[indices[j]] = sortedPairs[groupStart + j].first; // Values ko assign kartein hain
                
                groupStart = i + 1; // Agla group current ke baad start hota hai
            }
        }
        return result; // Lexicographically smallest array return kartein hain
    }
};

				
			
  • Original Index Tracking: Har number ka asli position track karo by pairing it with its index. Iska matlab har number ke sath uska index rakhna important hai.

    Sort by Values: Uske baad, numbers ko unki values ke hisaab se sort karo. Matlab har pair ko number ki value ke according ascending order mein arrange karo.

    Group by Limit: Phir, sorted numbers ko groups mein divide karo jahan consecutive numbers ka difference limit ke andar ho. Matlab, ek group banate hain jin numbers ko ek-dusre se swap kar sakte hain.

    Sort Original Positions: Har group ke liye, un numbers ke asli positions ko sort karo. Yeh zaroori hota hai taaki sorted values ko asli jagah par wapas rakh sakein.

    Place Sorted Values: Akhir mein, sorted values ko unke sorted positions mein place karo. Har group mein jo sorted numbers hain, unko starting se rakho. Isse lexicographically smallest array milta hai.