Make Lexicographically Smallest Array by Swapping Elements
Problem Statement
Aapko ek 0-indexed array of positive integers
nums
aur ek positive integerlimit
diya gaya hai.Permissible Operation:
Ek operation mein aapko
nums
ke kisi bhi do indicesi
aurj
ko choose karkenums[i]
aurnums[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
aurb
ko compare kiya jaye aur unka pehla different positionp
ho, jahana[p]
b[p]
se chhota ho, tab arraya
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]
konums[2]
se swap karte hain. Array:[1, 3, 5, 9, 8]
nums[3]
konums[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]
konums[2]
se swap karte hain. Array:[1, 6, 7, 18, 2, 1]
nums[0]
konums[4]
se swap karte hain. Array:[2, 6, 7, 18, 1, 1]
nums[0]
konums[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.Intuition
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.Approach
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
#include
using namespace std;
class Solution {
public:
// Function to get the lexicographically smallest array
vector lexicographicallySmallestArray(vector& 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> 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 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 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.