Insert Delete GetRandom O(1) – Duplicates allowed

No Comments

Design a data structure that supports all following operations in average O(1) time.

Note: Duplicate elements are allowed.
insert(val): Inserts an item val to the collection.

remove(val): Removes an item val from the collection if present.

getRandom: Returns a random element from current collection of elements. The probability of each element being returned is linearly related to the number of same value the collection contains.

Example:

// Init an empty collection.
RandomizedCollection collection = new RandomizedCollection();
 
// Inserts 1 to the collection. Returns true as the collection did not contain 1.
collection.insert(1);
 
// Inserts another 1 to the collection. Returns false as the collection contained 1. Collection now contains [1,1].
collection.insert(1);
 
// Inserts 2 to the collection, returns true. Collection now contains [1,1,2].
collection.insert(2);
 
// getRandom should return 1 with the probability 2/3, and returns 2 with the probability 1/3.
collection.getRandom();
 
// Removes 1 from the collection, returns true. Collection now contains [1,2].
collection.remove(1);
 
// getRandom should return 1 and 2 both equally likely.
collection.getRandom();

[Problem Link]

The idea here is to use a HashMap and Array. As we insert val’s, we have a mapping of val’s and nodes (containing value and index). We also insert the node into an array. At any point of time if we need a random value, we simply generate a random number (between 1 to length of array) and return the value from the array (in O(1) time).

How do we remove an element in O(1) time? First we use the map, to find the node where this element is stored. We then swap that with the last element and finally remove the last element. This works because when we look for a random number, we don’t care about order of elements in the array.

This wont work if you don’t store index’es in Nodes.

Let’s look at an example for remove. Below is the status of the HashMap and array at some point of the program. Note that, #xxx is the reference to the Node object (where we store index and value).

