var reachingPoints = function(sx, sy, tx, ty) {
  const history = {};
  let preRound = [[sx, sy]], round = [],
      x, y, newPosStr;
  while(preRound.length)
  {
    for(let pos of preRound)
    {
      x = pos[0];
      y = pos[1];
      if(nextPos(x + y, y, tx, ty, round, history)) return true;
      if(nextPos(x, x + y, tx, ty, round, history)) return true;
    }
    preRound = round;
    round = [];
  }
  return false;
};

function nextPos(x, y, sx, sy, round, history){
  if(x === sx && y === sy) return true;
  if(x > sx || y > sy) return false;
  let newPosStr = x + '_' + y; // Let's encode position.
  if(history[newPosStr]) return;
  round.push([x, y]);
  history[newPosStr] = true;
  return false;
}

var reachingPoints = function(sx, sy, tx, ty) {
  let [x, y] = [tx, ty];
  while(x >= sx && y >= sy)
  {
    if(x === sx && y === sy) return true;
    if(x === sx) return (y - sy) % x === 0;
    if(y === sy) return (x - sx) % y === 0;    
    [x, y] = (x > y) ? [x - y, y] : [x, y - x];
  }
  return false;
};

/**
 * @param {number[]} nums
 * @param {number} threshold
 * @return {number}
 */
var smallestDivisor = function(nums, threshold) {
  let start = 1, end = Math.max(...nums);
  if (nums.length === threshold) return end;

  while(start < end) {
    let mid = (start + end) / 2 | 0;

    let sum = 0;
    for(const num of nums) {
      sum += Math.ceil(num / mid);
    }

    sum > threshold ? (start = mid + 1) : (end = mid);
  }
  return start;
};

var findLHS = function(nums) {
  const countTable = countNums(nums);
  let max = 0;
  for(let num in countTable)
  {
    num = Number(num); // 注意这里转一下!!!
    if(countTable.hasOwnProperty(num + 1)) max = Math.max(max, countTable[num] + countTable[num + 1]);
    if(countTable.hasOwnProperty(num - 1)) max = Math.max(max, countTable[num] + countTable[num - 1]);
  }
  return max;
};

function countNums(nums){
  const countTable = {};
  for(let num of nums)
  {
    if(!countTable[num]) countTable[num] = 0;
    countTable[num] += 1;
  }
  return countTable;
}

const cumSum = nums => {
  const sumNums = [0], len = nums.length;
  for(let i = 1; i <= len; i++) {
    sumNums[i] = sumNums[i - 1] + nums[i - 1];
  }
  return sumNums;
}

const cumNums = nums => {
  const cumedNums = [0], len = nums.length;
  for(let i = 1; i <= len; i++) {
    cumedNums[i] = cumedNums[i - 1] + nums[i - 1];
  }
  return cumedNums;
}

/**
 * @param {number[][]} mat
 * @param {number} K
 * @return {number[][]}
 */
var matrixBlockSum = function(mat, K) {
  const cumedRowMat = mat.map(cumNums);
  const rowN = mat.length, colN = mat[0].length;
  
  const sumMatrixBlock = (i, j) => {
    const startRow = i - K < 0 ? 0 : i - K;
    const endRow = i + K >= rowN ? rowN - 1 : i + K;
    const startCol = j - K < 0 ? 0 : j - K;
    const endCol = j + K >= colN ? colN - 1 : j + K;

    let sum = 0;
    for(let row = startRow; row <= endRow; row++) {
      const cumedRowMatRow = cumedRowMat[row];
      const rangeSum = cumedRowMatRow[endCol + 1] - cumedRowMatRow[startCol];      
      sum += rangeSum;
    }
    return sum;
  }
  
  const blockSumMat = new Array(rowN).fill(null).map(() => new Array(colN).fill(0));
  for(let row = 0; row < rowN; row++) {
    for(let col = 0; col < colN; col++) {
      blockSumMat[row][col] = sumMatrixBlock(row, col);
    }    
  }
  return blockSumMat;
}

