10:I[13699,["/_next/static/chunks/6b91a202b724e571.js","/_next/static/chunks/6710f67d945945a1.js","/_next/static/chunks/bde5ef9330c4de2d.js"],"default"] 11:I[25152,["/_next/static/chunks/6b91a202b724e571.js","/_next/static/chunks/6710f67d945945a1.js","/_next/static/chunks/bde5ef9330c4de2d.js"],"default"] 12:T40c,class Solution { public int[] lexicographicallySmallestArray(int[] nums, int limit) { int[] sortedNums = nums.clone(); Arrays.sort(sortedNums); int currGroup = 0; Map numToGroup = new HashMap<>(); numToGroup.put(sortedNums[0], currGroup); Map> groupToList = new HashMap<>(); groupToList.put(currGroup, new LinkedList<>(Arrays.asList(sortedNums[0]))); for (int i = 1; i < nums.length; i++) { if (Math.abs(sortedNums[i] - sortedNums[i - 1]) > limit) { currGroup++; } numToGroup.put(sortedNums[i], currGroup); groupToList.computeIfAbsent(currGroup, k -> new LinkedList<>()).add(sortedNums[i]); } for (int i = 0; i < nums.length; i++) { int num = nums[i]; int group = numToGroup.get(num); nums[i] = groupToList.get(group).pollFirst(); } return nums; } }13:T4c2,/** * @param {number[]} nums * @param {number} limit * @return {number[]} */ var lexicographicallySmallestArray = function(nums, limit) { let sortedNums = [...nums].sort((a, b) => a - b); let currGroup = 0; let numToGroup = new Map(); numToGroup.set(sortedNums[0], currGroup); let groupToList = new Map(); groupToList.set(currGroup, [sortedNums[0]]); for (let i = 1; i < nums.length; i++) { if (Math.abs(sortedNums[i] - sortedNums[i - 1]) > limit) { currGroup++; } numToGroup.set(sortedNums[i], currGroup); if (!groupToList.has(currGroup)) { groupToList.set(currGroup, []); } groupToList.get(currGroup).push(sortedNums[i]); } let result = []; let groupIndices = new Map(); // Keep track of 'pop' index to avoid O(N) shift for(let i=0; i<=currGroup; i++) groupIndices.set(i, 0); for (let i = 0; i < nums.length; i++) { let num = nums[i]; let group = numToGroup.get(num); let list = groupToList.get(group); let idx = groupIndices.get(group); result.push(list[idx]); groupIndices.set(group, idx + 1); } return result; };

Time Complexity

Space Complexity