Find All Numbers Disappeared in an Array

Given an array of integers where $1 ≤ a[i] ≤ n$ (n = size of array), some elements appear twice and others appear once.

Find all the elements of $[1, n]$ inclusive that do not appear in this array.

Could you do it without extra space and in $O(n)$ runtime? You may assume the returned list does not count as extra space.

Example:

Input:
[4,3,2,7,8,2,3,1]

Output:
[5,6]

"use strict";

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var findDisappearedNumbers = function(nums) {
  let len = nums.length;
  let hash = {};
  let ans = [];

  nums.forEach(function(item) {
    hash[item] = true;
  });

  for (let i = 1; i <= len; i++)
    !hash[i] && (ans.push(i));

  return ans;
};

Find Bottom Left Tree Value

Given a binary tree, find the leftmost value in the last row of the tree.

Example 1:

Input:

    2
   / \
  1   3

Output:
1

Example 2:

Input:

        1
       / \
      2   3
     /   / \
    4   5   6
       /
      7

Output:
7

Note: You may assume the tree (i.e., the given root node) is not NULL.

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var findBottomLeftValue = function(root) {
  let res = [];

  let dfs = (node, step) => {
    if (res[step] === undefined)
      res[step] = node.val;

    node.left && dfs(node.left, step + 1);
    node.right && dfs(node.right, step + 1);
  };

  dfs(root, 0);
  return res.pop();
};

Find K Pairs with Smallest Sums

You are given two integer arrays nums1 and nums2 sorted in ascending order and an integer k.

Define a pair (u,v) which consists of one element from the first array and one element from the second array.

Find the k pairs (u1,v1),(u2,v2) …(uk,vk) with the smallest sums.

Example 1:

Given nums1 = [1,7,11], nums2 = [2,4,6],  k = 3

Return: [1,2],[1,4],[1,6]

The first 3 pairs are returned from the sequence:
[1,2],[1,4],[1,6],[7,2],[7,4],[11,2],[7,6],[11,4],[11,6]

Example 2:

Given nums1 = [1,1,2], nums2 = [1,2,3],  k = 2

Return: [1,1],[1,1]

The first 2 pairs are returned from the sequence:
[1,1],[1,1],[1,2],[2,1],[1,2],[2,2],[1,3],[1,3],[2,3]

Example 3:

Given nums1 = [1,2], nums2 = [3],  k = 3 

Return: [1,3],[2,3]

All possible pairs are returned from the sequence:
[1,3],[2,3]

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @param {number} k
 * @return {number[][]}
 */
var kSmallestPairs = function(nums1, nums2, k) {
  k = Math.min(nums1.length * nums2.length, k);
  var len = nums1.length;
  var a = [];
  var ans = [];

  for (var i = 0; i < len; i++)
    a[i] = 0;


  while (k--) {
    var minn = Infinity;
    var index;

    for (var i = 0; i < len; i++) {
      if (a[i] === nums2.length)
        continue;
      var sum = nums1[i] + nums2[a[i]];
      if (sum < minn) {
        minn = sum;
        index = i;
      }
    }

    ans.push([nums1[index], nums2[a[index]]]);
    a[index]++;
  }

  return ans;
};

Find Largest Value in Each Tree Row

You need to find the largest value in each row of a binary tree.

Example:

Input: 

          1
         / \
        3   2
       / \   \  
      5   3   9 

Output: [1, 3, 9]

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var largestValues = function(root) {
  let maxn = [];

  let getMax = (a, b = -Number.MAX_VALUE) => Math.max(a, b);

  let dfs = (node, step) => {
    if (!node) return;
    maxn[step] = getMax(node.val, maxn[step]);
    dfs(node.left, step + 1);
    dfs(node.right, step + 1);
  };

  dfs(root, 0);
  return maxn;
};

Find Median from Data Stream

Median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value. So the median is the mean of the two middle value.

Examples:
[2,3,4] , the median is 3

[2,3], the median is (2 + 3) / 2 = 2.5

Design a data structure that supports the following two operations:

• void addNum(int num) - Add a integer number from the data stream to the data structure.
• double findMedian() - Return the median of all elements so far.

For example:

addNum(1)
addNum(2)
findMedian() -> 1.5
addNum(3) 
findMedian() -> 2

function binarySearch(a, target) {
  target += 1;
  var start = 0
    , end = a.length - 1;

  while(start <= end) {
    var mid = ~~((start + end) >> 1);
    if (a[mid] >= target)
      end = mid - 1;
    else 
      start = mid + 1;
  }

  return start;
}

/**
 * @constructor
 */
var MedianFinder = function() {
  this.num = [];
};

/**
 * @param {integer} word
 * @return {void}
 * Adds a num into the data structure.
 */
MedianFinder.prototype.addNum = function(num) {
  var index = binarySearch(this.num, num);
  this.num.splice(index, 0, num);
};

/**
 * @return {double}
 * Return median of current data stream
 */
MedianFinder.prototype.findMedian = function() {
  var len = this.num.length;

  if (len & 1)
    return this.num[~~(len / 2)];
  else return (this.num[len / 2] + this.num[len / 2 - 1]) / 2;
};

/**
 * Your MedianFinder object will be instantiated and called as such:
 * var mf = new MedianFinder();
 * mf.addNum(1);
 * mf.findMedian();
 */