Welcome to Subscribe On Youtube

Question

Formatted question description: https://leetcode.ca/all/220.html

You are given an integer array nums and two integers indexDiff and valueDiff.

Find a pair of indices (i, j) such that:

  • i != j,
  • abs(i - j) <= indexDiff.
  • abs(nums[i] - nums[j]) <= valueDiff, and

Return true if such pair exists or false otherwise.

 

Example 1:

Input: nums = [1,2,3,1], indexDiff = 3, valueDiff = 0
Output: true
Explanation: We can choose (i, j) = (0, 3).
We satisfy the three conditions:
i != j --> 0 != 3
abs(i - j) <= indexDiff --> abs(0 - 3) <= 3
abs(nums[i] - nums[j]) <= valueDiff --> abs(1 - 1) <= 0

Example 2:

Input: nums = [1,5,9,1,5,9], indexDiff = 2, valueDiff = 3
Output: false
Explanation: After trying all the possible pairs (i, j), we cannot satisfy the three conditions, so we return false.

 

Constraints:

  • 2 <= nums.length <= 105
  • -109 <= nums[i] <= 109
  • 1 <= indexDiff <= nums.length
  • 0 <= valueDiff <= 109

Algorithm

Use TreeSet to solve, used to record the mapping between numbers and index.

most important difference between HashSet and TreeSet is ordering:

HashSet doesn’t guaranteed any order, while TreeSet maintains objects in Sorted order defined by either Comparable or Comparator method

Two pointers i and j are needed here. At first, both i and j point to 0, and then i starts to traverse the array to the right.

  • If the difference between i and j is greater than k, and there is nums[j] in the map, delete it from the TreeSet and j move 1 step to the right. This ensures that the difference between the index of all the numbers in TreeSet is not greater than k,
  • Then we use TreeSet subSet() function to find numbers greater than or equal to nums[i]-t, and the absolute value of the difference between all numbers less than this threshold and nums[i] will be greater than t.
  • Then check all the following numbers, and return true if the absolute value of the difference between the numbers is less than or equal to t. Finally traverse the entire array and return false

The treeSet is essentially a balanced binary search tree.

  • We put k elements in the treeSet, which is a sliding window.
  • So when we insert an element to the treeSet, we need to remove one from the end.

So the basic idea is for each element nums[i], we check if there is any element between [nums[i] - t, nums[i] + t]. If yes, return true.