var findSecondMinimumValue = function(root) {
  if(!root.left) return -1;
    
  let [leftVal, rightVal] = [root.left.val, root.right.val];  
  if(leftVal === root.val) leftVal = findSecondMinimumValue(root.left);
  if(rightVal === root.val) rightVal = findSecondMinimumValue(root.right);

  // 保证leftVal <= rightVal, 我们这里做一次交换!
  if(leftVal > rightVal) [leftVal, rightVal] = [rightVal, leftVal];
  
  if(-1 === leftVal) return rightVal;
  return leftVal;
};

var findMaxLength = function(nums) {
  const sum = [0], len = nums.length;
  for(let i = 0, num; i < len; i++) sum[i + 1] = nums[i] + sum[i];  
  let slow, fast, max = 0;
  for(slow = 0; slow < len; slow++)
  {
    for(fast = slow + 1; fast < len; fast++)
    {
      if((sum[fast + 1] - sum[slow]) * 2 === (fast - slow + 1)) 
      {
        max = Math.max(max, fast - slow + 1);
      }
    }    
  }
  return max;
};

var findMaxLength = function(nums) {
  const sums = [0], offsetToIdxs = { 0: [-1] }, len = nums.length;
  let max = 0, offset;
  for(let i = 0; i < len; i++) sums[i + 1] = nums[i] + sums[i];
  for(let i = 0; i < len; i++)
  {
    offset = 2 * sums[i + 1] - i - 1;
    if(!offsetToIdxs[offset]) offsetToIdxs[offset] = [];
    offsetToIdxs[offset].push(i);
    max = Math.max(max, i - offsetToIdxs[offset][0]);
  }
  return max;
};

const VERTEX_STATUS = {
  unvisit: 0,
  water: 1,
  visited: 2
}

/**
 * @param {number[][]} grid
 * @return {number}
 */
var closedIsland = function(matrix) {
  const rowN = matrix.length, colN = matrix[0].length;
  let count = 0;
  for(let row = 0; row < rowN; row++) {
    for(let col = 0; col < colN; col++) {
      if(matrix[row][col] === VERTEX_STATUS.unvisit) {
        bfs(matrix, [{ row, col }]) && (count += 1);
      }
    }
  }
  return count;
};

const TOWARDS = [
  [-1, 0],
  [0, 1],
  [1, 0],
  [0, -1]
];

const getNbrs = (sRow, sCol, rowN, colN) => {
  const nbrs = [];
  for(const [dRow, dCol] of TOWARDS) {
    const [row, col] = [sRow + dRow, sCol + dCol];
    if(0 <= row && row < rowN && 0 <= col && col < colN) {
      nbrs.push({ row, col });
    }
  }
  return nbrs;
}

const bfs = (matrix, startVs) => {
  const rowN = matrix.length, colN = matrix[0].length;  
  let [vs, nextVs] = [startVs, []], isClosed = true;
  while(vs.length > 0) {
    for(const v of vs) {
      if(
        v.row === 0 || (v.row === rowN - 1) || 
        v.col === 0 || (v.col === colN - 1)
      ) {
        isClosed = false;
      }
      const nbrs = getNbrs(v.row, v.col, rowN, colN);      
      for(const nbr of nbrs) {
        if(matrix[nbr.row][nbr.col] === VERTEX_STATUS.unvisit) {
          nextVs.push(nbr);
          matrix[nbr.row][nbr.col] = VERTEX_STATUS.visited;
        }
      }
    }
    [vs, nextVs] = [nextVs, []];
  }
  return isClosed;
}

var numIslands = function(grid) {
  if(!grid || !grid[0]) return 0;
  const rowN = grid.length, colN = grid[0].length;
  let count = 0;
  for(let row = 0; row < rowN; row++)
  {
    for(let col = 0; col < colN; col++)
    {
      count += dfs(grid, row, col) ? 1 : 0;
    }
  }
  return count;
};

function dfs(grid, row, col){    
  if(!grid[row] || !grid[row][col] || '0' === grid[row][col]) return 0;
  grid[row][col] = '0';
  return 1 + dfs(grid, row - 1, col) + dfs(grid, row + 1, col) +
    dfs(grid, row, col - 1) +dfs(grid, row, col + 1);
}

