2948. Make Lexicographically Smallest Array by Swapping Elements Medium

1/**
2 * [2948] Make Lexicographically Smallest Array by Swapping Elements
3 *
4 * You are given a 0-indexed array of positive integers nums and a positive integer limit.
5 * In one operation, you can choose any two indices i and j and swap nums[i] and nums[j] if |nums[i] - nums[j]| <= limit.
6 * Return the lexicographically smallest array that can be obtained by performing the operation any number of times.
7 * An array a is lexicographically smaller than an array b if in the first position where a and b differ, array a has an element that is less than the corresponding element in b. For example, the array [2,10,3] is lexicographically smaller than the array [10,2,3] because they differ at index 0 and 2 < 10.
8 *  
9 * <strong class="example">Example 1:
10 * 
11 * Input: nums = [1,5,3,9,8], limit = 2
12 * Output: [1,3,5,8,9]
13 * Explanation: Apply the operation 2 times:
14 * - Swap nums[1] with nums[2]. The array becomes [1,3,5,9,8]
15 * - Swap nums[3] with nums[4]. The array becomes [1,3,5,8,9]
16 * We cannot obtain a lexicographically smaller array by applying any more operations.
17 * Note that it may be possible to get the same result by doing different operations.
18 * 
19 * <strong class="example">Example 2:
20 * 
21 * Input: nums = [1,7,6,18,2,1], limit = 3
22 * Output: [1,6,7,18,1,2]
23 * Explanation: Apply the operation 3 times:
24 * - Swap nums[1] with nums[2]. The array becomes [1,6,7,18,2,1]
25 * - Swap nums[0] with nums[4]. The array becomes [2,6,7,18,1,1]
26 * - Swap nums[0] with nums[5]. The array becomes [1,6,7,18,1,2]
27 * We cannot obtain a lexicographically smaller array by applying any more operations.
28 * 
29 * <strong class="example">Example 3:
30 * 
31 * Input: nums = [1,7,28,19,10], limit = 3
32 * Output: [1,7,28,19,10]
33 * Explanation: [1,7,28,19,10] is the lexicographically smallest array we can obtain because we cannot apply the operation on any two indices.
34 * 
35 *  
36 * Constraints:
37 * 
38 * 	1 <= nums.length <= 10^5
39 * 	1 <= nums[i] <= 10^9
40 * 	1 <= limit <= 10^9
41 * 
42 */
43pub struct Solution {}
44
45// problem: https://leetcode.com/problems/make-lexicographically-smallest-array-by-swapping-elements/
46// discuss: https://leetcode.com/problems/make-lexicographically-smallest-array-by-swapping-elements/discuss/?currentPage=1&orderBy=most_votes&query=
47
48// submission codes start here
49
50impl Solution {
51    pub fn lexicographically_smallest_array(nums: Vec<i32>, limit: i32) -> Vec<i32> {
52        vec![]
53    }
54}
55
56// submission codes end
57
58#[cfg(test)]
59mod tests {
60    use super::*;
61
62    #[test]
63    fn test_2948() {
64    }
65}
66