2817. Minimum Absolute Difference Between Elements With Constraint

1class Solution {
2    public int minAbsoluteDifference(List<Integer> nums, int windowSize) {
3        // TreeMap to store the occurrences of the numbers in the current window
4        TreeMap<Integer, Integer> frequencyMap = new TreeMap<>();
5        // Initialize the answer with the maximum possible positive integer value
6        int minimumDifference = Integer.MAX_VALUE;
7      
8        // Start from index windowSize, as we want to have a complete window
9        for (int i = windowSize; i < nums.size(); ++i) {
10            // Add or update the frequency of the starting element of the current window
11            frequencyMap.merge(nums.get(i - windowSize), 1, Integer::sum);
12            // Find the smallest number greater than or equal to the current number
13            Integer higherOrEqual = frequencyMap.ceilingKey(nums.get(i));
14            if (higherOrEqual != null) {
15                // If found, update the minimum difference
16                minimumDifference = Math.min(minimumDifference, higherOrEqual - nums.get(i));
17            }
18            // Find the greatest number less than or equal to the current number
19            Integer lowerOrEqual = frequencyMap.floorKey(nums.get(i));
20            if (lowerOrEqual != null) {
21                // If found, update the minimum difference
22                minimumDifference = Math.min(minimumDifference, nums.get(i) - lowerOrEqual);
23            }
24        }
25        // Return the found minimum absolute difference
26        return minimumDifference;
27    }
28}
29

1#include <vector>
2#include <set>
3#include <algorithm> // For std::min and std::max
4#include <climits> // For INT_MAX
5
6class Solution {
7public:
8    // Function to find the minimum absolute difference
9    int minAbsoluteDifference(vector<int>& nums, int x) {
10        // Initialize the answer with the maximum possible int value
11        int minAbsDiff = INT_MAX;
12
13        // Use a multiset to maintain a sorted window of the last 'x' elements
14        multiset<int> windowElements;
15
16        // Loop to calculate the minimum absolute difference
17        for (int i = x; i < nums.size(); ++i) {
18            // Insert elements into the window so it always contains 'x' elements
19            windowElements.insert(nums[i - x]);
20
21            // Find the lower_bound of the current number in our window
22            auto it = windowElements.lower_bound(nums[i]);
23
24            // If the iterator is not at the end, update the minimum difference
25            if (it != windowElements.end()) {
26                minAbsDiff = min(minAbsDiff, abs(*it - nums[i]));
27            }
28
29            // Check the predecessor of the current element if it exists
30            if (it != windowElements.begin()) {
31                --it; // Move the iterator to the left element
32                minAbsDiff = min(minAbsDiff, abs(nums[i] - *it));
33            }
34        }
35        // Return the minimum absolute difference found
36        return minAbsDiff;
37    }
38};
39