var maxAreaOfIsland = function(grid) {
  if(!grid || !grid[0]) return 0;
  const rowN = grid.length, colN = grid[0].length;
  let maxArea = 0, area;
  for(let row = 0; row < rowN; row++) 
  {
    for(let col = 0; col < colN; col++) 
    {
      area =  dfs(grid, row, col);
      maxArea = maxArea > area ? maxArea : area;
    }
  }
  return maxArea;
};

function dfs(grid, row, col){
  if(!grid[row] || !grid[row][col]) return 0;
  grid[row][col] = 0;
  return 1 + dfs(grid, row - 1, col) + dfs(grid, row + 1, col) +
    dfs(grid, row, col - 1) + dfs(grid, row, col + 1);
}

var floodFill = function(image, sr, sc, newColor) {
  const rowN = image.length, colN = image[0].length;
  if(image[sr][sc] === newColor) return image;
  return dfs(image, sr, sc, image[sr][sc], newColor);
};

function dfs(grid, row, col, oldColor, newColor){
  if(!grid[row] || oldColor !== grid[row][col]) return grid;
  grid[row][col] = newColor;
  return dfs(grid, row - 1, col, oldColor, newColor) && 
    dfs(grid, row + 1, col, oldColor, newColor) &&
    dfs(grid, row, col - 1, oldColor, newColor) && 
    dfs(grid, row, col + 1, oldColor, newColor);
}

var findCircleNum = function(M) {
  if(!M || !M[0]) return 0;
  const len = M.length;
  let count = 0;
  for(let n = 0; n < len; n++)
  {
    count += dfs(M, n, n);
  }
  return count;
};

function dfs(M, row, col){
  if(!M[row][col]) return 0;
  M[row][col] = M[col][row] = 0;
  const n = M.length;
  for(let i = 0; i < n; i++) 
  {
    dfs(M, row, i);
    dfs(M, col, i);
  }
  return 1;
}

var islandPerimeter = function(grid) {
  const rowN = grid.length, colN = grid[0].length;
  for(let row = 0; row < rowN; row++)
  {
    for(let col = 0; col < colN; col++) 
    {
      if(grid[row][col]) return dfs(grid, row, col);
    }
  }
};
function dfs(grid, row, col){
  if(!grid[row] || !grid[row][col]) return 1;
  if(2 === grid[row][col]) return 0;
  grid[row][col] += 1; // this island is checked !!!
  return dfs(grid, row - 1, col) + dfs(grid, row + 1, col) +
    dfs(grid, row, col - 1) + dfs(grid, row, col + 1);
}

var islandPerimeter = function(grid) {
  const rowN = grid.length, colN = grid[0].length;
  let islandCount = 0, innerEdgeCount = 0;
  for(let row = 0; row < rowN; row++)
  {
    for(let col = 0; col < colN; col++) 
    {
      if(!grid[row][col]) continue;
      islandCount += 1;
      if(grid[row][col + 1] ) innerEdgeCount += 1; 
      if(grid[row + 1] && grid[row + 1][col]) innerEdgeCount += 1;
    }
  }
  return 4 * islandCount - 2 * innerEdgeCount;
};

var countBattleships = function(board) {
  const rowN = board.length, colN = board[0].length;
  let count = 0, tmp;
  for(let row = 0; row < rowN; row++)
  {
    for(let col = 0; col < colN; col++)
    {
      if(!matrixVal(board, row, col)) continue;
      if(0 === matrixVal(board, row - 1, col) + matrixVal(board, row, col - 1)) count += 1;
      if(2 === matrixVal(board, row + 1, col) + matrixVal(board, row, col + 1)) return 0; // 这是一个非法的排列
    }
  }
  return count;
};

function matrixVal(matrix, row, col){
  if(!matrix[row] || !matrix[row][col]) return 0;
  return matrix[row][col] === '.' ? 0 : 1;
}

