ravhb / leetcode

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
    var ret = [];
    for(var i = 0; i < nums.length; i++) {
        for(var j = i + 1; j < nums.length; j++) {
            if(nums[i] +  nums[j] === target) {
                ret.push(i);
                ret.push(j);
            }
        }
    }
    return ret;
};

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */

var getLengthList = function(head) {
  var len = 0;
  while (head !== null) {
    len++;
    head = head.next;
  }
  return len;
};

var addTwoNumbers = function(l1, l2) {
  var len1 = getLengthList(l1);
  var len2 = getLengthList(l2);

  if (len2 >= len1) {
    var tmp;
    tmp = l1; l1 = l2; l2 = tmp;
  }

  var head = l1;
  var val1, val2;
  var isOverTen = false;
  var prev;
  while (l1 !== null) {
    val1 = l1.val;
    val2 = l2 !== null ? l2.val : 0;

    if (isOverTen) {
      val1++;
      isOverTen = false;
    }
    if (val1 + val2 >= 10) {
      l1.val = val1 + val2 - 10;
      isOverTen = true;
    } else {
      l1.val = val1 + val2;
    }

    prev = l1;
    l1 = l1.next;
    if (l2 !== null) {
      l2 = l2.next;
    }
  }

  if (isOverTen) {
    prev.next = new ListNode(1);
  }

  return head;
};

/**
 * @param {string} s
 * @param {number} numRows
 * @return {string}
 */
var convert = function(s, numRows) {
    var chars = s.split('');
    var arrs = [];
    for(var k = 0; k < numRows; k++) {
        arrs.push([]);
    }

    var i = 0;
    while(i < chars.length) {
        for(var x = 0; x < numRows && i < chars.length; x++) {
            arrs[x].push(chars[i++]);
        }
        for(var x = numRows - 2; x > 0 && i < chars.length; x--) {
            arrs[x].push(chars[i++]);
        }
    }

    var ret = '';
    arrs.map(function(item) {
        ret = ret.concat(item.join(''));
    });
    return ret;
};

/**
 * @param {number} x
 * @return {number}
 */
var reverse = function(x) {
    var flag = (x < 0 ? true : false);
    x = Math.abs(x);
    var reverse = parseInt(new String(x).split('').reverse().join(''), 10);
    if(reverse > Math.pow(2, 31)) {
        return 0;
    }
    if(flag) {
        return 0 - reverse;
    } else {
        return reverse;
    }
    
};

/**
 * @param {string} str
 * @return {number}
 */
var myAtoi = function(str) {
    var ret = parseInt(str, 10);
    if(Number.isNaN(ret)) {
        return 0;
    }
    if(ret > 2147483647) {
        return 2147483647;
    } else if(ret < -2147483648) {
        return -2147483648;
    } else {
        return ret;
    }
};

/**
 * @param {number} x
 * @return {boolean}
 */
var isPalindrome = function(x) {
    x += '';
    var i = 0;
    var j = x.length - 1;
    while(i < j) {
        if(x[i] != x[j]) {
            return false
        }
        i++;
        j--;
    }
    return true;
};

/**
 * @param {number} num
 * @return {string}
 */