1 -> [#abc  #def  #ghi]
2 -> [#jkl  #mno]
3 -> [#pqr]
 
[#abc  #def  #mno  #ghi  #jkl  #pqr]
 
#abc = { idx: 0, val: 1 }
#def = { idx: 1, val: 1 }
#mno = { idx: 2, val: 2 }
#ghi = { idx: 3, val: 1 }
#jkl = { idx: 4, val: 2 }
#pqr = { idx: 5, val: 3 }
 
After remove(2)
 
1 -> [#abc  #def  #ghi]
2 -> [#jkl]
3 -> [#pqr]
 
[#abc  #def  #pqr  #ghi  #jkl]
 
#abc = { idx: 0, val: 1 }
#def = { idx: 1, val: 1 }
#mno = { idx: 2, val: 2 } (DELETED)
#ghi = { idx: 3, val: 1 }
#jkl = { idx: 4, val: 2 }
#pqr = { idx: 2, val: 3 } (UPDATED INDEX AND POSITION IN ARRAY)

Here is what we need todo to remove(2)

  1. Using the HashMap find positions where ‘2’ is stored. We could pick any position to remove it from (we pick #mno pointing to { idx: 2, val: 2 }).
  2. We then pop the last element (i.e. #pqr pointing to { idx: 5, val: 3 })
  3. We need to replace the reference in the array from #mno to #pqr.
    this.arr[removeNode.idx] = lastNode;
  4. Note, at this point #pqr index is still 5, we simply update that to the correct index
    lastNode.idx = removeNode.idx;
/**
 * Initialize your data structure here.
 */
var RandomizedCollection = function() {
    this.arr = [];
    this.map = {};
    this.Node = function(val, idx) {
        this.val = val;
        this.idx = idx;
    }
};
 
/**
 * Inserts a value to the collection. Returns true if the collection did not already contain the specified element. 
 * @param {number} val
 * @return {boolean}
 */
RandomizedCollection.prototype.insert = function(val) {
    if (!this.map[val]) this.map[val] = [];
    let newNode = new this.Node(val, this.arr.length);
    this.arr.push(newNode);
    this.map[val].push(newNode);
    //console.log('insert', val, this.arr);
    return this.map[val].length === 1;
};
 
/**
 * Removes a value from the collection. Returns true if the collection contained the specified element. 
 * @param {number} val
 * @return {boolean}
 */
RandomizedCollection.prototype.remove = function(val) {
    if (!this.map[val] || this.map[val].length === 0) return false;
    let removeNode = this.map[val].pop();
    let lastNode = this.arr.pop();
    if ( removeNode.idx !== lastNode.idx ) {
        lastNode.idx = removeNode.idx;
        this.arr[removeNode.idx] = lastNode;
    }
    //console.log('remove', val, this.map);
    //console.log(this.arr)
    return true;
};
 
/**
 * Get a random element from the collection.
 * @return {number}
 */
RandomizedCollection.prototype.getRandom = function() {
    if (this.arr.length < 1) return;
    let randomIdx = Math.floor(Math.random() * this.arr.length);
    //console.log('random', randomIdx, this.arr, this.arr.length)
    return this.arr[randomIdx].val;
};
 
/** 
 * Your RandomizedCollection object will be instantiated and called as such:
 * var obj = new RandomizedCollection()
 * var param_1 = obj.insert(val)
 * var param_2 = obj.remove(val)
 * var param_3 = obj.getRandom()
 */

[Programming Problem] Closest Binary Search Tree Value I and II

No Comments

Closest Binary Search Tree Value

Given a non-empty binary search tree and a target value, find the value in the BST that is closest to the target.

Note:

Given target value is a floating point.
You are guaranteed to have only one unique value in the BST that is closest to the target.
Example:

Input: root = [4,2,5,1,3], target = 3.714286

    4
   / \
  2   5
 / \
1   3

Output: 4

[Problem Link]

Since this is a BST, if the current node is larger than target, we look in the left subtree, else in the right subtree. In the end we simply return the value we get back from our recursion or the current node value depending on whichever one is closer to target. Remember to account for null values when we encounter a leaf node.

Time complexity is O(lgN)

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} target
 * @return {number}
 */
var closestValue = function(root, target) {
    if (!root) return null;
 
    let minNext;
    if (root.val > target) minNext = closestValue(root.left, target);
    else minNext = closestValue(root.right, target); 
 
    let minCurrDist = Math.abs(root.val-target);
    let minNextDist = minNext !== null ? Math.abs(minNext-target) : Number.MAX_VALUE;
 
    return minNextDist < minCurrDist ? minNext: root.val;
};

Closest Binary Search Tree Value II

Given a non-empty binary search tree and a target value, find k values in the BST that are closest to the target.

Note:

Given target value is a floating point.
You may assume k is always valid, that is: k ≤ total nodes.
You are guaranteed to have only one unique set of k values in the BST that are closest to the target.
Example:

Input: root = [4,2,5,1,3], target = 3.714286, and k = 2

    4
   / \
  2   5
 / \
1   3

Output: [4,3]

Follow up:
Assume that the BST is balanced, could you solve it in less than O(n) runtime (where n = total nodes)?

[Problem Link]

Traverse the full tree and keep storing closest distances (to target) in a priority queue. In the end, pop k number of elements from the queue and return the result. Note, the priority queue will be ordered based on distance (and not on the node values).

Time complexity will be O(NLgN), insert N items into a heap.
If we decide to keep the heap size k, it goes to O(NLgK).

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
 
class Node implements Comparable<Node> {
    int val;
    double dist;
    public Node(int val, double dist) {
        this.val = val;
        this.dist = dist;
    }
    public int compareTo(Node o) {
        return this.dist < o.dist ? -1 : 1;
    }
}
 
class Solution {
    public List<Integer> closestKValues(TreeNode root, double target, int k) {
        PriorityQueue<Node> q = new PriorityQueue<Node>();
        traverseBST(root, target, q);
        List<Integer> ret = new ArrayList<Integer>();
        for ( int i = 0 ; i < k ; i++ ) {
            ret.add(q.poll().val);
        }
        return ret;
    }
 
    public void traverseBST(TreeNode root, double target, PriorityQueue<Node> q) {
        if ( root == null )
            return;
        q.offer(new Node(root.val, Math.abs(root.val - target)));        
        traverseBST(root.left, target, q);
        traverseBST(root.right, target, q);        
    }
}

Another approach would be to traverse (inOrder) through the tree to build a sorted array (i.e. O(n)). Then we use two pointers to get the subarray which has numbers closest to k (i.e. another O(n) time complexity).

Total time complexity for this is: O(n)

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} target
 * @param {number} k
 * @return {number[]}
 */
 
function inOrder(root, arr) {
    if (!root) return;
 
    inOrder(root.left, arr);
    arr.push(root.val);
    inOrder(root.right, arr);
}
 
var closestKValues = function(root, target, k) {
    let ret = [];
    inOrder(root, ret);
    let i = 0;
    let j = ret.length - 1;
    while ((j-i+1) != k) {
        let iDist = Math.abs(ret[i] - target);
        let jDist = Math.abs(ret[j] - target);
        if ( iDist < jDist ) j--
        else i++
    }    
    let finalRet = [];
    for ( let start = i ; start <= j ; start++ ) finalRet.push(ret[start]);
    return finalRet;
};

[Programming Problem] Daily Temperatures

No Comments

Given a list of daily temperatures T, return a list such that, for each day in the input, tells you how many days you would have to wait until a warmer temperature. If there is no future day for which this is possible, put 0 instead.

For example, given the list of temperatures T = [73, 74, 75, 71, 69, 72, 76, 73], your output should be [1, 1, 4, 2, 1, 1, 0, 0].

Note: The length of temperatures will be in the range [1, 30000]. Each temperature will be an integer in the range [30, 100].

[Problem Link]

If you find a decreasing sequence keep moving forward until you find the number that breaks the sequence. Once you find that, move backward to find temperatures lower than that one. We could use a stack for this.

  1. Keep adding temperatures to a stack.
  2. If current temperature is less than or equal to the last element, add this temperature to the stack.
  3. If you find the current temperature is more than the last element on the stack you’ve found the next highest temperature for it (and possibly some temperatures before that). Keep doing this while the topmost element on the stack is less than the current temperature.

Basically when you find a decreasing sequence, just keep adding it to the stack. When that sequence breaks (meaning you find an element higher than the previous one), keep pop-ing elements from the stack to find temperatures that are lesser than the current temperature. We store indexes (and not actual temperatures) on the stack, so that we can calculate the days elapsed as we go.

Time and space complexity for this would be O(N)

/**
 * @param {number[]} T
 * @return {number[]}
 */
var dailyTemperatures = function(T) {
    if ( T.length === 0 ) return [];
    let ret = [];
    let arr = [ 0 ];
    T.forEach(function(curr, i) {
        if ( i === 0 ) return;
        while ( arr.length > 0 && T[arr[arr.length-1]] < curr ) {
            let lastElement = arr.pop();
            ret[lastElement] = i - lastElement;
        }
        arr.push(i);
    });
    if ( arr.length > 0 ) {
        arr.forEach(function(curr) {
            ret[curr] = 0;
        });
    }
    return ret;
};