var judgeCircle = function(moves) {
  let posX = posY = 0;
  for(let move of moves)
  {
    switch(move)
    {
    case 'U':
      posY -= 1;
      break;
    case 'D':
      posY += 1;
      break;
    case 'L':
      posX -= 1;
      break;
    case 'R':
      posX += 1;
      break;
    default:
      throw '位置的指令: ' + move;
    }
  }
  return 0 === posX && 0 === posY;
};

var judgeCircle = function(moves) {
  const record = { R: 0, L: 0, U: 0, D: 0 };
  for(let move of moves) record[move] += 1;
  return (record.R === record.L) && (record.U === record.D);
};

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root1
 * @param {TreeNode} root2
 * @return {boolean}
 */
var leafSimilar = function(root1, root2) {
  const [leaves1, leaves2] = [dfs(root1), dfs(root2)];  
  if(leaves1.length !== leaves2.length) return false;
  for(let i = 0, len = leaves1.length; i < len; i++) {
    if(leaves1[i].val !== leaves2[i].val) return false;
  }
  return true;
};

const dfs = (root, vs = []) => {
  if(!root) return vs;
  if(!root.left && !root.right) {
    vs.push(root);
  }
  dfs(root.left, vs);
  dfs(root.right, vs);
  return vs;
}

var knightProbability = function(N, K, r, c) {
  let count = dfs(N, K, r, c, 0);
  return count / (8 ** K);
};

const Moves = [[-2, -1], [-2, 1], [2, -1], [2, 1], [-1, -2], [1, -2], [-1, 2], [1, 2]];
function dfs(N, maxDeep, posX, posY, deep){
  const isOnTheBoard = (posX >= 0 && posX < N && posY >= 0 && posY < N);
  if(!isOnTheBoard) return 0;
  if(deep >= maxDeep) return 1;

  let count = 0;
  for(let move of Moves) count += dfs(N, maxDeep, posX + move[0], posY + move[1], deep + 1) ;
  return count;
}

var knightProbability = function(N, K, r, c) {
  const record = { }; // 三维矩阵...算了还是hash表好点
  const count = dfs(N, K, r, c, 0, record);
  return count / (8 ** K);
};

const Moves = [[-2, -1], [-2, 1], [2, -1], [2, 1], [-1, -2], [1, -2], [-1, 2], [1, 2]];
function dfs(N, maxDeep, posX, posY, deep, record){
  const isOnTheBoard = (posX >= 0 && posX < N && posY >= 0 && posY < N);
  if(!isOnTheBoard) return 0;
  if(maxDeep === deep) return 1;
  
  // 查表, 如果有记录那么直接返回记录!!!
  let count = record[encodeStatus(posX, posY, maxDeep - deep)];
  if(count) return count;

  count = 0;
  for(let move of Moves) count += dfs(N, maxDeep, posX + move[0], posY + move[1], deep + 1, record);
  record[encodeStatus(posX, posY, maxDeep - deep)] = count;
  return count;
}

function encodeStatus(posX, posY, step){
  return [posX, posY, step].join('_');
}

var integerReplacement = function(n) {
  const record = { 1: Number.MAX_SAFE_INTEGER };
  dfs(record, n, -1);
  return record[1];
};

function dfs(record, n, distance){
  if(record[n] > ++distance) record[n] = distance;
  if(1 === n || distance >= record[1]) return;
  n % 2 ? (dfs(record, n + 1, distance) || dfs(record, n - 1, distance)) :
    dfs(record, n / 2, distance);
}

var openLock = function(deadends, target) {
  if(-1 !== deadends.indexOf('0000')) return -1;
  const record = { "0000": 0 };
  for(let deadend of deadends) record[deadend] = -1;
  return bfs(record, [[0, 0, 0, 0]], target, 0);
};

function bfs(record, statusList, target, deep){
  if(!statusList.length) return -1;
  let len = statusList.length, status, statusNum, nextStatus;
  while(len--)
  {
    status = statusList.shift();
    statusNum = status.join('');
    if(statusNum === target) return deep;

    for(let i = 0; i < 4; i++)
    {
      for(let j of [1, 9])
      {
        nextStatus = status.slice();
        nextStatus[i] = (status[i] + j) % 10;
        if(undefined !== record[nextStatus.join('')]) continue;
        record[nextStatus.join('')] = deep + 1;
        statusList.push(nextStatus);
      }
    }
  }
  return bfs(record, statusList, target, deep + 1);
}

