var findDiagonalOrder = function(matrix) {
    // if matrix is empty, just return
    if(matrix.length == 0) 
        return matrix;
    let rows = matrix.length;
    let cols = matrix[0].length;
    // create an 2d-array that store every diagonal numbers
    let diagonalArray = new Array(rows + cols -1).fill(0).map(() => []);
    
    for(let i=0; i < rows; i++){
        for(let j=0; j< cols; j++){
            let key = i + j;
            let number = matrix[i][j];
            if(key % 2 == 0){
                // Within even diagonal use unshift to store number
                // this means we store number in upper-right direction
                diagonalArray[key].unshift(number);
                // console.log(diagonalArray);
            } 
            else{
                // Within odd diagonal use push to store number
                // this means we store number in bottom-left direction
                diagonalArray[key].push(number);
                // console.log(diagonalArray);
            }
        }
    }
    // just merge all arrays in diagonal array and return result
    return diagonalArray.reduce((result, array) => {
        result.push(...array);
        return result
    }, [])
};

var swapPairs = function(head) {
    // create a node which always point to head of the linst
    let temp = new ListNode(0, head);
    // At the beginning, current point to the head
    let current = temp;
    while(current.next != null && current.next.next != null){
        // need to set two variables to point first and second node
        let firstNode = current.next;
        let secondNode = current.next.next;
        // current point to second node which means second node will be head
        current.next = secondNode;
        // make first node link to 3rd node
        firstNode.next = secondNode.next;
        // make seconde node link to first node
        secondNode.next = firstNode;
        // make current point to the first node of next pairwise nodes
        current = current.next.next;
    }
    return temp.next
};

var numDecodings = function(s) {
    if(s.length === 0 || s == null) return 0;
    if(s[0] == '0') return 0;
    
    let dp = new Array(s.length+1).fill(0);
    
    // dp[i] is the ways to decode string that length is i
    dp[0] = 1;
    dp[1] = 1;
    for(let i = 2; i <= s.length; i++){
        
        const lastOneDigit = Number(s.slice(i-1, i));
        if(lastOneDigit <= 9 && lastOneDigit >= 1) {
            dp[i] += dp[i-1];
        }
         
        const lastTwoDigits = Number(s.slice(i-2, i));
        if(lastTwoDigits <= 26 && lastTwoDigits >= 10) {
            dp[i] += dp[i-2];
        }
            
    }
    return dp[s.length];
};

var minJumps = function(arr) {
  if (arr.length === 1) return 0;
  const sameValIdx = new Map();
  for (let i = arr.length - 1; i >= 0; i--) {
    const val = arr[i];
    if (!sameValIdx.has(val)) sameValIdx.set(val, []);
    sameValIdx.get(val).push(i);
  }
  
  const seen = new Set();
  seen.add(0);
  const queue = [[0, 0]];
  while (queue.length) {
    const [idx, step] = queue.shift();
    
    if (idx - 1 >= 0 && !seen.has(idx - 1)) {
      queue.push([idx - 1, step + 1]);
      seen.add(idx - 1);
    }
    if (idx + 1 < arr.length && !seen.has(idx + 1)) {
      if (idx + 1 === arr.length - 1) return step + 1; // You have to check here to handle this case [7,7,7,7,7...]
      queue.push([idx + 1, step + 1]);
      seen.add(idx + 1);
    }
    
    const targetArr = sameValIdx.get(arr[idx]);
    for (let j = 0; j < targetArr.length; j++) {
      const i = targetArr[j];
      if (!seen.has(i) && i !== idx - 1 && i !== idx + 1) {
        if (i === arr.length - 1) return step + 1; // You have to check here to handle this case [7,7,7,7,7...]
        queue.push([i, step + 1]);
        seen.add(i);
      }
    }
  }
};

var pseudoPalindromicPaths  = function(root) {
    
    let checker = new Array(10).fill(0);
    let res = 0;
    
    function checkOdd(){
        let odd = 0;
        for(let i=0; i <= 9; i++){
            if(checker[i] % 2 != 0) odd++;
        }
        
        return odd > 1 ? false : true;
    }
    
    function dfs(node){
        if(!node) return;
        
        checker[node.val]++;
        if(!node.left && !node.right) {
            if(checkOdd()){
                res++;
            }
        }
        else {
            dfs(node.left);
            dfs(node.right);
        }
        
        // backtrack
        checker[node.val]--;
    }
    
    dfs(root);
    return res;
};