/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isBalanced = function (root) {
  if (root === null) {
    return true;
  }
  return checkDepth(root) !== false;
};

const checkDepth = (node) => {
  if (node === null) {
    return 0;
  }

  // 각각 false 혹은 왼쪽/오른쪽 자식의 최대 깊이
  const left = checkDepth(node.left);
  const right = checkDepth(node.right);

  if (left === false || right === false || Math.abs(left - right) > 1) {
    return false;
  }

  // 트리의 가장 깊은 길이를 return
  return Math.max(left, right) + 1;
};

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var minDepth = function (root) {
  if (root === null) {
    return 0;
  }

  if (root.left === null) {
    return minDepth(root.right) + 1;
  }
  if (root.right === null) {
    return minDepth(root.left) + 1;
  }

  return 1 + Math.min(minDepth(root.left), minDepth(root.right));
};

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} targetSum
 * @return {boolean}
 */
var hasPathSum = function (root, targetSum) {
  if (root === null) {
    return false;
  }

  const calculatedValue = targetSum - root.val;
  if (root.left === null && root.right === null) {
    if (calculatedValue === 0) {
      return true;
    }
    return false;
  }

  return (
    hasPathSum(root.left, calculatedValue) ||
    hasPathSum(root.right, calculatedValue)
  );
};

/**
 * @param {number} numRows
 * @return {number[][]}
 */
var generate = function (numRows) {
  if (numRows === 1) {
    return [[1]];
  }

  if (numRows === 2) {
    return [[1], [1, 1]];
  }

  let rows = [[1], [1, 1]];

  for (let i = 2; i < numRows; i++) {
    let prevRow = rows[i - 1];

    let currentRow = [1];
    for (let j = 0; j < prevRow.length - 1; j++) {
      currentRow.push(prevRow[j] + prevRow[j + 1]);
    }
    currentRow.push(1);

    rows.push(currentRow);
  }
  return rows;
};

/**
 * @param {number} rowIndex
 * @return {number[]}
 */
var getRow = function (rowIndex) {
  if (rowIndex === 0) {
    return [1];
  }

  if (rowIndex === 1) {
    return [1, 1];
  }

  let rows = [[1], [1, 1]];

  for (let i = 2; i <= rowIndex; i++) {
    let prevRow = rows[i - 1];

    let currentRow = [1];

    for (let j = 0; j < prevRow.length - 1; j++) {
      currentRow.push(prevRow[j] + prevRow[j + 1]);
    }
    currentRow.push(1);

    rows.push(currentRow);
  }

  return rows[rowIndex];
};

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function (prices) {
  let based = prices[0];
  let result = 0;

  for (let i = 1; i < prices.length; i++) {
    let diff = prices[i] - based;

    if (diff < result) {
      if (diff < 0) {
        based = prices[i];
      }
    } else {
      result = diff;
    }
  }

  return result;
};

/**
 * @param {string} s
 * @return {boolean}
 */
var isPalindrome = function (s) {
  const lowerCaseString = s.toLowerCase();
  let onlyLowerCase = '';

  for (let i = 0; i < lowerCaseString.length; i++) {
    const regex = /^[a-z0-9]/;
    if (regex.test(lowerCaseString[i])) {
      onlyLowerCase += lowerCaseString[i];
    }
  }

  let reverseOnlyLowerCase = '';

  for (let j = onlyLowerCase.length - 1; j >= 0; j--) {
    reverseOnlyLowerCase += onlyLowerCase[j];
  }

  console.log(onlyLowerCase, reverseOnlyLowerCase);

  return onlyLowerCase === reverseOnlyLowerCase;
};

/**
 * @param {string} s
 * @return {number}
 */
var romanToInt = function (s) {
  let total = 0;

  for (let i = 0; i < s.length; i++) {
    if (values[s[i]] < values[s[i + 1]]) {
      total += values[s[i + 1]] - values[s[i]];
      i++;
    } else {
      total += values[s[i]];
    }
  }
  return total;
};

const values = {
  I: 1,
  V: 5,
  X: 10,
  L: 50,
  C: 100,
  D: 500,
  M: 1000,
};

/**
 * @param {number[]} nums
 * @return {number}
 */
var singleNumber = function (nums) {
  let hashMap = {};

  for (let i = 0; i < nums.length; i++) {
    const currentNum = nums[i];
    if (hashMap[currentNum]) {
      hashMap[currentNum]++;
    } else {
      hashMap[currentNum] = 1;
    }
  }

  return Number(getKeybyValue(hashMap, 1));
};

const getKeybyValue = (object, value) => {
  return Object.keys(object).find((key) => object[key] === value);
};

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

  const [baseWord, ...rest] = strs;

  for (let i = 0; i <= baseWord.length; i++) {
    for (let j = 0; j < strs.length; j++) {
      if (baseWord[i] !== strs[j][i]) {
        return baseWord.slice(0, i);
      }
    }
  }

  return baseWord;
};

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

  for (let i = 0; i <= strs[0].length; i++) {
    if (!strs.every((string) => string[i] === strs[0][i])) {
      return strs[0].slice(0, i);
    }
  }

  return strs[0];
};