var productExceptSelf = function(nums) {
  const len = nums.length, leftProducts = [], rightProducts = [], ans = [];

  leftProducts[0] = nums[0];
  for(let i = 1; i < len; i++) leftProducts[i] = leftProducts[i - 1] * nums[i];
  rightProducts[len - 1] = nums[len - 1];
  for(let i = len - 2; i >= 0; i--) rightProducts[i] = rightProducts[i + 1] * nums[i];
  
  ans[0] = rightProducts[1];
  ans[len - 1] = leftProducts[len - 2];
  for(let i = 1; i < len - 1; i++)
  {
    ans[i] = leftProducts[i - 1] * rightProducts[i + 1];
  }
  
  return ans;
};

const ALPHA_MAP = {
  '1': 'a',
  '2': 'b',
  '3': 'c',
  '4': 'd',
  '5': 'e',
  '6': 'f',
  '7': 'g',
  '8': 'h',
  '9': 'i',
  '10#': 'j',
  '11#': 'k',
  '12#': 'l',
  '13#': 'm',
  '14#': 'n',
  '15#': 'o',
  '16#': 'p',
  '17#': 'q',
  '18#': 'r',
  '19#': 's',
  '20#': 't',
  '21#': 'u',
  '22#': 'v',
  '23#': 'w',  
  '24#': 'x',
  '25#': 'y',
  '26#': 'z',  
}

/**
 * @param {string} s
 * @return {string}
 */
var freqAlphabets = function(text) {
  let offset = 0, alphas = [], len = text.length;
  while(offset < len) {
    const token = (text[offset + 2] === '#') ?
          text.slice(offset, offset + 3) : 
          text.slice(offset, offset + 1);
    alphas.push(ALPHA_MAP[token]);
    offset += token.length;
  }
  return alphas.join('');
};

/**
 * @param {number} num
 * @return {number}
 */
var addDigits = function(num) {
  while(num > 9) {
    num = addDigitsOnce(num);
  }
  return num;
};

const addDigitsOnce = num => {
  let sum = 0;
  while(num > 0) {
    sum += (num % 10);
    num = (num / 10 | 0);
  }
  return sum;
}

var getMinimumDifference = function(root) {
  const vals = inOrder(root, []);  
  let min = Number.MAX_SAFE_INTEGER;
  for(let i = 1, len = vals.length; i < len; i++)
  {
    min = Math.min(min, vals[i] - vals[i - 1]);
  }
  return min;
};

function inOrder(root, vals){
  if(!root) return vals;
  inOrder(root.left, vals);
  vals.push(root.val);
  inOrder(root.right, vals);
  return vals;
}

var sumEvenGrandparent = function(root, parent = null, grandParent = null) {
  if(!root) return 0;
  const isAccept = grandParent && (grandParent.val % 2 === 0);
  const val = isAccept ? root.val : 0;
  return val + sumEvenGrandparent(root.left, root, parent) +
    sumEvenGrandparent(root.right, root, parent);
};

var diameterOfBinaryTree = function(root) {
  let maxDiameter = 0;
  const treeHeight = root => {
    if(!root) return 0;
    const leftHeight = treeHeight(root.left);
    const rightHeight = treeHeight(root.right);
    maxDiameter = Math.max(maxDiameter, leftHeight + rightHeight);
    return Math.max(leftHeight, rightHeight) + 1;
  }
  treeHeight(root);
  return maxDiameter;
};

var removeLeafNodes = function(root, target) {
  postOrder(root, target, () => root = null);
  return root;
};

const postOrder = (root, target, delSelfFn) => {
  if(!root) return;
  postOrder(root.left, target, () => root.left = null);
  postOrder(root.right, target, () => root.right = null);
  if(
    root.val === target &&
    !root.left &&
    !root.right
  ) {
    delSelfFn();
  }
}

