LeetCode/go/make-lexicographically-smallest-array-by-swapping-elements.go

package main

import (
	sll "github.com/emirpasic/gods/v2/lists/singlylinkedlist"
	"slices"
)

func lexicographicallySmallestArray(nums []int, limit int) []int {
	// sort the numbers
	sortedNums := slices.Clone(nums)
	slices.Sort(sortedNums)

	// assign groups
	numToGroup := make(map[int]int)
	groups := make(map[int]*sll.List[int])

	group := 0
	for i, x := range sortedNums {
		if i > 0 && sortedNums[i]-sortedNums[i-1] > limit {
			group++
		}

		lst, ok := groups[group]
		if !ok {
			lst = sll.New[int]()
			groups[group] = lst
		}

		numToGroup[x] = group
		lst.Append(x)
	}

	// emplace into original slice
	for i, originalX := range nums {
		group = numToGroup[originalX]
		lst, _ := groups[group]

		newX, _ := lst.Get(0)
		lst.Remove(0)

		nums[i] = newX
	}

	return nums
}