Welcome to Subscribe On Youtube

2612. Minimum Reverse Operations

Description

You are given an integer n and an integer p in the range [0, n - 1]. Representing a 0-indexed array arr of length n where all positions are set to 0's, except position p which is set to 1.

You are also given an integer array banned containing some positions from the array. For the ith position in banned, arr[banned[i]] = 0, and banned[i] != p.

You can perform multiple operations on arr. In an operation, you can choose a subarray with size k and reverse the subarray. However, the 1 in arr should never go to any of the positions in banned. In other words, after each operation arr[banned[i]] remains 0.

Return an array ans where for each i from [0, n - 1], ans[i] is the minimum number of reverse operations needed to bring the 1 to position i in arr, or -1 if it is impossible.

  • A subarray is a contiguous non-empty sequence of elements within an array.
  • The values of ans[i] are independent for all i's.
  • The reverse of an array is an array containing the values in reverse order.

 

Example 1:

Input: n = 4, p = 0, banned = [1,2], k = 4
Output: [0,-1,-1,1]
Explanation: In this case k = 4 so there is only one possible reverse operation we can perform, which is reversing the whole array. Initially, 1 is placed at position 0 so the amount of operations we need for position 0 is 0. We can never place a 1 on the banned positions, so the answer for positions 1 and 2 is -1. Finally, with one reverse operation we can bring the 1 to index 3, so the answer for position 3 is 1. 

Example 2:

Input: n = 5, p = 0, banned = [2,4], k = 3
Output: [0,-1,-1,-1,-1]
Explanation: In this case the 1 is initially at position 0, so the answer for that position is 0. We can perform reverse operations of size 3. The 1 is currently located at position 0, so we need to reverse the subarray [0, 2] for it to leave that position, but reversing that subarray makes position 2 have a 1, which shouldn't happen. So, we can't move the 1 from position 0, making the result for all the other positions -1. 

Example 3:

Input: n = 4, p = 2, banned = [0,1,3], k = 1
Output: [-1,-1,0,-1]
Explanation: In this case we can only perform reverse operations of size 1. So the 1 never changes its position.

 

Constraints:

  • 1 <= n <= 105
  • 0 <= p <= n - 1
  • 0 <= banned.length <= n - 1
  • 0 <= banned[i] <= n - 1
  • 1 <= k <= n 
  • banned[i] != p
  • all values in banned are unique 

Solutions

Solution 1: Ordered Set + BFS

We notice that for any index $i$ in the subarray interval $[l,..r]$, the flipped index $j = l + r - i$.

If the subarray moves one position to the right, then $j = l + 1 + r + 1 - i = l + r - i + 2$, that is, $j$ will increase by $2$.

Similarly, if the subarray moves one position to the left, then $j = l - 1 + r - 1 - i = l + r - i - 2$, that is, $j$ will decrease by $2$.

Therefore, for a specific index $i$, all its flipped indices form an arithmetic progression with common difference $2$, that is, all the flipped indices have the same parity.

Next, we consider the range of values ​​of the index $i$ after flipping $j$.

  • If the boundary is not considered, the range of values ​​of $j$ is $[i - k + 1, i + k - 1]$.
  • If the subarray is on the left, then $[l, r] = [0, k - 1]$, so the flipped index $j$ of $i$ is $0 + k - 1 - i$, that is, $j = k - i - 1$, so the left boundary $mi = max(i - k + 1, k - i - 1)$.
  • If the subarray is on the right, then $[l, r] = [n - k, n - 1]$, so the flipped index $j= n - k + n - 1 - i$ is $j = n \times 2 - k - i - 1$, so the right boundary of $j$ is $mx = min(i + k - 1, n \times 2 - k - i - 1)$.

We use two ordered sets to store all the odd indices and even indices to be searched, here we need to exclude the indices in the array $banned$ and the index $p$.

Then we use BFS to search, each time searching all the flipped indices $j$ of the current index $i$, that is, $j = mi, mi + 2, mi + 4, \dots, mx$, updating the answer of index $j$ and adding index $j$ to the search queue, and removing index $j$ from the corresponding ordered set.

When the search is over, the answer to all indices can be obtained.