var removeLeafNodes = function(root, target) {
  return postOrder(root, target);
};

const isLeaf = root => root && !root.left && !root.right;

const postOrder = (root, target) => {
  if(!root) return null;
  root.left = postOrder(root.left, target);
  root.right = postOrder(root.right, target);  
  return (isLeaf(root) && root.val === target) ? null : root;
}

var findBottomLeftValue = function(root) {
  if(!root) return null;
  let row = [root], value;
  while(row.length)
  {
    value = row[0].val;    
    row = bfs(row);
  }
  return value
};

function bfs(row){
  let nextRow = [];
  for(let node of row)
  {
    if(node.left) nextRow.push(node.left);
    if(node.right) nextRow.push(node.right);
  }
  return nextRow;
}

var findBottomLeftValue = function(root) {
  if(!root) return null;
  const nice = { deep: 0, val: root.val };
  dfs(root, 0, nice);
  return nice.val;
};

function dfs(root, deep, nice){
  if(!root) return;
  if(!root.left && !root.right)
  {
    if(deep > nice.deep)
    {
      nice.deep = deep;
      nice.val = root.val;
    }
    return;
  }
  dfs(root.left, deep + 1, nice);
  dfs(root.right, deep + 1, nice);
}

var rangeSumBST = function(root, L, R) {
  if(!root) return 0;
  let { left, right, val } = root;
  if(val < L || val > R) val = 0;
  return val + rangeSumBST(left, L, R) + rangeSumBST(right, L, R);
};

var rangeSumBST = function(root, L, R) {
  if(!root) return 0;
  let { left, right, val } = root;
  const leftSum = (val >= L) ? rangeSumBST(left, L, R) : 0;
  const rightSum = (val <= R) ? rangeSumBST(right, L, R): 0;  
  if(val < L || val > R) val = 0;
  return val + leftSum + rightSum;
};

var sortArrayByParityII = function(nums) {
  let evenIdx = 0, oddIdx = 1, len = nums.length;
  while(evenIdx < len) {
    [nums[evenIdx], nums[oddIdx]] = [nums[oddIdx], nums[evenIdx]];
    while(nums[evenIdx] % 2 === 0) evenIdx += 2;
    while(nums[oddIdx] % 2 === 1) oddIdx += 2;
  }
  return nums;
};

/**
 * @param {number[]} arr
 * @return {boolean}
 */
var checkIfExist = function(nums) {
  const record = {};
  for(const num of nums) {
    record[num] ? record[num] += 1 : record[num] = 1;
    const isZeroDouble = num === 0 && record[num] === 2;
    const isNonZeroDouble = num !== 0 && (
      record[num * 2] || (num % 2 === 0 && record[num / 2])
    );
    if(isZeroDouble || isNonZeroDouble) {
       return true;
    }
  }    
  return false;
};

const ALPHAS = [];
for(let i = 0; i < 26; i++) {
  ALPHAS.push(String.fromCharCode((97 + i)));
}
const countAlpha = s => {
  const record = {};
  for(const alpha of ALPHAS) {
    record[alpha] = 0;
  }
  for(const char of s) {
    record[char] += 1;
  }
  return record;
}

/**
 * @param {string} s
 * @param {string} t
 * @return {number}
 */
var minSteps = function(s, t) {
  const [recordS, recordT] = [countAlpha(s), countAlpha(t)];
  let sum = 0;
  for(const alpha of ALPHAS) {
    sum += (Math.abs(recordS[alpha] - recordT[alpha]));
  }
  return sum / 2;
};

 // 已知 row，col
 k = row - col;
 offset = Math.min(row, col);

/**
 * @param {number[][]} mat
 * @return {number[][]}
 */