var intToRoman = function(num) {
    var M = ["", "M", "MM", "MMM"];
    var C = ["", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"];
    var X = ["", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"];
    var I = ["", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"];
    
    return [
        M[parseInt(num / 1000)],
        C[parseInt((num % 1000) / 100)],
        X[parseInt((num % 100) / 10)],
        I[num % 10]
    ].join('');
};

/**
 * @param {string} s
 * @return {number}
 * 
 * Symbol	Value
 *   I	      1
 *   V	      5
 *   X	      10
 *   L	      50
 *   C	      100
 *   D	      500
 *   M	      1,000

 */
var romanToInt = function(s) {
    var map = {
    	'I':1,
    	'V':5,
    	'X':10,
    	'L':50,
    	'C':100,
    	'D':500,
    	'M':1000
    };

    var sum = 0;
    var right = 'I';

    for(var i = s.length - 1; i >=0; i--) {
        if(i < s.length - 1) {
        	right = s[i + 1];
        }
        if(map[s[i]] < map[right]) {
        	sum -= map[s[i]];
        } else {
        	sum += map[s[i]];
        	right = s[i];
        }
    }
    return sum;
};

/**
 * @param {string[]} strs
 * @return {string}
 */
var longestCommonPrefix = function(strs) {
    if (strs.length === 0) return '';
    if (strs.length === 0) return strs[1];

    var ret = '';
    var isBreak = false;
    var isCommon = true;
    var char;

    for (var j = 0; j < strs[0].length; j++) {
        char = strs[0][j];

        for (var i = 1; i < strs.length; i++) {
            if (strs[i].length <= j || strs[i][j] !== char) {
                isBreak = true;
                break;
            }
        }
        if (isBreak) {
            break;
        }
        ret += strs[0][j];
    }
    return ret;
};

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

var threeSum = function(nums) {
    var ret = [];
    
    nums = nums.sort((a, b) => a - b);
    for (var i = 0; i + 2 < nums.length; i++) {
        if (i > 0 && nums[i] == nums[i - 1]) {
            continue;
        }
        
        var j = i + 1, k = nums.length - 1;  
        var target = -nums[i];
        
        while (j < k) {
            if (nums[j] + nums[k] == target) {
                ret.push([nums[i], nums[j], nums[k]]);
                j++;
                k--;
                while (j < k && nums[j] == nums[j - 1]) j++;
                while (j < k && nums[k] == nums[k + 1]) k--;
            } else if (nums[j] + nums[k] > target) {
                k--;
            } else {
                j++;
            }
        }
    }
    
    return ret;
};

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var threeSumClosest = function(nums, target) {
    var closet = Number.MAX_SAFE_INTEGER;
    var closetTarget;

    nums = nums.sort((a, b) => a - b);

    for (var i = 0; i + 2 < nums.length; i++) {
        if (i > 0 && nums[i] == nums[i - 1]) {
            continue;
        }

        var j = i + 1, k = nums.length - 1;

        while (j < k) {
            if (Math.abs(nums[j] + nums[k] + nums[i] - target) < closet) {
                closet = Math.abs(nums[j] + nums[k] + nums[i] - target);
                closetTarget = nums[j] + nums[k] + nums[i];
            }

            if (nums[j] + nums[k] + nums[i] === target) {
                return target;
            } else if (nums[j] + nums[k] + nums[i] > target) {
                k--;
            } else {
                j++;
            }
        }
    }

    return closetTarget;
};

/**
 * @param {string} digits
 * @return {string[]}
 */
var letterCombinations = function(digits) {
  if(digits.length === 0) {
    return [];
  }

  var map = {
    2: ['a', 'b', 'c'],
    3: ['d', 'e', 'f'],
    4: ['g', 'h', 'i'],
    5: ['j', 'k', 'l'],
    6: ['m', 'n', 'o'],
    7: ['p', 'q', 'r', 's'],
    8: ['t', 'u', 'v'],
    9: ['w', 'x', 'y', 'z'],
  };

  if(digits.length === 1) {
    return map[digits];
  } else {
    var front = map[digits.slice(0, 1)];
    var back = letterCombinations(digits.slice(1));
    var ret = [];

    front.forEach(f => {
      back.forEach(b => {
        ret.push(f + b);
      });
    });

    return ret;
  }
};

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} n
 * @return {ListNode}
 */
var removeNthFromEnd = function(head, n) {
    var front = head;
    var end = head;
    for(var i = 0; i <= n && front; i++) {
        front = front.next;
    }
    
    // delete first node
    if(i < n + 1) {
        return head.next;
    }
    
    while(front) {
        front = front.next;
        end = end.next;
    }
    end.next = end.next.next;
    return head;
};

/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function(s) {
    var stack = [];
    var match = {
        ')': '(',
        ']': '[',
        '}': '{'
    };
    var len;
    for(var i = 0; i < s.length; i++) {
        len = stack.length;
        if(len > 0 && stack[len-1] == match[s[i]]) {
            stack.pop();
        } else {
            stack.push(s[i]);
        }
    }
    return stack.length === 0;
};

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var mergeTwoLists = function(l1, l2) {
    if(!l1) return l2;
    if(!l2) return l1;
    var head = null
    if(l1.val < l2.val) {
        head = l1;
        l1 = l1.next;
    } else {
        head = l2;
        l2 = l2.next;
    }
    
    newlist = head;
    while(l1 && l2) {
        if(l1.val < l2.val) {
            newlist.next = l1;
            l1 = l1.next;
        } else {
            newlist.next = l2;
            l2 = l2.next;
        }
        newlist = newlist.next;
    }
    if(!l1) {
        newlist.next = l2;
    } else {
        newlist.next = l1;
    }
    
    return head;
};

/**
 * @param {number} n
 * @return {string[]}
 */
var generateParenthesis = function(n) {
  if(n === 0) {
    return [];
  } else if(n === 1){
    return ['()'];
  } else {
    var parenthesis = generateParenthesis(n - 1);
    var retObj = {};

    parenthesis.forEach(p => {
      for(var i = 0; i < p.length + 1; i++) {
        var charArr = p.split('');

        charArr.splice(i, 0, '()');
        retObj[charArr.join('')] = true;
      }
    });

    return Object.keys(retObj);
  }
};

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var swapPairs = function(head) {
    if(head === null || head.next === null) {
        return head;
    }
    
    var newhead = null;
    var tmp1 = head.next;
    var tmp2 = head.next.next;
    head.next.next = head;
    head.next = tmp2;
    newhead = tmp1;
    
    var p = head;
    while(p && p.next && p.next.next) {
        tmp1 = p.next.next;
        tmp2 = p.next.next.next;
        p.next.next.next = p.next;
        p.next.next = tmp2;
        p.next = tmp1;
        p = p.next.next;
    }
    
    return newhead;
};

/**
 * @param {number[]} nums
 * @return {number}
 */
var removeDuplicates = function(nums) {
    var i = 0;
    var j = 0;
    while(j < nums.length) {
        if(nums[i] == nums[j]) {
            j++;
        } else {
            i++;
            nums[i] = nums[j];
            j++;
        }
    }
    return i + 1;
    
};

/**
 * @param {number[]} nums
 * @param {number} val
 * @return {number}
 */
var removeElement = function(nums, val) {
    var head = 0;
    var tail = nums.length - 1;
    while(head <= tail) {
        if(nums[head] != val) {
            head++;
            continue;
        }
 
        if(nums[tail] == val) {
            tail--;
            continue;
        }  
        
        nums[head] = nums[tail];
        tail--;      
    }
    return head;
};

/**
 * @param {string} haystack
 * @param {string} needle
 * @return {number}
 */

var strStr = function(haystack, needle) {
  if (needle === '') return 0;
  for(var i = 0;; i++) {
    for(var j = 0;; j++) {
      if (j == needle.length) return i;
      if (i + j >= haystack.length) return -1;
      if (haystack[i + j] != needle[j]) break;
    }
  }
  return -1;
};

var nextPermutation = function(nums) {
    if (nums.length <= 1) {
      return;
    }

    var i = nums.length - 2;
    var j = nums.length - 1;
    while (nums[i] >= nums[i + 1] && i > -1) {
      i--;
    }
    if (i >= 0) {
      while (nums[j] <= nums[i]) {
        j--;
      }

      var temp;
      temp = nums[i];
      nums[i] = nums[j];
      nums[j] = temp;
    }

    var start = i + 1;
    var end = nums.length - 1;

    while (start < end) {
      temp = nums[start];
      nums[start] = nums[end];
      nums[end] = temp;
      start++;
      end--;
    }

};

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
function binarySearch(nums, target) {
    var end = nums.length - 1;
    var start = 0;
    var middle = parseInt((start + end) / 2);

    while (end >= start) {
        if (nums[middle] == target) {
            return middle;
        } else if(nums[middle] > target) {
            end = middle - 1;
        } else if(nums[middle] < target) {
            start = middle + 1;
        }
        middle = parseInt((start + end) / 2);
    }
    return -1;
}

var search = function(nums, target) {
    var i = 0;
    while(nums[i] <= nums[i+1]) {
        i++;
    }

    if (nums[0] <= target && target <= nums[i]) {
      return binarySearch(nums.slice(0, i + 1), target);
    } else if (nums[i + 1] <= target && target <= nums[nums.length - 1]){
      var ret = binarySearch(nums.slice(i + 1), target);
      return ret == -1 ? -1 : i + 1 + ret;
    } else {
      return -1;
    }
};

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var searchInsert = function(nums, target) {
    var start = 0;
    var end = nums.length - 1;
    var middle = parseInt((start + end) / 2);
    
    while(start <= end) {
        if (target === nums[middle]) {
            return middle;
        } else if (target > nums[middle]) {
            start = middle + 1;
        } else if (target < nums[middle] ) {
            end = middle - 1;
        }
        if (start > end) {
            if (target < nums[middle]) {
                return middle;
            } else {
                return middle + 1;    
            }
        } else {
            middle = parseInt((start + end) / 2);
        }
    }
};

/**
 * @param {character[][]} board
 * @return {boolean}
 */
var isValidSudoku = function(board) {
    var rowExist = {};
    var colExist = {};
    var boxExist = {};
    var k, value;
    for (var i = 0; i < board.length; i++) {
        for (var j = 0; j < board[i].length; j++) {
            value = board[i][j];
            k = parseInt(i / 3, 10) * 3 + parseInt(j / 3, 10); //the number of the box
            if (!rowExist[i]) {
                rowExist[i] = {};
            }
            if (!colExist[j]) {
                colExist[j] = {};
            }
            if (!boxExist[k]) {
                boxExist[k] = {};
            }

            if (value !== '.') {
                if (rowExist[i][value] || colExist[j][value] || boxExist[k][value]) {
                    return false;
                } else {
                    rowExist[i][value] = true;
                    colExist[j][value] = true;
                    boxExist[k][value] = true;
                }
            }
        }
    }
    return true;
};

/**
 * @param {number} n
 * @return {string}
 */

var countAndSay = function(n) {
    if (n === 1) return '1';
    
    var last = countAndSay(n - 1);
    var digit = last[0];
    var count = 0;
    var ret = '';
    
    for (var i = 0; i < last.length; i++) {
        if (last[i] !== digit) {
            ret += count + digit;
            digit = last[i];
            count = 0;
        }
        count++;
    }
    ret += count + digit;
    
    return ret;
};

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permute = function(nums) {
    var ret = [];
    if(nums.length == 1) {
        ret.push(nums);
        return ret;
    }

    var head, pre_ret, item, item_copy;
    head = nums.shift();
    pre_ret = permute(nums);
    for(var i = 0; i < pre_ret.length; i++ ) {
        item = pre_ret[i];
        for(var j = 0; j <= item.length; j++) {
            item_copy = [].slice.call(item);
            item_copy.splice(j, 0, head);
            ret.push(item_copy);
        }
    }
    return ret;
};

/**
 * @param {number[][]} matrix
 * @return {number[]}
 */
var spiralOrder = function(matrix) {
    if (matrix.length == 0) {return [];}
    var n = matrix.length;
    var m = matrix[0].length;
    var up = 0, right = m - 1, down = n - 1, left = 0;
    var ret = [];

    while(true) {
        for(var r = left; r <= right; r++) ret.push(matrix[up][r]);
        if (++up > down) break;

        for(var d = up; d <= down; d++) ret.push(matrix[d][right]);
        if (--right < left) break;

        for(var l = right; l >= left; l--) ret.push(matrix[down][l]);
        if (--down < up) break;

        for(var u = down; u >= up; u--) ret.push(matrix[u][left]);
        if (++left > right) break;
    }
    return ret;
};

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLastWord = function(s) {
    return s.trim().split(' ').pop().length;
};

/**
 * @param {number} m
 * @param {number} n
 * @return {number}
 */
var uniquePaths = function(m, n) {
  var dp = Array(n).fill(1).map(() => Array(m).fill(1));

  for (var i = 1; i < n; i++) {
    for (var j = 1; j < m; j++) {
      dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
    }
  }
  
  return dp[n - 1][m - 1];
};

/**
 * @param {number[][]} obstacleGrid
 * @return {number}
 */
var uniquePathsWithObstacles = function(obstacleGrid) {
    var n = obstacleGrid.length;
    var m = obstacleGrid[0].length;
    
    if (obstacleGrid[n - 1][m - 1] === 1 || obstacleGrid[0][0] === 1) return 0;
    
    var dp = Array(n).fill(null).map(() => Array(m).fill(0));
    for (var i = 0; i < m && obstacleGrid[0][i] === 0; i++) dp[0][i] = 1;
    for (var j = 0; j < n && obstacleGrid[j][0] === 0; j++) dp[j][0] = 1;
    
    var top, left;
    for (var i = 1; i < n; i++) {
        for (var j = 1; j < m; j++) {
            top = obstacleGrid[i - 1][j] === 1 ? 0 : dp[i - 1][j];
            left = obstacleGrid[i][j - 1] === 1 ? 0 : dp[i][j - 1];
            dp[i][j] = top + left;
        }
    }
    
    return dp[n - 1][m - 1];
};

/**
 * @param {number[]} digits
 * @return {number[]}
 */
var plusOne = function(digits) {
    digits.unshift(0);
    var tail = digits.length - 1;
    digits[tail]++;
    while(tail > 0) {
        if(digits[tail] == 10) {
            digits[tail] = 0;
            tail--;
            digits[tail]++;
        } else {
            tail--;
        }
    }
    if(digits[0] == 0) {
        digits.shift();
    }
    return digits;
};

/**
 * @param {number} x
 * @return {number}
 */
var mySqrt = function(x) {
    var start = 1;
    var end = x;
    var middle;

    while (start <= end) {
        middle = start + parseInt((end - start) / 2);
        if (x / middle === middle) {
            return middle;
        } else if (x / middle > middle) {
            start = middle + 1;
        } else {
            end = middle - 1;
        }
    }

    return end;
};

/**
 * @param {number[][]} matrix
 * @return {void} Do not return anything, modify matrix in-place instead.
 */
var setZeroes = function(matrix) {
    var hasZeroFirstCol = false;
    for(var i = 0; i < matrix.length; i++) {
        if(matrix[i][0] === 0)  {
            hasZeroFirstCol = true;
        }
        for(var j = 1; j < matrix[i].length; j++) {
            if(matrix[i][j] === 0) {
                matrix[0][j] = matrix[i][0] = 0;
            }
        }
    }
    for(var y = matrix.length - 1; y >= 0; y--) {
        for(var x = matrix[y].length - 1; x >= 1; x--) {
            if(matrix[0][x] === 0 || matrix[y][0] === 0) {
                matrix[y][x] = 0;
            }
        }
        if(hasZeroFirstCol) {
            matrix[y][0] = 0;
        }
    }
};

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var deleteDuplicates = function(head) {
    var iter = head;
    while(iter) {
        if(iter.next && iter.val === iter.next.val) {
            iter.next = iter.next.next;
        } else {
            iter = iter.next;
        }
    }
    return head;
};

/**
 * @param {number[]} nums1
 * @param {number} m
 * @param {number[]} nums2
 * @param {number} n
 * @return {void} Do not return anything, modify nums1 in-place instead.
 */
var merge = function(nums1, m, nums2, n) {
    while(n > 0) {
        if(m <= 0 || nums1[m - 1] <= nums2[n -1]) {
            nums1[m + n - 1] = nums2[n - 1];
            n--;
        } else {
            nums1[m + n - 1] = nums1[m - 1];
            m--;
        }
    }
};

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} m
 * @param {number} n
 * @return {ListNode}
 */

var reverseBetween = function(head, m, n) {
    function reverseList(head) {
        if(!head) {
            return head;
        }
        var prev = null;
        var next = null;
        while(head) {
            next = head.next;
            head.next = prev;
            prev = head;
            head = next;
        }
        return prev;
    }
    if(m === n) {
        return head;
    }
    var middleLeft = null;
    var middleRight = null;
    var left = null;
    var right = null;

    var i = 1;
    var point = head;
    while(point) {
        if(i + 1 === m) {
            left = point;
        }
        if(i === m) {
            middleLeft = point;
        }
        if(i === n) {
            middleRight = point;
        }
        if(i === n + 1) {
            right = point;
        }
        i++;
        point = point.next;
    }
    if(left) {
        left.next = null;
    }

    middleRight.next = null;
    reverseList(middleLeft);
    middleLeft.next = right;

    if(left) {
        left.next = middleRight;
        return head;
    } else {
        return middleRight;
    }
};

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
function isValid(root, max, min) {
  if (root === null) return true;
  if (root.val >= max || root.val <= min) return false;

  return isValid(root.left, root.val, min) && isValid(root.right, max, root.val);
}
var isValidBST = function(root) {
  return isValid(root, Number.MAX_SAFE_INTEGER, Number.MIN_SAFE_INTEGER);
};

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {boolean}
 */
var isSameTree = function(p, q) {
    if(p == null || q == null) {
        return p == q;
    }
    if(p.val == q.val && isSameTree(p.left, q.left) && isSameTree(p.right, q.right)) {
        return true;
    } else {
        return false;
    }
};

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */

var isSymmetric = function(root) {
    function isSymmetricNode(left, right) {
        if(!left && !right) {
            return true;
        }
        if((left && !right) || (!left && right)) {
            return false;
        }
        return (left.val == right.val) 
            && isSymmetricNode(left.left, right.right)
            && isSymmetricNode(left.right, right.left);
    }
    if(root === null) {
        return true;
    }
    var left = root.left;
    var right = root.right;
    return isSymmetricNode(left, right);
};

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var traversal = function(ret, root, depth) {
    if(root === null) {
        return;
    }
    if(!Array.isArray(ret[depth])) {
        ret[depth] = [];
    }
    ret[depth].push(root.val);
    traversal(ret, root.left, depth + 1);
    traversal(ret, root.right, depth + 1);
}
var levelOrder = function(root) {
    var ret = [];
    traversal(ret, root, 0);
    return ret;
};

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var maxDepth = function(root) {
    if(root == null) {
        return 0;
    } else {
        return Math.max(maxDepth(root.left), maxDepth(root.right)) +1;
    }
};

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var traversal = function(ret, root, depth) {
    if(root === null) {
        return;
    }
    if(!Array.isArray(ret[depth])) {
        ret[depth] = [];
    }
    ret[depth].push(root.val);
    traversal(ret, root.left, depth + 1);
    traversal(ret, root.right, depth + 1);
}
var levelOrderBottom = function(root) {
    var ret = [];
    traversal(ret, root, 0);
    return ret.reverse();
};

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

var sortedArrayToBST = function(nums) {
    if (nums.length === 0) {return null;}
    var start = 0; 
    var end = nums.length - 1;
    var middle = parseInt((start + end) / 2);
    
    var root, node1, node2, node3;
    
    if (nums.length <= 3) {
        node1 = new TreeNode(nums[0]);     
        if (nums.length === 1) {
            return node1;
        }
        
        node2 = new TreeNode(nums[1]);
        node2.left = node1;
        if (nums.length === 2) {
            return node2;
        }
        
        node3 = new TreeNode(nums[2]);
        node2.right = node3;
        return node2;
         
    } else {
        root = new TreeNode(nums[middle]);
        root.left = sortedArrayToBST(nums.slice(0, middle));
        root.right = sortedArrayToBST(nums.slice(middle + 1));
    }
    return root;
};

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var maxDeepth = function(root) {
    if(root === null) {
        return 0;
    } else {
        return Math.max(maxDeepth(root.left), maxDeepth(root.right)) + 1;
    }
}
var isBalanced = function(root) {
    if(root === null) {
        return true;
    }
    var leftDeepth = maxDeepth(root.left);
    var rightDeepth = maxDeepth(root.right);
    
    if(Math.abs(leftDeepth - rightDeepth) <= 1 
        && isBalanced(root.left)
        && isBalanced(root.right)
    ) {
        return true;
    } else {
        return false;
    }
};

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var minDepth = function(root) {
    if(root === null) {
        return 0;
    }
    var leftDepth = minDepth(root.left);
    var rightDepth = minDepth(root.right);
    
    if(leftDepth !== 0 && rightDepth !== 0) {
        return Math.min(leftDepth, rightDepth) + 1;
    } else if(leftDepth === 0) {
        return rightDepth + 1;
    } else {
        return leftDepth + 1;
    }
};

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} sum
 * @return {boolean}
 */