1module TreeMultiSetModule {
2    // Define a comparator type for comparing elements.
3    type Compare<T> = (lhs: T, rhs: T) => number;
4
5    // Red-Black Tree node class with generics support.
6    class RBTreeNode<T = number> {
7        data: T;
8        count: number;
9        left: RBTreeNode<T> | null;
10        right: RBTreeNode<T> | null;
11        parent: RBTreeNode<T> | null;
12        color: number;
13
14        constructor(data: T) {
15            this.data = data;
16            this.left = this.right = this.parent = null;
17            this.color = 0; // Use 0 for red, 1 for black.
18            this.count = 1; // Counter for duplicates.
19        }
20
21        // Helper function to get the sibling of the node.
22        sibling(): RBTreeNode<T> | null {
23            if (!this.parent) {
24                return null; // No sibling if no parent.
25            }
26            return this.isOnLeft() ? this.parent.right : this.parent.left;
27        }
28
29        // Check if the node is the left child of its parent.
30        isOnLeft(): boolean {
31            return this === this.parent!.left;
32        }
33
34        // Check if the node has at least one red child.
35        hasRedChild(): boolean {
36            return (
37                (this.left !== null && this.left.color === 0) ||
38                (this.right !== null && this.right.color === 0)
39            );
40        }
41    }
42
43    // Red-Black Tree class definition.
44    class RBTree<T> {
45        root: RBTreeNode<T> | null;
46        lt: (l: T, r: T) => boolean; // Function to compare two nodes.
47
48        constructor(compare: Compare<T> = (l: T, r: T) => (l < r ? -1 : l > r ? 1 : 0)) {
49            this.root = null; // Root initially set to null.
50            this.lt = (l: T, r: T) => compare(l, r) < 0;
51        }
52
53        // Rotate the subtree to the left at the given node.
54        rotateLeft(pt: RBTreeNode<T>): void {
55            const right = pt.right!;
56            pt.right = right.left;
57
58            if (pt.right) {
59                pt.right.parent = pt;
60            }
61            right.parent = pt.parent;
62
63            if (!pt.parent) {
64                this.root = right;
65            } else if (pt === pt.parent.left) {
66                pt.parent.left = right;
67            } else {
68                pt.parent.right = right;
69            }
70
71            right.left = pt;
72            pt.parent = right;
73        }
74
75        // Rotate the subtree to the right at the given node.
76        rotateRight(pt: RBTreeNode<T>): void {
77            const left = pt.left!;
78            pt.left = left.right;
79
80            if (pt.left) {
81                pt.left.parent = pt;
82            }
83            left.parent = pt.parent;
84
85            if (!pt.parent) {
86                this.root = left;
87            } else if (pt === pt.parent.left) {
88                pt.parent.left = left;
89            } else {
90                pt.parent.right = left;
91            }
92
93            left.right = pt;
94            pt.parent = left;
95        }
96
97        // Swap colors between two nodes.
98        swapColor(p1: RBTreeNode<T>, p2: RBTreeNode<T>): void {
99            const tmp = p1.color;
100            p1.color = p2.color;
101            p2.color = tmp;
102        }
103
104        // Swap data between two nodes.
105        swapData(p1: RBTreeNode<T>, p2: RBTreeNode<T>): void {
106            const tmp = p1.data;
107            p1.data = p2.data;
108            p2.data = tmp;
109        }
110      
111        // Additional RBTree methods would go here...
112    }
113
114    // TreeMultiSet class definition with generics support, using a Red-Black Tree.
115    class TreeMultiSet<T = number> {
116        private _size: number; // The number of elements in the multiset.
117        private tree: RBTree<T>; // The underlying Red-Black tree.
118        private compare: Compare<T>; // Comparator function for the elements.
119
120        constructor(
121            collection: T[] | Compare<T> = [],
122            compare: Compare<T> = (l: T, r: T) => (l < r ? -1 : l > r ? 1 : 0)
123        ) {
124            if (typeof collection === 'function') {
125                compare = collection;
126                collection = [];
127            }
128            this._size = 0;
129            this.compare = compare;
130            this.tree = new RBTree(compare);
131            for (const val of collection) {
132                this.add(val);
133            }
134        }
135
136        // Returns the size of the multiset.
137        size(): number {
138            return this._size;
139        }
140
141        // Checks if the multiset contains a value.
142        has(val: T): boolean {
143            return !!this.tree.find(val);
144        }
145
146        // Adds a value to the multiset.
147        add(val: T): boolean {
148            const successful = this.tree.insert(val);
149            if (successful) {
150                this._size++;
151            }
152            return successful;
153        }
154
155        // Deletes one occurrence of the value from the multiset.
156        delete(val: T): boolean {
157            const successful = this.tree.delete(val);
158            if (successful) {
159                this._size--;
160            }
161            return successful;
162        }
163
164        // Additional TreeMultiSet methods would go here...
165    }
166
167    // Export the TreeMultiSet class from the module.
168    export { TreeMultiSet };
169
170    // The rest of the TreeMultiSet class methods... (for brevity, not shown here)
171}
172
173// Export the module for use elsewhere.
174export = TreeMultiSetModule;
175