var diagonalSort = function(matrix) {
  const rowN = matrix.length, colN = matrix[0].length;
  
  const sortMatrixDiagonal = (row, col) => {
    const nums = [], n = matrix.length;
    for(let k = 0; row + k < rowN && col + k < colN; k++) {
      nums.push(matrix[row + k][col + k]);
    }
    nums.sort((x, y) => x > y ? 1 : -1);

    for(let k = 0; row + k < rowN && col + k < colN; k++) {
      matrix[row + k][col + k] = nums[k];      
    }
  }
  
  for(let row = 0, col = 0; col < colN; col++) {
    sortMatrixDiagonal(row, col);
  }
  for(let row = 0, col = 0; row < rowN; row++) {
    sortMatrixDiagonal(row, col);
  }
  return matrix;
};

/**
 * @param {number[][]} mat
 * @return {number[][]}
 */
var diagonalSort = function(matrix) {
  const rowN = matrix.length, colN = matrix[0].length, record = {};
  for(let row = 0; row < rowN; row++) {
    for(let col = 0; col < colN; col++) {
      const k = row - col;
      if(!record[k]) record[k] = [];
      record[k].push(matrix[row][col]);
    }
  }
  Object.values(record).map(nums => nums.sort((x, y) => x > y ? -1 : 1));  
  for(let row = 0; row < rowN; row++) {
    for(let col = 0; col < colN; col++) {
      const k = row - col;
      matrix[row][col] = record[k].pop();
    }
  }
  return matrix;
};

/**
 * @param {number[][]} bookings
 * @param {number} n
 * @return {number[]}
 */
var corpFlightBookings = function(bookings, n) {
  const record = [];
  for(let i = 1; i <= n; i++) {
    record[i] = 0;
  }
  for(const [start, end, k] of bookings) {
    for(let i = start; i <= end; i++) {
      record[i] += k;
    }
  }
  record.shift();
  return record;
};

/**
 * @param {number[]} A
 * @return {number}
 */
var maxScoreSightseeingPair = function(nums) {
  let max = -1, len = nums.length;  
  nums.forEach((num, i) => {
    let offset = 1, j;
    while(offset <= num && (j = i + offset) < len) {
      const score = nums[i] + nums[j] + i - j;
      (score > max) && (max = score); 
      offset += 1;
    }
  });
  return max;
};

/**
 * @param {number[]} A
 * @return {number}
 */
var maxScoreSightseeingPair = function(nums) {
  const len = nums.length;
  const aNums = nums.map((n, i) => n + i);
  const bNums = nums.map((n, j) => n - j);

  const cNums = [];
  cNums[len - 1] = bNums[len - 1];
  for(let i = len - 2; i >= 0; i--) {
    cNums[i] = Math.max(bNums[i], cNums[i + 1]);
  }
  
  aNums.pop();
  const dNums = aNums.map((val, i) => val + cNums[i + 1]);
  const max = Math.max(...dNums);
  return max;
};

var maxScoreSightseeingPair = function(nums) {
  const len = nums.length;
  let tmp = nums[0], max = -1;
  for(let j = 1; j < len; j++) {
    max = Math.max(nums[j] - j + tmp, max);
    tmp = Math.max(tmp, nums[j] + j);
  }
  return max;
};

/**
 * @param {number[][]} coordinates
 * @return {boolean}
 */
var checkStraightLine = function(coordinates) {
  const [[x1, y1], [x2, y2]] = coordinates;
  const [dx, dy] = [x1 - x2, y1 - y2];
  const crossProduct  = x1 * dy - y1 * dx;
  
  for(const [x, y] of coordinates) {
    if(x * dy - y * dx !== crossProduct) return false;
  }
  return true;
};

const TOWARDS = [
  [0, 0],
  [-1, 0],
  [-1, 1],
  [0, 1],
  [1, 1],
  [1, 0],
  [1, -1],
  [0, -1],
  [-1, -1]
];

/**
 * @param {number[][]} M
 * @return {number[][]}
 */
var imageSmoother = function(matrix) {
  const rowN = matrix.length, colN = matrix[0].length;
  
  const isInRange = (row, col) => row >= 0 && row < rowN && col >= 0 && col < colN;
  
  const getNbrsAverVal = (curRow, curCol) => {
    const vals = [];
    TOWARDS.forEach( ([dRow, dCol]) => {
      const [row, col] = [curRow + dRow, curCol + dCol];
      isInRange(row, col) && vals.push(matrix[row][col]);
    });
    const sum = vals.reduce((total, val) => total += val, 0);
    const averVal = sum / vals.length | 0;
    return averVal;
  };
  
  const smoothMatrix = matrix.map((nums, row) => {
    return nums.map((num, col) => getNbrsAverVal(row, col));
  });
  
  return smoothMatrix;
};