var hasPathSum = function(root, sum) {
    if(root == null) {
        return false;
    }
    if(root.left == null && root.right == null && sum == root.val) {
        return true;
    }
    if(hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val)) {
        return true;
    } else {
        return false;
    }
};

/**
 * @param {number} numRows
 * @return {number[][]}
 */
var generate = function(numRows) {
    if(numRows === 0) {
        return [];
    } 
    if(numRows === 1) {
        return [[1]];
    }
    
    var ret = [[1]];
    for(var i = 1; i < numRows; i++) {
        ret.push([]);
        for(var j = 0; j < ret[i - 1].length - 1; j++) {
            ret[i].push(ret[i-1][j] + ret[i-1][j + 1]);
        }
        ret[i].unshift(1);
        ret[i].push(1);
    }
    return ret;
};

/**
 * @param {number} rowIndex
 * @return {number[]}
 */
var getRow = function(rowIndex) {
    var ret = [];
    ret[0] = 1;
    for(var i = 1; i <= rowIndex; i++ ) {
        ret[i] = 1;
        for(j = i - 1; j > 0; j--) {
            ret[j] = ret[j] + ret[j - 1];
        }
    }
    return ret;
};

/**
 * @param {number[][]} triangle
 * @return {number}
 */
var minimumTotal = function(triangle) {
    if (triangle.length === 0 || triangle[0].length === 0) return 0;
    var dp = Array(triangle.length).fill(null);
    dp[0] = triangle[0][0];
    var minv = dp[0];
    var prev;
    
    for (var i = 1; i < triangle.length; i++) {
        prev = dp.slice(); // copy dp
        dp[0] = prev[0] + triangle[i][0];
        for (var j = 1; j < triangle[i].length - 1; j++) {
            dp[j] = Math.min(prev[j - 1], prev[j]) + triangle[i][j];        
        }
        dp[triangle[i].length - 1] = prev[triangle[i].length - 2] + triangle[i][triangle[i].length - 1];
    }
    
    return Math.min.apply(null, dp);
};  

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(prices) {
    var min = Number.MAX_VALUE;
    var profit = 0;
    
    for(var i = 0; i < prices.length; i++) {
        min =  Math.min(min, prices[i]);   
        profit = Math.max(profit, prices[i] - min);
    }
    
    return profit;
};

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(prices) {
    var len = prices.length;
    var minsum = 0;
    var maxsum = 0;
    var isUp;
    var lastIsUp;
    
    for(var i = 0; i < prices.length - 1; i++) {
        if(prices[i] < prices[i+1]) {
            isUp = true;
        } else {
            isUp = false;
        }
        if(isUp && (i === 0 || lastIsUp === false)) {
            minsum += prices[i];
        }
        if(lastIsUp && isUp === false) {
            maxsum += prices[i];
        }
        if(isUp && i === prices.length - 2) {
            maxsum += prices[i + 1];
        }
        lastIsUp = isUp;
    }
    return maxsum - minsum;
};

/**
 * @param {string} s
 * @return {boolean}
 */
var isPalindrome = function(s) {
    var str = s.split('').filter(function(c) {
        return c.match(/[\w\d]/);
    }).join('').toLowerCase();
    
    if(str === '') {
        return true;
    }
    var i = 0;
    var j = str.length - 1;
    while(i < j) {
        if(str[i] != str[j]) {
            return false;
        }
        i++;
        j--;
    }
    return true;
};