Code

  • import java.util.SortedSet;
    import java.util.TreeSet;
    
    public class Contains_Duplicate_III {
    
        class Solution {
            public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
    
                if (nums == null || nums.length < 2 || k < 0 || t < 0) {
                    return false;
                }
    
                TreeSet<Long> set = new TreeSet<>(); // long because int will possibly be overflow
                for (int i = 0; i < nums.length; i++) {
                    long current = (long) nums[i];
                    long leftBoundary = (long) current - t;
                    long rightBoundary = (long) current + t + 1; // right boundary is exclusive, so +1
    
                    SortedSet<Long> sub = set.subSet(leftBoundary, rightBoundary);
    
                    if (sub.size() > 0) {
                        return true;
                    }
    
                    set.add(current);
    
                    // to keep the index diff <=k
                    if (i >= k) { // or if(set.size()>=k+1)
                        set.remove((long) nums[i - k]);
                    }
                }
    
                return false;
            }
        }
    
    }
    
    ############
    
    class Solution {
        public boolean containsNearbyAlmostDuplicate(int[] nums, int indexDiff, int valueDiff) {
            TreeSet<Long> ts = new TreeSet<>();
            for (int i = 0; i < nums.length; ++i) {
                Long x = ts.ceiling((long) nums[i] - (long) valueDiff);
                if (x != null && x <= (long) nums[i] + (long) valueDiff) {
                    return true;
                }
                ts.add((long) nums[i]);
                if (i >= indexDiff) {
                    ts.remove((long) nums[i - indexDiff]);
                }
            }
            return false;
        }
    }
    
  • // OJ: https://leetcode.com/problems/contains-duplicate-iii/
    // Time: O(NlogK)
    // Space: O(K)
    class Solution {
    public:
        bool containsNearbyAlmostDuplicate(vector<int>& A, int k, int t) {
            if (t < 0) return false;
            multiset<long> s;
            for (int i = 0; i < A.size(); ++i) {
                if (i > k) s.erase(s.find(A[i - k - 1]));
                if (s.lower_bound((long)A[i] - t) != s.upper_bound((long)A[i] + t)) return true;
                s.insert(A[i]);
            }
            return false;
        }
    };
    
  • '''
    Sorted Containers is an Apache2 licensed sorted collections library, written in pure-Python, and fast as C-extensions.
    
    
    >>> from sortedcontainers import SortedList
    >>> sl = SortedList(['e', 'a', 'c', 'd', 'b'])
    >>> sl
    SortedList(['a', 'b', 'c', 'd', 'e'])
    >>> sl *= 10_000_000
    >>> sl.count('c')
    10000000
    >>> sl[-3:]
    ['e', 'e', 'e']
    
    >>> from sortedcontainers import SortedDict
    >>> sd = SortedDict({'c': 3, 'a': 1, 'b': 2})
    >>> sd
    SortedDict({'a': 1, 'b': 2, 'c': 3})
    >>> sd.popitem(index=-1)
    ('c', 3)
    
    >>> from sortedcontainers import SortedSet
    >>> ss = SortedSet('abracadabra')
    >>> ss
    SortedSet(['a', 'b', 'c', 'd', 'r'])
    >>> ss.bisect_left('c')
    2
    
    
    ref: https://pypi.org/project/sortedcontainers/
    '''
    
    from sortedcontainers import SortedSet
    
    class Solution:
        def containsNearbyAlmostDuplicate(
            self, nums: List[int], indexDiff: int, valueDiff: int
        ) -> bool:
            s = SortedSet()
            for i, v in enumerate(nums):
                j = s.bisect_left(v - valueDiff) # then true: s[j] <= v - valueDiff
                if j < len(s) and s[j] <= v + valueDiff:
                    return True
                s.add(v)
                if i >= indexDiff:
                    s.remove(nums[i - indexDiff])
            return False
    
    ############
    
    '''
    bisect: maintaining a list in sorted order without having to sort the list after each insertion.
    https://docs.python.org/3/library/bisect.html
    
    bisect.bisect_left()
    Locate the insertion point for x in a to maintain sorted order.
    
    bisect.bisect_right() or bisect.bisect()
    Similar to bisect_left(), but returns an insertion point which comes after (to the right of) any existing entries of x in a.
    
    
    bisect.insort_left(a, x, lo=0, hi=len(a), *, key=None)
    Insert x in a in sorted order.
    Keep in mind that the O(log n) search is dominated by the slow O(n) insertion step.
    
    
    bisect.insort_right(a, x, lo=0, hi=len(a), *, key=None)
    bisect.insort(a, x, lo=0, hi=len(a), *, key=None)
    Similar to insort_left(), but inserting x in a after any existing entries of x.
    
    
    >>> import bisect
    >>> bisect.bisect_left([1,2,3], 2)
    1
    >>> bisect.bisect_right([1,2,3], 2)
    2
    
    >>> a = [1, 1, 1, 2, 3]
    >>> bisect.insort_left(a, 1.0)
    >>> a
    [1.0, 1, 1, 1, 2, 3]
    
    >>> a = [1, 1, 1, 2, 3]
    >>> bisect.insort_right(a, 1.0)
    >>> a
    [1, 1, 1, 1.0, 2, 3]
    
    >>> a = [1, 1, 1, 2, 3]
    >>> bisect.insort(a, 1.0)
    >>> a
    [1, 1, 1, 1.0, 2, 3]
    '''
    
    import bisect
    
    class Solution(object):
      def containsNearbyAlmostDuplicate(self, nums, k, t):
        """
        :type nums: List[int]
        :type k: int
        :type t: int
        :rtype: bool
        """
        if k == 0:
          return False
        bst = []
        if k < 0 or t < 0:
          return False
        for i, num in enumerate(nums):
          idx = bisect.bisect_left(bst, num)
          if idx < len(bst) and abs(bst[idx] - num) <= t:
            return True
          if idx > 0 and abs(bst[idx - 1] - num) <= t: # idx-1 is because, [3,4,5] and 3.5 insertion-index is 1, but here should check index=0 (i.e. 3), so idx-1
            return True
          if len(bst) >= k:
            del bst[bisect.bisect_left(bst, nums[i - k])]
          bisect.insort(bst, num)
        return False
    
    
  • func containsNearbyAlmostDuplicate(nums []int, k int, t int) bool {
    	n := len(nums)
    	left, right := 0, 0
    	rbt := redblacktree.NewWithIntComparator()
    	for right < n {
    		cur := nums[right]
    		right++
    		if p, ok := rbt.Floor(cur); ok && cur-p.Key.(int) <= t {
    			return true
    		}
    		if p, ok := rbt.Ceiling(cur); ok && p.Key.(int)-cur <= t {
    			return true
    		}
    		rbt.Put(cur, struct{}{})
    		if right-left > k {
    			rbt.Remove(nums[left])
    			left++
    		}
    	}
    	return false
    }
    
    
  • public class Solution {
        public bool ContainsNearbyAlmostDuplicate(int[] nums, int k, int t) {
            if (k <= 0 || t < 0) return false;
            var index = new SortedList<int, object>();
            for (int i = 0; i < nums.Length; ++i) {
                if (index.ContainsKey(nums[i])) {
                    return true;
                }
                index.Add(nums[i], null);
                var j = index.IndexOfKey(nums[i]);
                if (j > 0 && (long)nums[i] - index.Keys[j - 1] <= t) {
                    return true;
                }
                if (j < index.Count - 1 && (long)index.Keys[j + 1] - nums[i] <= t) {
                    return true;
                }
                if (index.Count > k) {
                    index.Remove(nums[i - k]);
                }
            }
            return false;
        }
    }
    
  • function containsNearbyAlmostDuplicate(
        nums: number[],
        indexDiff: number,
        valueDiff: number,
    ): boolean {
        const ts = new TreeSet<number>();
        for (let i = 0; i < nums.length; ++i) {
            const x = ts.ceil(nums[i] - valueDiff);
            if (x != null && x <= nums[i] + valueDiff) {
                return true;
            }
            ts.add(nums[i]);
            if (i >= indexDiff) {
                ts.delete(nums[i - indexDiff]);
            }
        }
        return false;
    }
    
    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