const DIGITS = "123456789";
const sequentialNums = [];
for(let offset = 0; offset < DIGITS.length; offset++) {
  for(let len = 1; offset + len <= DIGITS.length; len++) {
    sequentialNums.push(Number(DIGITS.substr(offset, len)));
  }
}
sequentialNums.sort((x, y) => x > y ? 1 : -1);

var sequentialDigits = function(low, high) {
  return sequentialNums.filter(num => num >= low && num <= high);
};

/**
 * @param {number[]} flowerbed
 * @param {number} n
 * @return {boolean}
 */
var canPlaceFlowers = function(flowerbed, n) {
  flowerbed = [1, 0, ...flowerbed, 0, 1];
  let [slow, fast, len, count, delta] = [0, 2, flowerbed.length, 0, 0];
  while(fast < len) {
    while(flowerbed[fast] === 0) fast += 1;
    delta = parseInt((fast - slow) / 2) - 1;
    delta < 0 && (delta = 0);
    count += delta;
    [slow, fast] = [fast, fast + 1];
  }  
  return count >= n;
};

var addToArrayForm = function(A, K) {
  const val = parseInt(A.join('')) + K;
  return val.toString().split('');
};

/**
 * // Definition for a QuadTree node.
 * function Node(val,isLeaf,topLeft,topRight,bottomLeft,bottomRight) {
 *    this.val = val;
 *    this.isLeaf = isLeaf;
 *    this.topLeft = topLeft;
 *    this.topRight = topRight;
 *    this.bottomLeft = bottomLeft;
 *    this.bottomRight = bottomRight;
 * };
 */
/**
 * @param {Node} quadTree1
 * @param {Node} quadTree2
 * @return {Node}
 */
var intersect = function(t1, t2) {  
  if(isTrueLeaf(t1) || isTrueLeaf(t2)) {
    return createQuadTree(true);
  }
  if(isFalseLeaf(t1) && isFalseLeaf(t2)) {
    return createQuadTree(false);
  }
  if(!t1.isLeaf && !t2.isLeaf) {
    const [t1Children, t2Children] = [
      getQuadTreeChildren(t1),
      getQuadTreeChildren(t2)
    ];
    const intersectChildren = [];
    for(let i = 0, len = t1Children.length; i < len; i++) {
      const intersectChild = intersect(t1Children[i], t2Children[i]);
      intersectChildren.push(intersectChild);
    }
    const intersectedTree = createQuadTree(true, intersectChildren);
    const mergedTree = mergeQuadTreeChildren(intersectedTree);
    return mergedTree;
  }
  return !t1.isLeaf ? t1 : t2;
};
const createQuadTree = (val, children) => { 
  const isLeaf = !children;
  if(!children) {
    children = [null, null, null, null];
  }
  return {
    val,
    isLeaf,
    topLeft: children[0],
    topRight: children[1],
    bottomLeft: children[2],
    bottomRight: children[3]
  };
};
const getQuadTreeChildren = (t) => {
  return [t.topLeft, t.topRight, t.bottomLeft, t.bottomRight];
};
const isTrueLeaf = (quadTree) => {
  return quadTree.isLeaf && quadTree.val;
};
const isFalseLeaf = (quadTree) => {
  return quadTree.isLeaf && quadTree.val;
};
const mergeQuadTreeChildren = (t) => {
  const children = getQuadTreeChildren(t);

  const leafCount = children.filter(child => child && child.isLeaf).length;
  if(leafCount !== children.length) {
    return t;
  }
  const vals = children.map(child => child.val);
  const valCount = vals.filter(val => vals[0] === val).length
  if(valCount !== children.length) {
    return t;
  }

  const mergedQuadTree = createQuadTree(vals[0]);
  return mergedQuadTree;
};