Find Minimum in Rotated Sorted Array

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

Find the minimum element.

You may assume no duplicate exists in the array.

/**
 * @param {number[]} nums
 * @return {number}
 */

var findMin = function(nums) {
  return Math.min.apply(null, nums);
};

Find Minimum in Rotated Sorted Array II

Follow up for “Find Minimum in Rotated Sorted Array”:
What if duplicates are allowed?

Would this affect the run-time complexity? How and why?

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

Find the minimum element.

The array may contain duplicates.

/**
 * @param {number[]} nums
 * @return {number}
 */

var findMin = function(nums) {
  return Math.min.apply(null, nums);
};

Find Mode in Binary Search Tree

Given a binary search tree (BST) with duplicates, find all the mode(s) (the most frequently occurred element) in the given BST.

Assume a BST is defined as follows:

• The left subtree of a node contains only nodes with keys less than or equal to the node’s key.
• The right subtree of a node contains only nodes with keys greater than or equal to the node’s key.
• Both the left and right subtrees must also be binary search trees.

For example:
Given BST [1,null,2,2],

1
 \
  2
 /
2

return [2].

Note: If a tree has more than one mode, you can return them in any order.

Follow up: Could you do that without using any extra space? (Assume that the implicit stack space incurred due to recursion does not count).

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

  let helper = (node) => {
    let val = node.val;
    hash[val] = (~~hash[val]) + 1;

    if (node.left)
      helper(node.left);
    if (node.right)
      helper(node.right);
  };

  root && helper(root);

  let ans = [];
  let maxn = -1;

  for (let key in hash) {
    let val = hash[key];

    if (val > maxn) {
      maxn = val;
      ans = [+key];
    } else if (val === maxn) {
      ans.push(+key);
    }
  }

  return ans;
};

Find Peak Element

A peak element is an element that is greater than its neighbors.

Given an input array where num[i] ≠ num[i+1], find a peak element and return its index.

The array may contain multiple peaks, in that case return the index to any one of the peaks is fine.

You may imagine that num[-1] = num[n] = -∞.

For example, in array [1, 2, 3, 1], 3 is a peak element and your function should return the index number 2.

/**
 * @param {number[]} nums
 * @return {number}
 */

var findPeakElement = function(nums) {
  var len = nums.length;
  nums[-1] = nums[len] = -Number.MAX_VALUE;
  for(var i = 0; i < len; i++) {
    if (nums[i] > nums[i - 1] && nums[i] > nums[i + 1])
      return i;
  }  
};

Find Right Interval

Given a set of intervals, for each of the interval i, check if there exists an interval j whose start point is bigger than or equal to the end point of the interval i, which can be called that j is on the “right” of i.

For any interval i, you need to store the minimum interval j’s index, which means that the interval j has the minimum start point to build the “right” relationship for interval i. If the interval j doesn’t exist, store -1 for the interval i. Finally, you need output the stored value of each interval as an array.

Note

• You may assume the interval’s end point is always bigger than its start point.
• You may assume none of these intervals have the same start point.

Example1:

Input: [ [1,2] ]

Output: [-1]

Explanation: There is only one interval in the collection, so it outputs -1.

Example2:

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

Output: [-1, 0, 1]

Explanation: There is no satisfied "right" interval for [3,4].
For [2,3], the interval [3,4] has minimum-"right" start point;
For [1,2], the interval [2,3] has minimum-"right" start point.

Example3:

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

Output: [-1, 2, -1]

Explanation: There is no satisfied "right" interval for [1,4] and [3,4].
For [2,3], the interval [3,4] has minimum-"right" start point.

"use strict";

/**
 * Definition for an interval.
 * function Interval(start, end) {
 *     this.start = start;
 *     this.end = end;
 * }
 */
/**
 * @param {Interval[]} intervals
 * @return {number[]}
 */
var findRightInterval = function(intervals) {
  intervals.forEach(function(item, index) {
    item.index = index;
  });

  intervals.sort(function(a, b) {
    // different starting positions
    return a.start - b.start;
  });

  let len = intervals.length;
  for (let i = 0; i < len; i++) {
    let f = true;
    for (let j = i + 1; j < len; j++) {
      if (intervals[j].start >= intervals[i].end) {
        intervals[i].right = intervals[j].index;
        f = false;
        break;
      }
    }
    f && (intervals[i].right = -1);
  }

  intervals.sort(function(a, b) {
    // different starting positions
    return a.index - b.index;
  });

  let ans = [];
  intervals.forEach(function(item) {
    ans.push(item.right);
  });

  return ans;
};