The time complexity is $O(n \times \log n)$ and the space complexity is $O(n)$. Where $n$ is the given array length in the problem.

  • class Solution {
        public int[] minReverseOperations(int n, int p, int[] banned, int k) {
            int[] ans = new int[n];
            TreeSet<Integer>[] ts = new TreeSet[] {new TreeSet<>(), new TreeSet<>()};
            for (int i = 0; i < n; ++i) {
                ts[i % 2].add(i);
                ans[i] = i == p ? 0 : -1;
            }
            ts[p % 2].remove(p);
            for (int i : banned) {
                ts[i % 2].remove(i);
            }
            ts[0].add(n);
            ts[1].add(n);
            Deque<Integer> q = new ArrayDeque<>();
            q.offer(p);
            while (!q.isEmpty()) {
                int i = q.poll();
                int mi = Math.max(i - k + 1, k - i - 1);
                int mx = Math.min(i + k - 1, n * 2 - k - i - 1);
                var s = ts[mi % 2];
                for (int j = s.ceiling(mi); j <= mx; j = s.ceiling(mi)) {
                    q.offer(j);
                    ans[j] = ans[i] + 1;
                    s.remove(j);
                }
            }
            return ans;
        }
    }
    
  • class Solution {
    public:
        vector<int> minReverseOperations(int n, int p, vector<int>& banned, int k) {
            vector<int> ans(n, -1);
            ans[p] = 0;
            set<int> ts[2];
            for (int i = 0; i < n; ++i) {
                ts[i % 2].insert(i);
            }
            ts[p % 2].erase(p);
            for (int i : banned) {
                ts[i % 2].erase(i);
            }
            ts[0].insert(n);
            ts[1].insert(n);
            queue<int> q{ {p} };
            while (!q.empty()) {
                int i = q.front();
                q.pop();
                int mi = max(i - k + 1, k - i - 1);
                int mx = min(i + k - 1, n * 2 - k - i - 1);
                auto& s = ts[mi % 2];
                auto it = s.lower_bound(mi);
                while (*it <= mx) {
                    int j = *it;
                    ans[j] = ans[i] + 1;
                    q.push(j);
                    it = s.erase(it);
                }
            }
            return ans;
        }
    };
    
  • from sortedcontainers import SortedSet
    
    
    class Solution:
        def minReverseOperations(
            self, n: int, p: int, banned: List[int], k: int
        ) -> List[int]:
            ans = [-1] * n
            ans[p] = 0
            ts = [SortedSet() for _ in range(2)]
            for i in range(n):
                ts[i % 2].add(i)
            ts[p % 2].remove(p)
            for i in banned:
                ts[i % 2].remove(i)
            ts[0].add(n)
            ts[1].add(n)
            q = deque([p])
            while q:
                i = q.popleft()
                mi = max(i - k + 1, k - i - 1)
                mx = min(i + k - 1, n * 2 - k - i - 1)
                s = ts[mi % 2]
                j = s.bisect_left(mi)
                while s[j] <= mx:
                    q.append(s[j])
                    ans[s[j]] = ans[i] + 1
                    s.remove(s[j])
                    j = s.bisect_left(mi)
            return ans
    
    
  • func minReverseOperations(n int, p int, banned []int, k int) []int {
    	ans := make([]int, n)
    	ts := [2]*redblacktree.Tree{redblacktree.NewWithIntComparator(), redblacktree.NewWithIntComparator()}
    	for i := 0; i < n; i++ {
    		ts[i%2].Put(i, struct{}{})
    		ans[i] = -1
    	}
    	ans[p] = 0
    	ts[p%2].Remove(p)
    	for _, i := range banned {
    		ts[i%2].Remove(i)
    	}
    	ts[0].Put(n, struct{}{})
    	ts[1].Put(n, struct{}{})
    	q := []int{p}
    	for len(q) > 0 {
    		i := q[0]
    		q = q[1:]
    		mi := max(i-k+1, k-i-1)
    		mx := min(i+k-1, n*2-k-i-1)
    		s := ts[mi%2]
    		for x, _ := s.Ceiling(mi); x.Key.(int) <= mx; x, _ = s.Ceiling(mi) {
    			j := x.Key.(int)
    			s.Remove(j)
    			ans[j] = ans[i] + 1
    			q = append(q, j)
    		}
    	}
    	return ans
    }
    
    func max(a, b int) int {
    	if a > b {
    		return a
    	}
    	return b
    }
    
    func min(a, b int) int {
    	if a < b {
    		return a
    	}
    	return b
    }
    
  • function minReverseOperations(
        n: number,
        p: number,
        banned: number[],
        k: number,
    ): number[] {
        const ans = new Array(n).fill(-1);
        const ts = new Array(2).fill(0).map(() => new TreeSet<number>());
        for (let i = 0; i < n; ++i) {
            ts[i % 2].add(i);
        }
        ans[p] = 0;
        ts[p % 2].delete(p);
        for (const i of banned) {
            ts[i % 2].delete(i);
        }
        ts[0].add(n);
        ts[1].add(n);
        let q = [p];
        while (q.length) {
            const t: number[] = [];
            for (const i of q) {
                const mi = Math.max(i - k + 1, k - i - 1);
                const mx = Math.min(i + k - 1, n * 2 - k - i - 1);
                const s = ts[mi % 2];
                for (let j = s.ceil(mi)!; j <= mx; j = s.ceil(j)!) {
                    t.push(j);
                    ans[j] = ans[i] + 1;
                    s.delete(j);
                }
            }
            q = t;
        }
        return ans;
    }
    
    type Compare<T> = (lhs: T, rhs: T) => number;
    
    class RBTreeNode<T = number> {
        data: T;
        count: number;
        left: RBTreeNode<T> | null;
        right: RBTreeNode<T> | null;
        parent: RBTreeNode<T> | null;
        color: number;
        constructor(data: T) {
            this.data = data;
            this.left = this.right = this.parent = null;
            this.color = 0;
            this.count = 1;
        }
    
        sibling(): RBTreeNode<T> | null {
            if (!this.parent) return null; // sibling null if no parent
            return this.isOnLeft() ? this.parent.right : this.parent.left;
        }
    
        isOnLeft(): boolean {
            return this === this.parent!.left;
        }
    
        hasRedChild(): boolean {
            return (
                Boolean(this.left && this.left.color === 0) ||
                Boolean(this.right && this.right.color === 0)
            );
        }
    }
    
    class RBTree<T> {
        root: RBTreeNode<T> | null;
        lt: (l: T, r: T) => boolean;
        constructor(
            compare: Compare<T> = (l: T, r: T) => (l < r ? -1 : l > r ? 1 : 0),
        ) {
            this.root = null;
            this.lt = (l: T, r: T) => compare(l, r) < 0;
        }
    
        rotateLeft(pt: RBTreeNode<T>): void {
            const right = pt.right!;
            pt.right = right.left;
    
            if (pt.right) pt.right.parent = pt;
            right.parent = pt.parent;
    
            if (!pt.parent) this.root = right;
            else if (pt === pt.parent.left) pt.parent.left = right;
            else pt.parent.right = right;
    
            right.left = pt;
            pt.parent = right;
        }
    
        rotateRight(pt: RBTreeNode<T>): void {
            const left = pt.left!;
            pt.left = left.right;
    
            if (pt.left) pt.left.parent = pt;
            left.parent = pt.parent;
    
            if (!pt.parent) this.root = left;
            else if (pt === pt.parent.left) pt.parent.left = left;
            else pt.parent.right = left;
    
            left.right = pt;
            pt.parent = left;
        }
    
        swapColor(p1: RBTreeNode<T>, p2: RBTreeNode<T>): void {
            const tmp = p1.color;
            p1.color = p2.color;
            p2.color = tmp;
        }
    
        swapData(p1: RBTreeNode<T>, p2: RBTreeNode<T>): void {
            const tmp = p1.data;
            p1.data = p2.data;
            p2.data = tmp;
        }
    
        fixAfterInsert(pt: RBTreeNode<T>): void {
            let parent = null;
            let grandParent = null;
    
            while (pt !== this.root && pt.color !== 1 && pt.parent?.color === 0) {
                parent = pt.parent;
                grandParent = pt.parent.parent;
    
                /*  Case : A
                    Parent of pt is left child of Grand-parent of pt */
                if (parent === grandParent?.left) {
                    const uncle = grandParent.right;
    
                    /* Case : 1
                       The uncle of pt is also red
                       Only Recoloring required */
                    if (uncle && uncle.color === 0) {
                        grandParent.color = 0;
                        parent.color = 1;
                        uncle.color = 1;
                        pt = grandParent;
                    } else {
                        /* Case : 2
                           pt is right child of its parent
                           Left-rotation required */
                        if (pt === parent.right) {
                            this.rotateLeft(parent);
                            pt = parent;
                            parent = pt.parent;
                        }
    
                        /* Case : 3
                           pt is left child of its parent
                           Right-rotation required */
                        this.rotateRight(grandParent);
                        this.swapColor(parent!, grandParent);
                        pt = parent!;
                    }
                } else {
                    /* Case : B
                   Parent of pt is right child of Grand-parent of pt */
                    const uncle = grandParent!.left;
    
                    /*  Case : 1
                        The uncle of pt is also red
                        Only Recoloring required */
                    if (uncle != null && uncle.color === 0) {
                        grandParent!.color = 0;
                        parent.color = 1;
                        uncle.color = 1;
                        pt = grandParent!;
                    } else {
                        /* Case : 2
                           pt is left child of its parent
                           Right-rotation required */
                        if (pt === parent.left) {
                            this.rotateRight(parent);
                            pt = parent;
                            parent = pt.parent;
                        }
    
                        /* Case : 3
                           pt is right child of its parent
                           Left-rotation required */
                        this.rotateLeft(grandParent!);
                        this.swapColor(parent!, grandParent!);
                        pt = parent!;
                    }
                }
            }
            this.root!.color = 1;
        }
    
        delete(val: T): boolean {
            const node = this.find(val);
            if (!node) return false;
            node.count--;
            if (!node.count) this.deleteNode(node);
            return true;
        }
    
        deleteAll(val: T): boolean {
            const node = this.find(val);
            if (!node) return false;
            this.deleteNode(node);
            return true;
        }
    
        deleteNode(v: RBTreeNode<T>): void {
            const u = BSTreplace(v);
    
            // True when u and v are both black
            const uvBlack = (u === null || u.color === 1) && v.color === 1;
            const parent = v.parent!;
    
            if (!u) {
                // u is null therefore v is leaf
                if (v === this.root) this.root = null;
                // v is root, making root null
                else {
                    if (uvBlack) {
                        // u and v both black
                        // v is leaf, fix double black at v
                        this.fixDoubleBlack(v);
                    } else {
                        // u or v is red
                        if (v.sibling()) {
                            // sibling is not null, make it red"
                            v.sibling()!.color = 0;
                        }
                    }
                    // delete v from the tree
                    if (v.isOnLeft()) parent.left = null;
                    else parent.right = null;
                }
                return;
            }
    
            if (!v.left || !v.right) {
                // v has 1 child
                if (v === this.root) {
                    // v is root, assign the value of u to v, and delete u
                    v.data = u.data;
                    v.left = v.right = null;
                } else {
                    // Detach v from tree and move u up
                    if (v.isOnLeft()) parent.left = u;
                    else parent.right = u;
                    u.parent = parent;
                    if (uvBlack) this.fixDoubleBlack(u);
                    // u and v both black, fix double black at u
                    else u.color = 1; // u or v red, color u black
                }
                return;
            }
    
            // v has 2 children, swap data with successor and recurse
            this.swapData(u, v);
            this.deleteNode(u);
    
            // find node that replaces a deleted node in BST
            function BSTreplace(x: RBTreeNode<T>): RBTreeNode<T> | null {
                // when node have 2 children
                if (x.left && x.right) return successor(x.right);
                // when leaf
                if (!x.left && !x.right) return null;
                // when single child
                return x.left ?? x.right;
            }
            // find node that do not have a left child
            // in the subtree of the given node
            function successor(x: RBTreeNode<T>): RBTreeNode<T> {
                let temp = x;
                while (temp.left) temp = temp.left;
                return temp;
            }
        }
    
        fixDoubleBlack(x: RBTreeNode<T>): void {
            if (x === this.root) return; // Reached root
    
            const sibling = x.sibling();
            const parent = x.parent!;
            if (!sibling) {
                // No sibiling, double black pushed up
                this.fixDoubleBlack(parent);
            } else {
                if (sibling.color === 0) {
                    // Sibling red
                    parent.color = 0;
                    sibling.color = 1;
                    if (sibling.isOnLeft()) this.rotateRight(parent);
                    // left case
                    else this.rotateLeft(parent); // right case
                    this.fixDoubleBlack(x);
                } else {
                    // Sibling black
                    if (sibling.hasRedChild()) {
                        // at least 1 red children
                        if (sibling.left && sibling.left.color === 0) {
                            if (sibling.isOnLeft()) {
                                // left left
                                sibling.left.color = sibling.color;
                                sibling.color = parent.color;
                                this.rotateRight(parent);
                            } else {
                                // right left
                                sibling.left.color = parent.color;
                                this.rotateRight(sibling);
                                this.rotateLeft(parent);
                            }
                        } else {
                            if (sibling.isOnLeft()) {
                                // left right
                                sibling.right!.color = parent.color;
                                this.rotateLeft(sibling);
                                this.rotateRight(parent);
                            } else {
                                // right right
                                sibling.right!.color = sibling.color;
                                sibling.color = parent.color;
                                this.rotateLeft(parent);
                            }
                        }
                        parent.color = 1;
                    } else {
                        // 2 black children
                        sibling.color = 0;
                        if (parent.color === 1) this.fixDoubleBlack(parent);
                        else parent.color = 1;
                    }
                }
            }
        }
    
        insert(data: T): boolean {
            // search for a position to insert
            let parent = this.root;
            while (parent) {
                if (this.lt(data, parent.data)) {
                    if (!parent.left) break;
                    else parent = parent.left;
                } else if (this.lt(parent.data, data)) {
                    if (!parent.right) break;
                    else parent = parent.right;
                } else break;
            }
    
            // insert node into parent
            const node = new RBTreeNode(data);
            if (!parent) this.root = node;
            else if (this.lt(node.data, parent.data)) parent.left = node;
            else if (this.lt(parent.data, node.data)) parent.right = node;
            else {
                parent.count++;
                return false;
            }
            node.parent = parent;
            this.fixAfterInsert(node);
            return true;
        }
    
        find(data: T): RBTreeNode<T> | null {
            let p = this.root;
            while (p) {
                if (this.lt(data, p.data)) {
                    p = p.left;
                } else if (this.lt(p.data, data)) {
                    p = p.right;
                } else break;
            }
            return p ?? null;
        }
    
        *inOrder(root: RBTreeNode<T> = this.root!): Generator<T, undefined, void> {
            if (!root) return;
            for (const v of this.inOrder(root.left!)) yield v;
            yield root.data;
            for (const v of this.inOrder(root.right!)) yield v;
        }
    
        *reverseInOrder(
            root: RBTreeNode<T> = this.root!,
        ): Generator<T, undefined, void> {
            if (!root) return;
            for (const v of this.reverseInOrder(root.right!)) yield v;
            yield root.data;
            for (const v of this.reverseInOrder(root.left!)) yield v;
        }
    }
    
    class TreeSet<T = number> {
        _size: number;
        tree: RBTree<T>;
        compare: Compare<T>;
        constructor(
            collection: T[] | Compare<T> = [],
            compare: Compare<T> = (l: T, r: T) => (l < r ? -1 : l > r ? 1 : 0),
        ) {
            if (typeof collection === 'function') {
                compare = collection;
                collection = [];
            }
            this._size = 0;
            this.compare = compare;
            this.tree = new RBTree(compare);
            for (const val of collection) this.add(val);
        }
    
        size(): number {
            return this._size;
        }
    
        has(val: T): boolean {
            return !!this.tree.find(val);
        }
    
        add(val: T): boolean {
            const successful = this.tree.insert(val);
            this._size += successful ? 1 : 0;
            return successful;
        }
    
        delete(val: T): boolean {
            const deleted = this.tree.deleteAll(val);
            this._size -= deleted ? 1 : 0;
            return deleted;
        }
    
        ceil(val: T): T | undefined {
            let p = this.tree.root;
            let higher = null;
            while (p) {
                if (this.compare(p.data, val) >= 0) {
                    higher = p;
                    p = p.left;
                } else {
                    p = p.right;
                }
            }
            return higher?.data;
        }
    
        floor(val: T): T | undefined {
            let p = this.tree.root;
            let lower = null;
            while (p) {
                if (this.compare(val, p.data) >= 0) {
                    lower = p;
                    p = p.right;
                } else {
                    p = p.left;
                }
            }
            return lower?.data;
        }
    
        higher(val: T): T | undefined {
            let p = this.tree.root;
            let higher = null;
            while (p) {
                if (this.compare(val, p.data) < 0) {
                    higher = p;
                    p = p.left;
                } else {
                    p = p.right;
                }
            }
            return higher?.data;
        }
    
        lower(val: T): T | undefined {
            let p = this.tree.root;
            let lower = null;
            while (p) {
                if (this.compare(p.data, val) < 0) {
                    lower = p;
                    p = p.right;
                } else {
                    p = p.left;
                }
            }
            return lower?.data;
        }
    
        first(): T | undefined {
            return this.tree.inOrder().next().value;
        }
    
        last(): T | undefined {
            return this.tree.reverseInOrder().next().value;
        }
    
        shift(): T | undefined {
            const first = this.first();
            if (first === undefined) return undefined;
            this.delete(first);
            return first;
        }
    
        pop(): T | undefined {
            const last = this.last();
            if (last === undefined) return undefined;
            this.delete(last);
            return last;
        }
    
        *[Symbol.iterator](): Generator<T, void, void> {
            for (const val of this.values()) yield val;
        }
    
        *keys(): Generator<T, void, void> {
            for (const val of this.values()) yield val;
        }
    
        *values(): Generator<T, undefined, void> {
            for (const val of this.tree.inOrder()) yield val;
            return undefined;
        }
    
        /**
         * Return a generator for reverse order traversing the set
         */
        *rvalues(): Generator<T, undefined, void> {
            for (const val of this.tree.reverseInOrder()) yield val;
            return undefined;
        }
    }
    
    class TreeMultiSet<T = number> {
        _size: number;
        tree: RBTree<T>;
        compare: Compare<T>;
        constructor(
            collection: T[] | Compare<T> = [],
            compare: Compare<T> = (l: T, r: T) => (l < r ? -1 : l > r ? 1 : 0),
        ) {
            if (typeof collection === 'function') {
                compare = collection;
                collection = [];
            }
            this._size = 0;
            this.compare = compare;
            this.tree = new RBTree(compare);
            for (const val of collection) this.add(val);
        }
    
        size(): number {
            return this._size;
        }
    
        has(val: T): boolean {
            return !!this.tree.find(val);
        }
    
        add(val: T): boolean {
            const successful = this.tree.insert(val);
            this._size++;
            return successful;
        }
    
        delete(val: T): boolean {
            const successful = this.tree.delete(val);
            if (!successful) return false;
            this._size--;
            return true;
        }
    
        count(val: T): number {
            const node = this.tree.find(val);
            return node ? node.count : 0;
        }
    
        ceil(val: T): T | undefined {
            let p = this.tree.root;
            let higher = null;
            while (p) {
                if (this.compare(p.data, val) >= 0) {
                    higher = p;
                    p = p.left;
                } else {
                    p = p.right;
                }
            }
            return higher?.data;
        }
    
        floor(val: T): T | undefined {
            let p = this.tree.root;
            let lower = null;
            while (p) {
                if (this.compare(val, p.data) >= 0) {
                    lower = p;
                    p = p.right;
                } else {
                    p = p.left;
                }
            }
            return lower?.data;
        }
    
        higher(val: T): T | undefined {
            let p = this.tree.root;
            let higher = null;
            while (p) {
                if (this.compare(val, p.data) < 0) {
                    higher = p;
                    p = p.left;
                } else {
                    p = p.right;
                }
            }
            return higher?.data;
        }
    
        lower(val: T): T | undefined {
            let p = this.tree.root;
            let lower = null;
            while (p) {
                if (this.compare(p.data, val) < 0) {
                    lower = p;
                    p = p.right;
                } else {
                    p = p.left;
                }
            }
            return lower?.data;
        }
    
        first(): T | undefined {
            return this.tree.inOrder().next().value;
        }
    
        last(): T | undefined {
            return this.tree.reverseInOrder().next().value;
        }
    
        shift(): T | undefined {
            const first = this.first();
            if (first === undefined) return undefined;
            this.delete(first);
            return first;
        }
    
        pop(): T | undefined {
            const last = this.last();
            if (last === undefined) return undefined;
            this.delete(last);
            return last;
        }
    
        *[Symbol.iterator](): Generator<T, void, void> {
            yield* this.values();
        }
    
        *keys(): Generator<T, void, void> {
            for (const val of this.values()) yield val;
        }
    
        *values(): Generator<T, undefined, void> {
            for (const val of this.tree.inOrder()) {
                let count = this.count(val);
                while (count--) yield val;
            }
            return undefined;
        }
    
        /**
         * Return a generator for reverse order traversing the multi-set
         */
        *rvalues(): Generator<T, undefined, void> {
            for (const val of this.tree.reverseInOrder()) {
                let count = this.count(val);
                while (count--) yield val;
            }
            return undefined;
        }
    }
    
    

All Problems

All Solutions