My LeetCode Profile

My LeetCode Journal Notion Note

H11. Two Sum

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

Example 1:

plaintext

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

Example 2:

plaintext

Input: nums = [3,2,4], target = 6
Output: [1,2]

Example 3:

plaintext

Input: nums = [3,3], target = 6
Output: [0,1]

Solution:

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
    const hash = {};
    for (let i = 0; i < nums.length; i++) {
        if (nums[i] in hash) return [i, hash[nums[i]]];
        hash[target - nums[i]] = i;
    }
};

H1 2. Add Two Numbers

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example 1:

plaintext

Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]
Explanation: 342 + 465 = 807.

Solution:

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var addTwoNumbers = function (l1, l2, carry = 0) {
    if (!l1 && !l2 && !carry) return null;
    const sum = (l1?.val || 0) + (l2?.val || 0) + carry;
    return new ListNode(sum % 10, addTwoNumbers(l1?.next, l2?.next, sum > 9 ? 1 : 0));
};

H1 14. Longest Common Prefix

Write a function to find the longest common prefix string amongst an array of strings.

If there is no common prefix, return an empty string "".

Example 1:

plaintext

Input: strs = ["flower","flow","flight"]
Output: "fl"

Solution:

/**
 * @param {string[]} strs
 * @return {string}
 */
var longestCommonPrefix = function (strs) {
    strs.sort();
    const l = strs[0], r = strs[strs.length - 1];
    let prefix = "";
    for (let i = 0; i < l.length; i++) {
        if (l[i] !== r[i]) break;
        prefix += l[i];
    }
    return prefix;
};

H1 19. Remove Nth Node From End of List

Given the head of a linked list, remove the nth node from the end of the list and return its head.

Example 1:

plaintext

Input: head = [1,2,3,4,5], n = 2
Output: [1,2,3,5]

Solution:

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} n
 * @return {ListNode}
 */
var removeNthFromEnd = function (head, n) {
    let fast = slow = head;
    for (let i = 0; i < n; i++) {
        fast = fast.next;
    }
    if (!fast) {
        return head.next;
    }
    while (fast.next) {
        fast = fast.next;
        slow = slow.next;
    }
    slow.next = slow.next.next;
 
    return head;
};

Note:

We use fast and slow to reach the n^th^ node from the end of the list cleverly.

H1 21. Merge Two Sorted Lists

You are given the heads of two sorted linked lists list1 and list2.

Merge the two lists into one sorted list. The list should be made by splicing together the nodes of the first two lists.

Return the head of the merged linked list.

Example 1:

plaintext

Input: list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]

Solution:

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} list1
 * @param {ListNode} list2
 * @return {ListNode}
 */
var mergeTwoLists = function (list1, list2) {
    if (!list1) return list2;
    if (!list2) return list1;
    if (list1.val < list2.val) {
        list1.next = mergeTwoLists(list1.next, list2);
        return list1;
    }
    list2.next = mergeTwoLists(list1, list2.next);
    return list2;
};

H1 26. Remove Duplicates from Sorted Array

Given an integer array nums sorted in non-decreasing order, remove the duplicates in-place such that each unique element appears only once. The relative order of the elements should be kept the same. Then return the number of unique elements in nums.

Consider the number of unique elements of nums to be k, to get accepted, you need to do the following things:

Change the array nums such that the first k elements of nums contain the unique elements in the order they were present in nums initially. The remaining elements of nums are not important as well as the size of nums.
Return k.

Example 1:

plaintext

Input: nums = [1,1,2]
Output: 2, nums = [1,2,_]
Explanation: Your function should return k = 2, with the first two elements of nums being 1 and 2 respectively.
It does not matter what you leave beyond the returned k (hence they are underscores).

Constraints:

1 <= nums.length <= 3 * 104
-100 <= nums[i] <= 100
nums is sorted in non-decreasing order.

Solution:

/**
 * @param {number[]} nums
 * @return {number}
 */
var removeDuplicates = function (nums) {
    let count = 1, i = 0;
    for (let j = 1; j < nums.length; j++) {
        if (nums[i] === nums[j]) {
            nums[j] = 101;
        } else {
            i = j;
            count++;
        }
    }
    nums.sort((a, b) => a - b);
    return count;
}

Note: We ought to use a two-pointer approach here. One, that would keep track of the current element in the original array and another one for just the unique elements.

H1 45. Jump Game II

You are given a 0-indexed array of integers nums of length n. You are initially positioned at nums[0].

Each element nums[i] represents the maximum length of a forward jump from index i. In other words, if you are at nums[i], you can jump to any nums[i + j] where:

0 <= j <= nums[i] and
i + j < n

Return the minimum number of jumps to reach nums[n - 1]. The test cases are generated such that you can reach nums[n - 1].

Example 1:

plaintext

Input: nums = [2,3,1,1,4]
Output: 2
Explanation: The minimum number of jumps to reach the last index is 2. Jump 1 step from index 0 to 1, then 3 steps to the last index.

Solution:

/**
 * @param {number[]} nums
 * @return {number}
 */
var jump = function (nums) {
    const len = nums.length - 1;
    let l = -1, r = 0, res = 0;
    for (let i = 0; r < len; i++) {
        if (l < i) l = r, res++;
        r = Math.max(r, i + nums[i]);
    }
    return res;
};

H1 49. Group Anagrams

Given an array of strings strs, group the anagrams together. You can return the answer in any order.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

Example 1:

plaintext

Input: strs = ["eat","tea","tan","ate","nat","bat"]
Output: [["bat"],["nat","tan"],["ate","eat","tea"]]

Solution:

/**
 * @param {string[]} strs
 * @return {string[][]}
 */
var groupAnagrams = function (strs) {
    const hash = new Map();
    for (const str of strs) {
        const str1 = [...str].sort().join("");
        if (hash.has(str1)) {
            hash.get(str1).push(str);
        } else {
            hash.set(str1, [str]);
        }
    }
    return [...hash.values()];
};

Note: In scenarios where key-value pairs are frequently added or deleted, Map may perform better than Object.

H1 53. Maximum Subarray

Given an integer array nums, find the subarray with the largest sum, and return its sum.

Example 1:

plaintext

Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: The subarray [4,-1,2,1] has the largest sum 6.

Solution:

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function(nums) {
    let max = nums[0];
    for (let i = 1; i < nums.length; i++) {
        nums[i] = nums[i] + Math.max(0, nums[i - 1]);
        if (nums[i] > max) max = nums[i];
    }
    return max;
};

Note: dp[i] = nums[i] + max(0, dp[i-1])

H1 55. Jump Game

You are given an integer array nums. You are initially positioned at the array's first index, and each element in the array represents your maximum jump length at that position.

Return true if you can reach the last index, or false otherwise.

Example 1:

plaintext

Input: nums = [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

Solution:

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var canJump = function (nums) {
    if (nums.length === 1) return true;
    for (var i = nums.length - 2, j = nums.length - 1; i >= 0; i--) {
        if (nums[i] >= j - i) j = i;
    }
    return j ? false : true;
};

H1 71. Simplify Path

Given a string path, which is an absolute path (starting with a slash '/') to a file or directory in a Unix-style file system, convert it to the simplified canonical path.

In a Unix-style file system, a period '.' refers to the current directory, a double period '..' refers to the directory up a level, and any multiple consecutive slashes (i.e. '//') are treated as a single slash '/'. For this problem, any other format of periods such as '...' are treated as file/directory names.

The canonical path should have the following format:

The path starts with a single slash '/'.
Any two directories are separated by a single slash '/'.
The path does not end with a trailing '/'.
The path only contains the directories on the path from the root directory to the target file or directory (i.e., no period '.' or double period '..')

Return the simplified canonical path.

Example 1:

plaintext

Input: path = "/home/"
Output: "/home"
Explanation: Note that there is no trailing slash after the last directory name.

Example 2:

plaintext

Input: path = "/../"
Output: "/"
Explanation: Going one level up from the root directory is a no-op, as the root level is the highest level you can go.

Solution:

/**
 * @param {string} path
 * @return {string}
 */
var simplifyPath = function (path) {
    const stack = [];
    for (const p of path.split("/")) {
        if (p === "..") {
            stack.pop();
        } else if (p && p !== ".") {
            stack.push(p);
        }
    }
    return "/" + stack.join("/");
};

H1 80. Remove Duplicates from Sorted Array II

Given an integer array nums sorted in non-decreasing order, remove some duplicates in-place such that each unique element appears at most twice. The relative order of the elements should be kept the same.

Since it is impossible to change the length of the array in some languages, you must instead have the result be placed in the first part of the array nums. More formally, if there are k elements after removing the duplicates, then the first k elements of nums should hold the final result. It does not matter what you leave beyond the first k elements.

Return k after placing the final result in the first k slots of nums.

Do not allocate extra space for another array. You must do this by modifying the input array in-place with O(1) extra memory.

Example 1:

plaintext

Input: nums = [1,1,1,2,2,3]
Output: 5, nums = [1,1,2,2,3,_]
Explanation: Your function should return k = 5, with the first five elements of nums being 1, 1, 2, 2 and 3 respectively.
It does not matter what you leave beyond the returned k (hence they are underscores).

Solution:

/**
 * @param {number[]} nums
 * @return {number}
 */
var removeDuplicates = function (nums) {
    if (nums.length <= 2) {
        return nums.length;
    }
    for (var i = j = 2; j < nums.length; j++) {
        if (nums[j] != nums[i - 2] || nums[j] != nums[i - 1]) {
            nums[i] = nums[j];
            i++;
        }
    }
    return i;
};

H1 88. Merge Sorted Array

You are given two integer arrays nums1 and nums2, sorted in non-decreasing order, and two integers m and n, representing the number of elements in nums1 and nums2 respectively.

Merge nums1 and nums2 into a single array sorted in non-decreasing order.

The final sorted array should not be returned by the function, but instead be stored inside the array nums1. To accommodate this, nums1 has a length of m + n, where the first m elements denote the elements that should be merged, and the last n elements are set to 0 and should be ignored. nums2 has a length of n.

Example 1:

plaintext

Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
Output: [1,2,2,3,5,6]
Explanation: The arrays we are merging are [1,2,3] and [2,5,6].
The result of the merge is [1,2,2,3,5,6] with the underlined elements coming from nums1.

Solution:

/**
 * @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) {
    m--;
    n--;
    while (n >= 0) {
        if (m >= 0 && (nums1[m] > nums2[n])) {
            nums1[m + n + 1] = nums1[m];
            m--;
        } else {
            nums1[m + n + 1] = nums2[n];
            n--;
        }
    }
};

H1 92. Reverse Linked List II

Given the head of a singly linked list and two integers left and right where left <= right, reverse the nodes of the list from position left to position right, and return the reversed list.

Example 1:

plaintext

Input: head = [1,2,3,4,5], left = 2, right = 4
Output: [1,4,3,2,5]

Solution:

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} left
 * @param {number} right
 * @return {ListNode}
 */
var reverseBetween = function (head, left, right) {
    if (!head?.next || left === right) return head;
    let i = 1, curr = next = head, prev = null;
    while (i < left) {
        [prev, curr] = [curr, curr.next];
        i++;
    }
    let prev1 = prev, curr1 = curr;
    while (i <= right) {
        next = curr.next;
        curr.next = prev;
        prev = curr;
        curr = next;
        i++;
    }
    if (left > 1) {
        prev1.next = prev;
    } else {
        head = prev;
    }
    curr1.next = curr;
    return head;
};

H1 100. Same Tree

Given the roots of two binary trees p and q, write a function to check if they are the same or not.

Two binary trees are considered the same if they are structurally identical, and the nodes have the same value.

Example 1:

plaintext

Input: p = [1,2,3], q = [1,2,3]
Output: true

Solution:

/**
 * 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} p
 * @param {TreeNode} q
 * @return {boolean}
 */
var isSameTree = function (p, q) {
    if (p === null && q === null) return true;
    if (!p || !q) return false;
    if (p.val === q.val) return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    return false;
};

H1 101. Symmetric Tree

Given the root of a binary tree, check whether it is a mirror of itself (i.e., symmetric around its center).

Example 1:

plaintext

Input: root = [1,2,2,3,4,4,3]
Output: true

Solution:

/**
 * 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 isSymmetric = function (root) {
    const q = [root.left, root.right];
    while (q.length) {
        const l = q.shift(), r = q.shift();
        if (!l && !r) continue;
        if (!l || !r || l.val !== r.val) return false;
        q.push(l.right, r.left, l.left, r.right);
    }
    return true;
};

H1 112. Path Sum

Given the root of a binary tree and an integer targetSum, return true if the tree has a root-to-leaf path such that adding up all the values along the path equals targetSum.

A leaf is a node with no children.

Example 1:

plaintext

Input: root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
Output: true
Explanation: The root-to-leaf path with the target sum is shown.

Solution:

/**
 * 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) return false;
    if (root.val === targetSum && !root.left && !root.right) return true;
    return hasPathSum(root.left, targetSum - root.val) || hasPathSum(root.right, targetSum - root.val);
};

H1 114. Flatten Binary Tree to Linked List

Given the root of a binary tree, flatten the tree into a "linked list":

The "linked list" should use the same TreeNode class where the right child pointer points to the next node in the list and the left child pointer is always null.
The "linked list" should be in the same order as a pre-order traversal of the binary tree.

Example 1:

plaintext

Input: root = [1,2,5,3,4,null,6]
Output: [1,null,2,null,3,null,4,null,5,null,6]

Solution:

/**
 * 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 {void} Do not return anything, modify root in-place instead.
 */
var flatten = function (root) {
    let crt = root;
    while (crt) {
        if (crt.left) {
            let runner = crt.left;
            while (runner.right) runner = runner.right;
            runner.right = crt.right;
            crt.right = crt.left;
            crt.left = null;
        }
        crt = crt.right;
    }
};

Note: Here we use Morris Traversal.

Reference

H1 108. Convert Sorted Array to Binary Search Tree

Given an integer array nums where the elements are sorted in ascending order, convert it to a height-balanced binary search tree.

Example 1:

plaintext

Input: nums = [-10,-3,0,5,9]
Output: [0,-3,9,-10,null,5]
Explanation: [0,-10,5,null,-3,null,9] is also accepted:

Solution:

/**
 * 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 {number[]} nums
 * @return {TreeNode}
 */
var sortedArrayToBST = function (nums) {
    const dfs = (beg, end) => {
        if (beg > end) return null;
        const mid = Math.floor((beg + end) / 2);
        const node = new TreeNode(nums[mid]);
        node.left = dfs(beg, mid - 1);
        node.right = dfs(mid + 1, end);
        return node;
    }
    return dfs(0, nums.length - 1);
};

H1 117. Populating Next Right Pointers in Each Node II

Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.

Initially, all next pointers are set to NULL.

Example 1:

plaintext

Input: root = [1,2,3,4,5,null,7]
Output: [1,#,2,3,#,4,5,7,#]

Solution:

/**
 * // Definition for a Node.
 * function Node(val, left, right, next) {
 *    this.val = val === undefined ? null : val;
 *    this.left = left === undefined ? null : left;
 *    this.right = right === undefined ? null : right;
 *    this.next = next === undefined ? null : next;
 * };
 */
 
/**
 * @param {Node} root
 * @return {Node}
 */
var connect = function (root) {
    if (!root) return null;
    const q = [[root, 0]];
    while (q.length) {
        const [curr, level] = q.shift();
        if (q.length) {
            const [next, nextLevel] = q[0];
            if (level === nextLevel) curr.next = next;
        }
        if (curr.left) q.push([curr.left, level + 1]);
        if (curr.right) q.push([curr.right, level + 1]);
    }
    return root;
};

H1 121. Best Time to Buy and Sell Stock

You are given an array prices where prices[i] is the price of a given stock on the ith day.

You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.

Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.

Example 1:

plaintext

Input: prices = [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.

Example 2:

plaintext

Input: prices = [7,6,4,3,1]
Output: 0
Explanation: In this case, no transactions are done and the max profit = 0.

Solution:

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function (prices) {
    let min = prices[0], profit = 0;
    for (let i = 0; i < prices.length; i++) {
        if (min > prices[i]) {
            min = prices[i];
        } else if (prices[i] - min > profit) {
            profit = prices[i] - min;
        }
    }
    return profit;
};

H1 128. Longest Consecutive Sequence

Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence.

You must write an algorithm that runs in O(n) time.

Example 1:

plaintext

Input: nums = [100,4,200,1,3,2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.

Solution:

/**
 * @param {number[]} nums
 * @return {number}
 */
var longestConsecutive = function (nums) {
    const set = new Set(nums);
    let max = 0;
    for (const n of [...set]) {
        if (!set.has(n - 1)) {
            let len = 1;
            while (set.has(n + len)) len++;
            max = Math.max(max, len)
        }
    }
    return max;
};

Note: Every number will be accessed at most twice, so the time complexity is O(n).

H1 130. Surrounded Regions

Given an m x n matrix board containing 'X' and 'O', capture all regions that are 4-directionally surrounded by 'X'.

A region is captured by flipping all 'O's into 'X's in that surrounded region.

Example 1:

plaintext

Input: board = [["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]]
Output: [["X","X","X","X"],["X","X","X","X"],["X","X","X","X"],["X","O","X","X"]]
Explanation: Notice that an 'O' should not be flipped if:
- It is on the border, or
- It is adjacent to an 'O' that should not be flipped.
The bottom 'O' is on the border, so it is not flipped.
The other three 'O' form a surrounded region, so they are flipped.

Solution:

/**
 * @param {character[][]} board
 * @return {void} Do not return anything, modify board in-place instead.
 */
var solve = function (board) {
    const m = board.length, n = board[0].length;
    const dfs = (i, j) => {
        if (0 > i || i >= m || 0 > j || j >= n) return;
        if (board[i][j] === "O") {
            board[i][j] = "S"
            dfs(i + 1, j);
            dfs(i - 1, j);
            dfs(i, j + 1);
            dfs(i, j - 1);
        }
    }
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n;) {
            if (board[i][j] === "O") dfs(i, j);
            if (!i || i === m - 1) {
                j++;
            } else {
                j += n - 1;
            }
        }
    }
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            board[i][j] = board[i][j] === "O" ? "X" : board[i][j] === "S" ? "O" : "X";
        }
    }
};

Note:

We have to traverse board's boader once to find "O".

If we find "O", run dfs on this "O" and rename all the adjacent "O" as "S" which stands for "Saving".

Traverse board again to rename all the "O" as "X" and "S" as "O".

H1 133. Clone Graph

Given a reference of a node in a connected undirected graph.

Return a deep copy (clone) of the graph.

Each node in the graph contains a value (int) and a list (List[Node]) of its neighbors.

plaintext

class Node {
    public int val;
    public List<Node> neighbors;
}

Test case format:

For simplicity, each node's value is the same as the node's index (1-indexed). For example, the first node with val == 1, the second node with val == 2, and so on. The graph is represented in the test case using an adjacency list.

An adjacency list is a collection of unordered lists used to represent a finite graph. Each list describes the set of neighbors of a node in the graph.

The given node will always be the first node with val = 1. You must return the copy of the given node as a reference to the cloned graph.

Example 1:

plaintext

Input: adjList = [[2,4],[1,3],[2,4],[1,3]]
Output: [[2,4],[1,3],[2,4],[1,3]]
Explanation: There are 4 nodes in the graph.
1st node (val = 1)'s neighbors are 2nd node (val = 2) and 4th node (val = 4).
2nd node (val = 2)'s neighbors are 1st node (val = 1) and 3rd node (val = 3).
3rd node (val = 3)'s neighbors are 2nd node (val = 2) and 4th node (val = 4).
4th node (val = 4)'s neighbors are 1st node (val = 1) and 3rd node (val = 3).

Solution:

/**
 * // Definition for a Node.
 * function Node(val, neighbors) {
 *    this.val = val === undefined ? 0 : val;
 *    this.neighbors = neighbors === undefined ? [] : neighbors;
 * };
 */
/**
 * @param {Node} node
 * @return {Node}
 */
var cloneGraph = function (graph) {
    if (!graph) return null;
    const map = new Map();
    const dfs = (node) => {
        if (!map.has(node.val)) {
            map.set(node.val, new Node(node.val));
            map.get(node.val).neighbors = node.neighbors.map(dfs); 	// Key Point
        }
        return map.get(node.val);
    }
    return dfs(graph);
};

H1 134. Gas Station

There are n gas stations along a circular route, where the amount of gas at the ith station is gas[i].

You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from the ith station to its next (i + 1)th station. You begin the journey with an empty tank at one of the gas stations.

Given two integer arrays gas and cost, return the starting gas station's index if you can travel around the circuit once in the clockwise direction, otherwise return -1. If there exists a solution, it is guaranteed to be unique

Example 1:

plaintext

Input: gas = [1,2,3,4,5], cost = [3,4,5,1,2]
Output: 3
Explanation:
Start at station 3 (index 3) and fill up with 4 unit of gas. Your tank = 0 + 4 = 4
Travel to station 4. Your tank = 4 - 1 + 5 = 8
Travel to station 0. Your tank = 8 - 2 + 1 = 7
Travel to station 1. Your tank = 7 - 3 + 2 = 6
Travel to station 2. Your tank = 6 - 4 + 3 = 5
Travel to station 3. The cost is 5. Your gas is just enough to travel back to station 3.
Therefore, return 3 as the starting index.

Solution:

/**
 * @param {number[]} gas
 * @param {number[]} cost
 * @return {number}
 */
var canCompleteCircuit = function (gas, cost) {
    let start = 0, tank = 0, totalTank = 0;
    for (let i = 0; i < gas.length; i++) {
        const netCost = gas[i] - cost[i];
        totalTank += netCost;
        tank += netCost;
        if (tank < 0) {
            tank = 0;
            start = i + 1;
        }
    }
    return totalTank < 0 ? -1 : start;
};

H1 135. Candy

There are n children standing in a line. Each child is assigned a rating value given in the integer array ratings.

You are giving candies to these children subjected to the following requirements:

Each child must have at least one candy.
Children with a higher rating get more candies than their neighbors.

Return the minimum number of candies you need to have to distribute the candies to the children.

Example 1:

plaintext

Input: ratings = [1,0,2]
Output: 5
Explanation: You can allocate to the first, second and third child with 2, 1, 2 candies respectively.

Solution:

/**
 * @param {number[]} ratings
 * @return {number}
 */
var candy = function (ratings) {
    const len = ratings.length, candy = Array(len).fill(1);
    for (let i = 1; i < len; i++) {
        if (ratings[i - 1] < ratings[i]) {
            candy[i] = candy[i - 1] + 1;
        }
    }
    for (let i = len - 2; i >= 0; i--) {
        if (ratings[i] > ratings[i + 1]) {
            candy[i] = Math.max(candy[i], candy[i + 1] + 1);
        }
    }
    return candy.reduce((a, c) => a + c);
};

Note:

Initialize Candies array filled with 1.

Conduct Forward pass & Backward pass to ensure the current candy number is less than or more neighbor candy numbers based on comparison.

Sum it all up.

H1 141. Linked List Cycle

Given head, the head of a linked list, determine if the linked list has a cycle in it.

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail's next pointer is connected to. Note that pos is not passed as a parameter.

Return true if there is a cycle in the linked list. Otherwise, return false.

Example 1:

plaintext

Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the 1st node (0-indexed).

Solution:

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
 
/**
 * @param {ListNode} head
 * @return {boolean}
 */
var hasCycle = function(head) {
    let s = head, i = 0;
    while (head) {
        head = head.next;
        if (s === head) return true;
        if (i++ % 2 === 1) s = s.next;
    }
    return false;;
};

H1 169. Majority Element

Given an array nums of size n, return the majority element.

The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array.

Example 1:

plaintext

Input: nums = [3,2,3]
Output: 3

Solution:

/**
 * @param {number[]} nums
 * @return {number}
 */
var majorityElement = function (nums) {
    let candidate, vote = 0;
    for (const n of nums) {
        if (candidate === n) {
            vote++;
        } else {
            if (vote === 0) {
                candidate = n;
            } else {
                vote--;
            }
        }
    }
    return candidate;
};

Note: Use Boyer-Moore Voting Algorithm.

H1 199. Binary Tree Right Side View

Given the root of a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.

Example 1:

plaintext

Input: root = [1,2,3,null,5,null,4]
Output: [1,3,4]

Solution:

/**
 * 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 rightSideView = function (root) {
    const res = [], v = new Set();
    const dfs = (node, i) => {
        if (!node) return;
        if (!v.has(i)) {
            v.add(i);
            res.push(node.val);
        }
        dfs(node.right, i + 1);
        dfs(node.left, i + 1);
    }
    dfs(root, 0);
    return res;
};

H1 200. Number of Islands

Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return the number of islands.

An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Example 1:

plaintext

Input: grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
Output: 1

Solution:

/**
 * @param {character[][]} grid
 * @return {number}
 */
var numIslands = function (grid) {
    // const m = grid.length, n = grid[0].length;
    // const v = Array.from({ length: m }, () => new Array(n).fill(0));
    // const moves = [[0, 1], [0, -1], [1, 0], [-1, 0]];
    // let count = 0;
    // for (let i = 0; i < m; i++) {
    //     for (let j = 0; j < n; j++) {
    //         if (!v[i][j] && +grid[i][j]) {
    //             v[i][j] = 1;
    //             const q = [[i, j]];
    //             while (q.length) {
    //                 const [x, y] = q.shift();
    //                 for (const [mx, my] of moves) {
    //                     const newX = x + mx, newY = y + my;
    //                     if (0 <= newX && newX < m && 0 <= newY && newY < n && !v[newX][newY] && +grid[newX][newY]) {
    //                         v[newX][newY] = 1;
    //                         q.push([newX, newY]);
    //                     }
    //                 }
    //             }
    //             count++;
    //         }
    //     }
    // }
    // return count;
    const m = grid.length, n = grid[0].length;
    let count = 0;
    const dfs = (x, y) => {
        if (0 > x || x >= m || 0 > y || y >= n || !+grid[x][y]) return;
        grid[x][y] = "0"; // Key Point
        dfs(x - 1, y);
        dfs(x + 1, y);
        dfs(x, y - 1);
        dfs(x, y + 1);
    }
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (+grid[i][j]) dfs(i, j), count++;
        }
    }
    return count;
};

H1 206. Reverse Linked List

Given the head of a singly linked list, reverse the list, and return the reversed list.

Example 1:

plaintext

Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]

Solution:

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function(head) {
    let result = null;
    while (head) {
        const nextNode = head.next;
        head.next = result;
        result = head;
        head = nextNode;
    }
    return result;
};

H1 207. Course Schedule

There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course bi first if you want to take course ai.

For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1.

Return true if you can finish all courses. Otherwise, return false.

Example 1:

plaintext

Input: numCourses = 2, prerequisites = [[1,0]]
Output: true
Explanation: There are a total of 2 courses to take. 
To take course 1 you should have finished course 0. So it is possible.

Solution:

/**
 * @param {number} numCourses
 * @param {number[][]} prerequisites
 * @return {boolean}
 */
var canFinish = function (numCourses, prerequisites) {
    const v = new Set(), adj = Array.from({ length: numCourses }, () => []);
    for (const [x, y] of prerequisites) adj[x].push(y);
    // Can this course be finished?
    const dfs = (node) => {
        if (v.has(node)) return false;
        if (!adj[node].length) return true;
        v.add(node);
        for (const n of adj[node]) if (!dfs(n)) return false;
        // If nothing happens, that means this is acyclic. The couse can be taken.
        v.delete(node);
        adj[node] = [];
        return true;
    }
    for (let i = 0; i < numCourses; i++) {
        if (!dfs(i)) return false;
    }
    return true;
};

Note:

Solution Video

H1 228. Summary Ranges

You are given a sorted unique integer array nums.

A range [a,b] is the set of all integers from a to b (inclusive).

Return the smallest sorted list of ranges that cover all the numbers in the array exactly. That is, each element of nums is covered by exactly one of the ranges, and there is no integer x such that x is in one of the ranges but not in nums.

Each range [a,b] in the list should be output as:

"a->b" if a != b
"a" if a == b

Example 1:

plaintext

Input: nums = [0,1,2,4,5,7]
Output: ["0->2","4->5","7"]
Explanation: The ranges are:
[0,2] --> "0->2"
[4,5] --> "4->5"
[7,7] --> "7"

Solution:

/**
 * @param {number[]} nums
 * @return {string[]}
 */
var summaryRanges = function (nums) {
    const res = [];
    for (let i = 0, left = nums[0]; i < nums.length; i++) {
        if (nums[i] + 1 !== nums[i + 1]) {
            res.push(left === nums[i] ? String(nums[i]) : left + "->" + nums[i]);
            left = nums[i + 1];
        }
    }
    return res;
};

H1 238. Product of Array Except Self

Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].

The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

You must write an algorithm that runs in O(n) time and without using the division operation.

Example 1:

plaintext

Input: nums = [1,2,3,4]
Output: [24,12,8,6]

Solution:

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var productExceptSelf = function(nums) {
    const len = nums.length, arr = [1];
    for (let i = 1; i < len; i++) {
        arr[i] = arr[i - 1] * nums[i - 1];
    }
    let suf = nums[len - 1];
    for (let i = len - 2; i > -1; i--) {
        arr[i] *= suf;
        suf *= nums[i];
    }
    return arr;
};

H1 283. Move Zeroes

Given an integer array nums, move all 0's to the end of it while maintaining the relative order of the non-zero elements.

Note that you must do this in-place without making a copy of the array.

Example 1:

plaintext

Input: nums = [0,1,0,3,12]
Output: [1,3,12,0,0]

Solution:

/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var moveZeroes = function (nums) {
    for (let i = j = 0; i < nums.length; i++) {
        if (nums[i] !== 0) {
            [nums[i], nums[j]] = [nums[j], nums[i]];
            j++;
        }
    }
};

H1 290. Word Pattern

Given a pattern and a string s, find if s follows the same pattern.

Here follow means a full match, such that there is a bijection between a letter in pattern and a non-empty word in s.

Example 1:

plaintext

Input: pattern = "abba", s = "dog cat cat dog"
Output: true

Example 2:

plaintext

Input: pattern = "abba", s = "dog cat cat fish"
Output: false

Solution:

/**
 * @param {string} pattern
 * @param {string} s
 * @return {boolean}
 */
var wordPattern = function (pattern, s) {
    // const str = s.split(" "), map = new Map(), set = new Set();
    // if (pattern.length !== str.length) return false;
    // for (let i = 0; i < str.length; i++) {
    //     if ((map.has(pattern[i]) && str[i] !== map.get(pattern[i])) || (!map.has(pattern[i]) && set.has(str[i]))) {
    //         return false;
    //     } else {
    //         map.set(pattern[i], str[i]);
    //         set.add(str[i]);
    //     }
    // }
    // return true;
    const str = s.split(" ");
    if (pattern.length !== str.length) return false;
    for (let i = 0; i < str.length; i++) {
        if (str.indexOf(str[i]) !== pattern.indexOf(pattern[i])) return false;
    }
    return true;
};

H1 399. Evaluate Division

You are given an array of variable pairs equations and an array of real numbers values, where equations[i] = [Ai, Bi] and values[i] represent the equation Ai / Bi = values[i]. Each Ai or Bi is a string that represents a single variable.

You are also given some queries, where queries[j] = [Cj, Dj] represents the jth query where you must find the answer for Cj / Dj = ?.

Return the answers to all queries. If a single answer cannot be determined, return -1.0.

Note: The input is always valid. You may assume that evaluating the queries will not result in division by zero and that there is no contradiction.

Note: The variables that do not occur in the list of equations are undefined, so the answer cannot be determined for them.

Example 1:

plaintext

Input: equations = [["a","b"],["b","c"]], values = [2.0,3.0], queries = [["a","c"],["b","a"],["a","e"],["a","a"],["x","x"]]
Output: [6.00000,0.50000,-1.00000,1.00000,-1.00000]
Explanation: 
Given: a / b = 2.0, b / c = 3.0
queries are: a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ? 
return: [6.0, 0.5, -1.0, 1.0, -1.0 ]
note: x is undefined => -1.0

Solution:

/**
 * @param {string[][]} equations
 * @param {number[]} values
 * @param {string[][]} queries
 * @return {number[]}
 */
var calcEquation = function (equations, values, queries) {
    const adj = new Map();
    equations.forEach(([s, e], i) => {
        if (!adj.has(s)) adj.set(s, new Map());
        adj.get(s).set(e, values[i]);
        if (!adj.has(e)) adj.set(e, new Map());
        adj.get(e).set(s, 1 / values[i]);
    });
    const dfs = (s, e, vis = new Set()) => {
        if (!adj.has(s) || !adj.has(e)) return -1;
        vis.add(s);
        if (s === e) return 1;
        for (const [u, v] of [...adj.get(s)]) {
            if (!vis.has(u)) {
                const div = dfs(u, e, vis);
                if (div !== -1) return div * v;
            }
        }
        return -1;
    }
    return queries.map(([s, e]) => dfs(s, e));
};

H1 530. Minimum Absolute Difference in BST

Given the root of a Binary Search Tree (BST), return the minimum absolute difference between the values of any two different nodes in the tree.

Example 1:

plaintext

Input: root = [4,2,6,1,3]
Output: 1

Solution:

/**
 * 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 getMinimumDifference = function (root) {
    const arr = [];
    let min = 1e5;
    const dfs = (node) => {
        if (!node) return;
        dfs(node.left);
        arr.push(node.val);
        dfs(node.right);
    }
    dfs(root);
    for (let i = 1; i < arr.length; i++) {
        min = Math.min(min, arr[i] - arr[i - 1]);
    }
    return min;
};

H1 559. Maximum Depth of N-ary Tree

Given a n-ary tree, find its maximum depth.

The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

Nary-Tree input serialization is represented in their level order traversal, each group of children is separated by the null value (See examples).

Example 1:

plaintext

Input: root = [1,null,3,2,4,null,5,6]
Output: 3

Solution:

/**
 * @param {Node|null} root
 * @return {number}
 */
var maxDepth = function(root) {
    if(!root) return 0
    let depth = 0
    for (let child of root.children) {
        depth = Math.max(depth, maxDepth(child))
    }
    return depth+1
};

H1 590. N-ary Tree Postorder Traversal

Given the root of an n-ary tree, return the postorder traversal of its nodes' values.

Nary-Tree input serialization is represented in their level order traversal. Each group of children is separated by the null value (See examples)

Example 1:

plaintext

Input: root = [1,null,3,2,4,null,5,6]
Output: [5,6,3,2,4,1]

Solution:

/**
 * // Definition for a Node.
 * function Node(val,children) {
 *    this.val = val;
 *    this.children = children;
 * };
 */
/**
 * @param {Node|null} root
 * @return {number[]}
 */
var postorder = function(root) {
    let res = [];
    const dfs = (node) => {
        if (!node) return;
        for (const n of node.children) dfs(n);
        res.push(node.val);
    }
    dfs(root);
    return res;
};

H1 617. Merge Two Binary Trees

You are given two binary trees root1 and root2.

Imagine that when you put one of them to cover the other, some nodes of the two trees are overlapped while the others are not. You need to merge the two trees into a new binary tree. The merge rule is that if two nodes overlap, then sum node values up as the new value of the merged node. Otherwise, the NOT null node will be used as the node of the new tree.

Return the merged tree.

Note: The merging process must start from the root nodes of both trees.

Example 1:

plaintext

Input: root1 = [1,3,2,5], root2 = [2,1,3,null,4,null,7]
Output: [3,4,5,5,4,null,7]

Solution:

var mergeTrees = function (root1, root2) {
    if (!root1) return root2;
    if (!root2) return root1;
    root1.val += root2.val;
    root1.left = mergeTrees(root1.left, root2.left);
    root1.right = mergeTrees(root1.right, root2.right);
    return root1;
};

H1 637. Average of Levels in Binary Tree

Given the root of a binary tree, return the average value of the nodes on each level in the form of an array. Answers within 10-5 of the actual answer will be accepted.

Example 1:

plaintext

Input: root = [3,9,20,null,null,15,7]
Output: [3.00000,14.50000,11.00000]
Explanation: The average value of nodes on level 0 is 3, on level 1 is 14.5, and on level 2 is 11.
Hence return [3, 14.5, 11].

Solution:

/**
 * 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 averageOfLevels = function (root) {
    const res = [], queue = [root];
    while (queue.length) {
        let sum = 0;
        const len = queue.length;
        for (let i = 0; i < len; i++) {
            const node = queue.shift();
            sum += node.val;
            if (node.left) queue.push(node.left);
            if (node.right) queue.push(node.right);
        }
        res.push(sum / len);
    }
    return res;
};

H1 746. Min Cost Climbing Stairs

You are given an integer array cost where cost[i] is the cost of ith step on a staircase. Once you pay the cost, you can either climb one or two steps.

You can either start from the step with index 0, or the step with index 1.

Return the minimum cost to reach the top of the floor.

Example 1:

plaintext

Input: cost = [10,15,20]
Output: 15
Explanation: You will start at index 1.
- Pay 15 and climb two steps to reach the top.
The total cost is 15.

Solution:

/**
 * @param {number[]} cost
 * @return {number}
 */
var minCostClimbingStairs = function (cost) {
    let len = cost.length - 1;
    const dp = [];
    while (len >= 0) {
        dp[len] = cost[len] + Math.min(dp[len + 1] || 0, dp[len + 2] || 0);
        len--;
    }
    return Math.min(dp[0], dp[1]);
};

Hint:

Build an array dp where dp[i] is the minimum cost to climb to the top starting from the ith staircase.

Assuming we have n staircase labeled from 0 to n - 1 and assuming the top is n, then dp[n] = 0, marking that if you are at the top, the cost is 0.

Now, looping from n - 1 to 0, the dp[i] = cost[i] + min(dp[i + 1], dp[i + 2]). The answer will be the minimum of dp[0] and dp[1]

H1 807. Max Increase to Keep City Skyline

There is a city composed of n x n blocks, where each block contains a single building shaped like a vertical square prism. You are given a 0-indexed n x n integer matrix grid where grid[r][c] represents the height of the building located in the block at row r and column c.

A city's skyline is the outer contour formed by all the building when viewing the side of the city from a distance. The skyline from each cardinal direction north, east, south, and west may be different.

We are allowed to increase the height of any number of buildings by any amount (the amount can be different per building). The height of a 0-height building can also be increased. However, increasing the height of a building should not affect the city's skyline from any cardinal direction.

Return the maximum total sum that the height of the buildings can be increased by without changing the city's skyline from any cardinal direction.

Example 1:

plaintext

Input: grid = [[3,0,8,4],[2,4,5,7],[9,2,6,3],[0,3,1,0]]
Output: 35
Explanation: The building heights are shown in the center of the above image.
The skylines when viewed from each cardinal direction are drawn in red.
The grid after increasing the height of buildings without affecting skylines is:
gridNew = [ [8, 4, 8, 7],
            [7, 4, 7, 7],
            [9, 4, 8, 7],
            [3, 3, 3, 3] ]

Solution:

/**
 * @param {number[][]} grid
 * @return {number}
 */
var maxIncreaseKeepingSkyline = function (grid) {
    let res = 0, len = grid.length, max_col = [], max_row = [];
    for (let i = 0; i < len; i++) {
        max_row.push(Math.max(...grid[i]));
        for (let j = 0; j < len; j++) {
            max_col[j] = max_col[j] > -1 ? Math.max(max_col[j], grid[i][j]) : grid[i][j];
        }
    }
    for (let i = 0; i < len; i++) {
        for (let j = 0; j < len; j++) {
            const min = Math.min(max_row[i], max_col[j]);
            if (grid[i][j] < min) res += min - grid[i][j];
        }
    }
    return res;
};

H1 841. Keys and Rooms

There are n rooms labeled from 0 to n - 1 and all the rooms are locked except for room 0. Your goal is to visit all the rooms. However, you cannot enter a locked room without having its key.

When you visit a room, you may find a set of distinct keys in it. Each key has a number on it, denoting which room it unlocks, and you can take all of them with you to unlock the other rooms.

Given an array rooms where rooms[i] is the set of keys that you can obtain if you visited room i, return true if you can visit all the rooms, or false otherwise.

Example 1:

plaintext

Input: rooms = [[1],[2],[3],[]]
Output: true
Explanation: 
We visit room 0 and pick up key 1.
We then visit room 1 and pick up key 2.
We then visit room 2 and pick up key 3.
We then visit room 3.
Since we were able to visit every room, we return true.

Solution:

/**
 * @param {number[][]} rooms
 * @return {boolean}
 */
var canVisitAllRooms = function (rooms) {
    const v = new Set([0]), q = [0];
    while (q.length) {
        const crt = q.shift();
        for (const k of rooms[crt]) {
            if (!v.has(k)) {
                q.push(k);
                v.add(k);
            }
        }
    }
    return v.size === rooms.length;
};

H1 872. Leaf-Similar Trees

Consider all the leaves of a binary tree, from left to right order, the values of those leaves form a leaf value sequence*.*

For example, in the given tree above, the leaf value sequence is (6, 7, 4, 9, 8).

Two binary trees are considered leaf-similar if their leaf value sequence is the same.

Return true if and only if the two given trees with head nodes root1 and root2 are leaf-similar.

Example 1:

plaintext

Input: root1 = [3,5,1,6,2,9,8,null,null,7,4], root2 = [3,5,1,6,7,4,2,null,null,null,null,null,null,9,8]
Output: true

Solution:

/**
 * 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} root1
 * @param {TreeNode} root2
 * @return {boolean}
 */
var leafSimilar = function (root1, root2) {
    const dfs = (node) => {
        if (!node) return [];
        const leaves = [...dfs(node.left), ...dfs(node.right)];
        return leaves.length > 0 ? leaves : [node.val];
    }
    return JSON.stringify(dfs(root1)) === JSON.stringify(dfs(root2));
}

H1 897. Increasing Order Search Tree

Given the root of a binary search tree, rearrange the tree in in-order so that the leftmost node in the tree is now the root of the tree, and every node has no left child and only one right child.

Example 1:

plaintext

Input: root = [5,3,6,2,4,null,8,1,null,null,null,7,9]
Output: [1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9]

Solution:

/**
 * 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 {TreeNode}
 */
var increasingBST = function(root) {
    let newRoot = newTree = null;
    const dfs = (node) => {
        if (!node) return;
        dfs(node.left);
        if (!newRoot) {
            newRoot = newTree = node;
        } else {
            newTree.right = node;
            newTree = newTree.right;
            newTree.left = null;
        }
        dfs(node.right);
    }
    dfs(root);
    return newRoot;
};

H1 933. Number of Recent Calls

You have a RecentCounter class which counts the number of recent requests within a certain time frame.

Implement the RecentCounter class:

RecentCounter() Initializes the counter with zero recent requests.
int ping(int t) Adds a new request at time t, where t represents some time in milliseconds, and returns the number of requests that has happened in the past 3000 milliseconds (including the new request). Specifically, return the number of requests that have happened in the inclusive range [t - 3000, t].

It is guaranteed that every call to ping uses a strictly larger value of t than the previous call.

Example 1:

plaintext

Input
["RecentCounter", "ping", "ping", "ping", "ping"]
[[], [1], [100], [3001], [3002]]
Output
[null, 1, 2, 3, 3]

Explanation
RecentCounter recentCounter = new RecentCounter();
recentCounter.ping(1);     // requests = [1], range is [-2999,1], return 1
recentCounter.ping(100);   // requests = [1, 100], range is [-2900,100], return 2
recentCounter.ping(3001);  // requests = [1, 100, 3001], range is [1,3001], return 3
recentCounter.ping(3002);  // requests = [1, 100, 3001, 3002], range is [2,3002], return 3

Solution:

var RecentCounter = function () {
    this.queue = [];
};
 
/** 
 * @param {number} t
 * @return {number}
 */
RecentCounter.prototype.ping = function (t) {
    while (this.queue.length !== 0 && this.queue[0] < t - 3000) {
        this.queue.shift();
    }
    this.queue.push(t);
    return this.queue.length;
};
 
/** 
 * Your RecentCounter object will be instantiated and called as such:
 * var obj = new RecentCounter()
 * var param_1 = obj.ping(t)
 */

Note:

I suddenly found we can write more than one condition in while loop.

H1 938. Range Sum of BST

Given the root node of a binary search tree and two integers low and high, return the sum of values of all nodes with a value in the inclusive range [low, high].

Example 1:

plaintext

Input: root = [10,5,15,3,7,null,18], low = 7, high = 15
Output: 32
Explanation: Nodes 7, 10, and 15 are in the range [7, 15]. 7 + 10 + 15 = 32.

Solution:

/**
 * 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} low
 * @param {number} high
 * @return {number}
 */
var rangeSumBST = function (root, low, high) {
    let sum = 0;
    const dfs = (node) => {
        if (!node) return;
        if (low <= node.val && node.val <= high) sum += node.val;
        if (node.val < low || node.val < high) dfs(node.right);
        if (node.val > high || node.val > low) dfs(node.left);
    }
    dfs(root);
    return sum;
};

H1 997. Find the Town Judge

In a town, there are n people labeled from 1 to n. There is a rumor that one of these people is secretly the town judge.

If the town judge exists, then:

The town judge trusts nobody.
Everybody (except for the town judge) trusts the town judge.
There is exactly one person that satisfies properties 1 and 2.

You are given an array trust where trust[i] = [ai, bi] representing that the person labeled ai trusts the person labeled bi. If a trust relationship does not exist in trust array, then such a trust relationship does not exist.

Return the label of the town judge if the town judge exists and can be identified, or return -1 otherwise.

Example 1:

plaintext

Input: n = 3, trust = [[1,3],[2,3]]
Output: 3

Example 2:

plaintext

Input: n = 3, trust = [[1,3],[2,3],[3,1]]
Output: -1

Solution:

/**
 * @param {number} n
 * @param {number[][]} trust
 * @return {number}
 */
var findJudge = function (n, trust) {
    const adj = Array.from({ length: n + 1 }, () => []);
    for (const t of trust) adj[t[0]].push(t[1]);
    const judge = adj.findLastIndex(item => !item.length);
    if (judge > 0) {
        const isTrustedByEveryone = adj.every((item, i) => {
            if (i === judge || i === 0) return true;
            return item.includes(judge);
        });
        if (isTrustedByEveryone) return judge;
    }
    return -1;
};

H1 1021. Remove Outermost Parentheses

A valid parentheses string is either empty "", "(" + A + ")", or A + B, where A and B are valid parentheses strings, and + represents string concatenation.

For example, "", "()", "(())()", and "(()(()))" are all valid parentheses strings.

A valid parentheses string s is primitive if it is nonempty, and there does not exist a way to split it into s = A + B, with A and B nonempty valid parentheses strings.

Given a valid parentheses string s, consider its primitive decomposition: s = P1 + P2 + ... + Pk, where Pi are primitive valid parentheses strings.

Return s after removing the outermost parentheses of every primitive string in the primitive decomposition of s.

Example 1:

plaintext

Input: s = "(()())(())"
Output: "()()()"
Explanation: 
The input string is "(()())(())", with primitive decomposition "(()())" + "(())".
After removing outer parentheses of each part, this is "()()" + "()" = "()()()".

Solution:

/**
 * @param {string} s
 * @return {string}
 */
var removeOuterParentheses = function (s) {
    let stack = 0;
    let result = "";
    for (const str of s) {
        if (str === "(") {
            if (stack) result += str;
            stack++;
        } else {
            stack--;
            if (stack) result += str;
        }
    }
 
    return result;
};

Note:

Use const to declare str.

stack is not necessarily to be [], because we don't need to use value of this array. So we might as well use Number to check if each part comes to an end.

H1 1207. Unique Number of Occurrences

Given an array of integers arr, return true if the number of occurrences of each value in the array is unique or false otherwise.

Example 1:

plaintext

Input: arr = [1,2,2,1,1,3]
Output: true
Explanation: The value 1 has 3 occurrences, 2 has 2 and 3 has 1. No two values have the same number of occurrences.

Example 2:

plaintext

Input: arr = [1,2]
Output: false

Solution:

/**
 * @param {number[]} arr
 * @return {boolean}
 */
var uniqueOccurrences = function (arr) {
    const hash = {};
    arr.forEach((a) => {
        hash[a] = (hash[a] || 0) + 1;
    })
    const vals = Object.values(hash);
    const set = new Set(vals)
    return vals.length === set.size;
};

H1 1221. Split a String in Balanced Strings

Balanced strings are those that have an equal quantity of 'L' and 'R' characters.

Given a balanced string s, split it into some number of substrings such that:

Each substring is balanced.

Return the maximum number of balanced strings you can obtain.

Example 1:

plaintext

Input: s = "RLRRLLRLRL"
Output: 4
Explanation: s can be split into "RL", "RRLL", "RL", "RL", each substring contains same number of 'L' and 'R'.

Solution:

/**
 * @param {string} s
 * @return {number}
 */
var balancedStringSplit = function (s) {
    let count = stack = 0;
    for (const str of s) {
        stack += str === "L" ? 1 : -1;
        if (!stack) count++;
    }
    return count;
};

H1 1282. Group the People Given the Group Size They Belong To

There are n people that are split into some unknown number of groups. Each person is labeled with a unique ID from 0 to n - 1.

You are given an integer array groupSizes, where groupSizes[i] is the size of the group that person i is in. For example, if groupSizes[1] = 3, then person 1 must be in a group of size 3.

Return a list of groups such that each person i is in a group of size groupSizes[i].

Each person should appear in exactly one group, and every person must be in a group. If there are multiple answers, return any of them. It is guaranteed that there will be at least one valid solution for the given input.

Example 1:

plaintext

Input: groupSizes = [3,3,3,3,3,1,3]
Output: [[5],[0,1,2],[3,4,6]]
Explanation: 
The first group is [5]. The size is 1, and groupSizes[5] = 1.
The second group is [0,1,2]. The size is 3, and groupSizes[0] = groupSizes[1] = groupSizes[2] = 3.
The third group is [3,4,6]. The size is 3, and groupSizes[3] = groupSizes[4] = groupSizes[6] = 3.
Other possible solutions are [[2,1,6],[5],[0,4,3]] and [[5],[0,6,2],[4,3,1]].

Example 2:

plaintext

Input: groupSizes = [2,1,3,3,3,2]
Output: [[1],[0,5],[2,3,4]]

Solution:

/**
 * @param {number[]} groupSizes
 * @return {number[][]}
 */
var groupThePeople = function (groupSizes) {
    const hash = {}, result = [];
    groupSizes.forEach((s, i) => {
        hash[s] ||= [];
        hash[s].push(i);
        if (hash[s].length === s) {
            result.push(hash[s]);
            hash[s] = [];
        }
    })
    return result;
};

Note: It took me 40 minutes to figure it out. if statement here is the point.

H1 1379. Find a Corresponding Node of a Binary Tree in a Clone of That Tree

Given two binary trees original and cloned and given a reference to a node target in the original tree.

The cloned tree is a copy of the original tree.

Return a reference to the same node in the cloned tree.

Note that you are not allowed to change any of the two trees or the target node and the answer must be a reference to a node in the cloned tree.

Example 1:

plaintext

Input: tree = [7,4,3,null,null,6,19], target = 3
Output: 3
Explanation: In all examples the original and cloned trees are shown. The target node is a green node from the original tree. The answer is the yellow node from the cloned tree.

Solution:

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} original
 * @param {TreeNode} cloned
 * @param {TreeNode} target
 * @return {TreeNode}
 */
 
var getTargetCopy = function (original, cloned, target) {
    const dfs = (o, c) => {
        if (!o) return;
        if (o === target) return c;
        return dfs(o.left, c.left) || dfs(o.right, c.right);
    }
    return dfs(original, cloned);
};

H1 1402. Reducing Dishes

A chef has collected data on the satisfaction level of his n dishes. Chef can cook any dish in 1 unit of time.

Like-time coefficient of a dish is defined as the time taken to cook that dish including previous dishes multiplied by its satisfaction level i.e. time[i] * satisfaction[i].

Return the maximum sum of like-time coefficient that the chef can obtain after preparing some amount of dishes.

Dishes can be prepared in any order and the chef can discard some dishes to get this maximum value.

Example 1:

plaintext

Input: satisfaction = [-1,-8,0,5,-9]
Output: 14
Explanation: After Removing the second and last dish, the maximum total like-time coefficient will be equal to (-1*1 + 0*2 + 5*3 = 14).
Each dish is prepared in one unit of time.

Solution:

/**
 * @param {number[]} satisfaction
 * @return {number}
 */
var maxSatisfaction = function (satisfaction) {
    satisfaction.sort((a, b) => b - a);
    let sum = max = 0;
    for (const s of satisfaction) {
        sum += s;
        if (sum < 0) break;
        max += sum;
    }
    return max;
};

Note: If sum < 0, that means we don't need the rest of them anymore. Look, [-4, 5] and [5]，which sum of like-time coefficient is bigger? Definitely the former one, so we should ensure sum is more than 0 to keep the maximum sum.

H1 1512. Number of Good Pairs

Given an array of integers nums, return the number of good pairs.

A pair (i, j) is called good if nums[i] == nums[j] and i < j.

Example 1:

plaintext

Input: nums = [1,2,3,1,1,3]
Output: 4
Explanation: There are 4 good pairs (0,3), (0,4), (3,4), (2,5) 0-indexed.

Example 2:

plaintext

Input: nums = [1,1,1,1]
Output: 6
Explanation: Each pair in the array are good.

Solution:

/**
 * @param {number[]} nums
 * @return {number}
 */
var numIdenticalPairs = function (nums) {
    const obj = {};
    for (const n of nums) {
        obj[n] = (obj[n] || 0) + 1;
    }
    return Object.entries(obj).reduce((acc, [_, val]) => {
        if (val > 1) acc += (val - 1) * val / 2;
        return acc;
    }, 0)
};

H1 1539. Kth Missing Positive Number

Given an array arr of positive integers sorted in a strictly increasing order, and an integer k.

Return the kth positive integer that is missing from this array.

Example 1:

plaintext

Input: arr = [2,3,4,7,11], k = 5
Output: 9
Explanation: The missing positive integers are [1,5,6,8,9,10,12,13,...]. The 5th missing positive integer is 9.

Example 2:

plaintext

Input: arr = [1,2,3,4], k = 2
Output: 6
Explanation: The missing positive integers are [5,6,7,...]. The 2nd missing positive integer is 6.

Solution:

/**
 * @param {number[]} arr
 * @param {number} k
 * @return {number}
 */
var findKthPositive = function(arr, k) {
    let i = 1;
    let j = 0;
    while(1) {
        if (!arr.includes(i)) {
            j++;
            if (j == k) {
                return i;
            }
        }
        i++;
    }
};

H1 1615. Maximal Network Rank

There is an infrastructure of n cities with some number of roads connecting these cities. Each roads[i] = [ai, bi] indicates that there is a bidirectional road between cities ai and bi.

The network rank of two different cities is defined as the total number of directly connected roads to either city. If a road is directly connected to both cities, it is only counted once.

The maximal network rank of the infrastructure is the maximum network rank of all pairs of different cities.

Given the integer n and the array roads, return the maximal network rank of the entire infrastructure.

Example 1:

img

plaintext

Input: n = 4, roads = [[0,1],[0,3],[1,2],[1,3]]
Output: 4
Explanation: The network rank of cities 0 and 1 is 4 as there are 4 roads that are connected to either 0 or 1. The road between 0 and 1 is only counted once.

Solution:

/**
 * @param {number} n
 * @param {number[][]} roads
 * @return {number}
 */
var maximalNetworkRank = function (n, roads) {
    let max = 0;
    const adj = Array.from({length: n}, () => []);
    for (let [a, b] of roads) {
        adj[a].push(b);
        adj[b].push(a);
    }
    for (let i = 0; i < n; i++) {
        for (let j = i + 1; j < n; j++) {
            let rank = adj[i].length + adj[j].length;
            if (adj[i].includes(j)) rank--;
            max = Math.max(max, rank);
        }
    }
    return max;
};

H1 1640. Check Array Formation Through Concatenation

You are given an array of distinct integers arr and an array of integer arrays pieces, where the integers in pieces are distinct. Your goal is to form arr by concatenating the arrays in pieces in any order. However, you are not allowed to reorder the integers in each array pieces[i].

Return true if it is possible to form the array arr from pieces. Otherwise, return false.

Example 1:

plaintext

Input: arr = [15,88], pieces = [[88],[15]]
Output: true
Explanation: Concatenate [15] then [88]

Example 2:

plaintext

Input: arr = [49,18,16], pieces = [[16,18,49]]
Output: false
Explanation: Even though the numbers match, we cannot reorder pieces[0].

Example 3:

plaintext

Input: arr = [91,4,64,78], pieces = [[78],[4,64],[91]]
Output: true
Explanation: Concatenate [91] then [4,64] then [78]

Solution:

/**
 * @param {number[]} arr
 * @param {number[][]} pieces
 * @return {boolean}
 */
var canFormArray = function (arr, pieces) {
    const hash = {}, result = [];
    pieces.forEach(piece => {
        hash[piece[0]] = piece;
    })
    for (const a of arr) {
        if (hash[a]) result.push(hash[a].flat());
    }
 
    return String(arr) === String(result);
};

H1 1689. Partitioning Into Minimum Number Of Deci-Binary Numbers

A decimal number is called deci-binary if each of its digits is either 0 or 1 without any leading zeros. For example, 101 and 1100 are deci-binary, while 112 and 3001 are not.

Given a string n that represents a positive decimal integer, return the minimum number of positive deci-binary numbers needed so that they sum up to n.

Example 1:

plaintext

Input: n = "32"
Output: 3
Explanation: 10 + 11 + 11 = 32

Example 2:

plaintext

Input: n = "82734"
Output: 8

Example 3:

plaintext

Input: n = "27346209830709182346"
Output: 9

Solution:

/**
 * @param {string} n
 * @return {number}
 */
var minPartitions = function (n) {
    // return Math.max(...n);
    for (let i = 9; i > 0; i--) {
        if (n.indexOf(i) !== -1) return i;
    }
};

Note: The greediness lies in finding the biggest digit in n at first.

H1 1848. Minimum Distance to the Target Element

Given an integer array nums (0-indexed) and two integers target and start, find an index i such that nums[i] == target and abs(i - start) is minimized. Note that abs(x) is the absolute value of x.

Return abs(i - start).

It is guaranteed that target exists in nums.

Example 1:

plaintext

Input: nums = [1,2,3,4,5], target = 5, start = 3
Output: 1
Explanation: nums[4] = 5 is the only value equal to target, so the answer is abs(4 - 3) = 1.

Example 2:

plaintext

Input: nums = [1], target = 1, start = 0
Output: 0
Explanation: nums[0] = 1 is the only value equal to target, so the answer is abs(0 - 0) = 0.

Solution:

/**
 * @param {number[]} nums
 * @param {number} target
 * @param {number} start
 * @return {number}
 */
var getMinDistance = function(nums, target, start) {
    let min = 10000;
    for (let i = 0; i < start; i++) {
        if (nums[i] === target) {
            min = start - i;
        }
    }
 
    for (let i = start; i < start + min; i++) {
        if (nums[i] === target) {
            return i - start;
        }
    }
 
    return min;
};

H1 1971. Find if Path Exists in Graph

There is a bi-directional graph with n vertices, where each vertex is labeled from 0 to n - 1 (inclusive). The edges in the graph are represented as a 2D integer array edges, where each edges[i] = [ui, vi] denotes a bi-directional edge between vertex ui and vertex vi. Every vertex pair is connected by at most one edge, and no vertex has an edge to itself.

You want to determine if there is a valid path that exists from vertex source to vertex destination.

Given edges and the integers n, source, and destination, return true if there is a valid path from source to destination, or false otherwise*.*

Example 1:

plaintext

Input: n = 6, edges = [[0,1],[0,2],[3,5],[5,4],[4,3]], source = 0, destination = 5
Output: false
Explanation: There is no path from vertex 0 to vertex 5.

Solution:

/**
 * @param {number} n
 * @param {number[][]} edges
 * @param {number} source
 * @param {number} destination
 * @return {boolean}
 */
var validPath = function(n, edges, source, destination) {
    if (n === 1) return true;
    const v = new Array(n).fill(0);
    v[source] = 1;
    let flag = true;
    while (flag) {
        flag = false;
        for (const e of edges) {
            if (v[e[0]] !== v[e[1]]) v[e[0]] = v[e[1]] = 1, flag = true;
            if (v[destination]) return true;
        }
    }
    return false;
};

H1 2006. Count Number of Pairs With Absolute Difference K

Given an integer array nums and an integer k, return the number of pairs (i, j) where i < j such that |nums[i] - nums[j]| == k.

The value of |x| is defined as:

x if x >= 0.
-x if x < 0.

Example 1:

plaintext

Input: nums = [1,2,2,1], k = 1
Output: 4

Example 2:

plaintext

Input: nums = [1,3], k = 3
Output: 0
Explanation: There are no pairs with an absolute difference of 3.

Solution:

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var countKDifference = function (nums, k) {
    let count = 0;
    // for (let i = 0; i < nums.length; i++) {
    //     for (let j = i + 1; j < nums.length; j++) {
    //         if (Math.abs(nums[i] - nums[j]) === k) count++;
    //     }
    // }
    const hash = {};
    for (const n of nums) {
        hash[n] = (hash[n] || 0) + 1;
    }
    for (const n of nums) {
        count += hash[n + k] || 0;
    }
    return count;
};

H1 2224. Minimum Number of Operations to Convert Time

You are given two strings current and correct representing two 24-hour times.

24-hour times are formatted as "HH:MM", where HH is between 00 and 23, and MM is between 00 and 59. The earliest 24-hour time is 00:00, and the latest is 23:59.

In one operation you can increase the time current by 1, 5, 15, or 60 minutes. You can perform this operation any number of times.

Return the minimum number of operations needed to convert current to correct.

Example 1:

plaintext

Input: current = "02:30", correct = "04:35"
Output: 3
Explanation:
We can convert current to correct in 3 operations as follows:
- Add 60 minutes to current. current becomes "03:30".
- Add 60 minutes to current. current becomes "04:30".
- Add 5 minutes to current. current becomes "04:35".
It can be proven that it is not possible to convert current to correct in fewer than 3 operations.

Solution:

/**
 * @param {string} current
 * @param {string} correct
 * @return {number}
 */
var convertTime = function (current, correct) {
    let diff = (Number(correct.slice(0, 2)) - Number(current.slice(0, 2))) * 60
        + Number(correct.slice(-2)) - Number(current.slice(-2));
    let min = 0;
    min += Math.floor(diff / 60);
    diff %= 60;
    min += Math.floor(diff / 15);
    diff %= 15;
    min += Math.floor(diff / 5);
    diff %= 5;
    min += diff;
    return min;
};

Note: You don't need to use while, just calculate it.

H1 2265. Count Nodes Equal to Average of Subtree

Given the root of a binary tree, return the number of nodes where the value of the node is equal to the average of the values in its subtree.

Note:

The average of n elements is the sum of the n elements divided by n and rounded down to the nearest integer.
A subtree of root is a tree consisting of root and all of its descendants.

Example 1:

plaintext

Input: root = [4,8,5,0,1,null,6]
Output: 5
Explanation: 
For the node with value 4: The average of its subtree is (4 + 8 + 5 + 0 + 1 + 6) / 6 = 24 / 6 = 4.
For the node with value 5: The average of its subtree is (5 + 6) / 2 = 11 / 2 = 5.
For the node with value 0: The average of its subtree is 0 / 1 = 0.
For the node with value 1: The average of its subtree is 1 / 1 = 1.
For the node with value 6: The average of its subtree is 6 / 1 = 6.

Solution:

/**
 * 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 averageOfSubtree = function (root) {
    let count = 0;
    const dfs = (node) => {
        if (!node) return [0, 0];
        const [leftSize, leftSum] = dfs(node.left);
        const [rightSize, rightSum] = dfs(node.right);
        const sum = node.val + leftSum + rightSum;
        const size = 1 + leftSize + rightSize;
        if (Math.floor(sum / size) === node.val) count++;
        return [size, sum];
    }
    dfs(root);
    return count;
};

H1 2325. Decode the Message

You are given the strings key and message, which represent a cipher key and a secret message, respectively. The steps to decode message are as follows:

Use the first appearance of all 26 lowercase English letters in key as the order of the substitution table.
Align the substitution table with the regular English alphabet.
Each letter in message is then substituted using the table.
Spaces ' ' are transformed to themselves.

For example, given key = "**hap**p**y** **bo**y" (actual key would have at least one instance of each letter in the alphabet), we have the partial substitution table of ('h' -> 'a', 'a' -> 'b', 'p' -> 'c', 'y' -> 'd', 'b' -> 'e', 'o' -> 'f').

Return the decoded message.

Example 1:

plaintext

Input: key = "the quick brown fox jumps over the lazy dog", message = "vkbs bs t suepuv"
Output: "this is a secret"
Explanation: The diagram above shows the substitution table.
It is obtained by taking the first appearance of each letter in "the quick brown fox jumps over the lazy dog".

Example 2:

plaintext

Input: key = "eljuxhpwnyrdgtqkviszcfmabo", message = "zwx hnfx lqantp mnoeius ycgk vcnjrdb"
Output: "the five boxing wizards jump quickly"
Explanation: The diagram above shows the substitution table.
It is obtained by taking the first appearance of each letter in "eljuxhpwnyrdgtqkviszcfmabo".

Solution:

/**
 * @param {string} key
 * @param {string} message
 * @return {string}
 */
var decodeMessage = function (key, message) {
    const hash = {};
    let result = "";
    for (let i = j = 0; i < key.length; i++) {
        if (key[i] !== " " && !hash[key[i]]) {
            hash[key[i]] = String.fromCharCode("a".charCodeAt(0) + j);
            if (j === 25) break;
            j++;
        }
    }
    for (const m of message) {
        result += hash[m] || " ";
    }
    return result;
};

H1 2409. Count Days Spent Together

Alice and Bob are traveling to Rome for separate business meetings.

You are given 4 strings arriveAlice, leaveAlice, arriveBob, and leaveBob. Alice will be in the city from the dates arriveAlice to leaveAlice (inclusive), while Bob will be in the city from the dates arriveBob to leaveBob (inclusive). Each will be a 5-character string in the format "MM-DD", corresponding to the month and day of the date.

Return the total number of days that Alice and Bob are in Rome together.

You can assume that all dates occur in the same calendar year, which is not a leap year. Note that the number of days per month can be represented as: [31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31].

Example 1:

plaintext

Input: arriveAlice = "08-15", leaveAlice = "08-18", arriveBob = "08-16", leaveBob = "08-19"
Output: 3
Explanation: Alice will be in Rome from August 15 to August 18. Bob will be in Rome from August 16 to August 19. They are both in Rome together on August 16th, 17th, and 18th, so the answer is 3.

Solution:

/**
 * @param {string} arriveAlice
 * @param {string} leaveAlice
 * @param {string} arriveBob
 * @param {string} leaveBob
 * @return {number}
 */
var countDaysTogether = function (arriveAlice, leaveAlice, arriveBob, leaveBob) {
    if (arriveAlice > leaveBob || arriveBob > leaveAlice) return 0;
 
    const dates = [arriveAlice, leaveAlice, arriveBob, leaveBob].sort();
    const start = dates[1].split("-"), end = dates[2].split("-");
    let sm = +start[0] - 1, em = +end[0] - 1, days = 0;
    const sd = +start[1], ed = +end[1];
    const months = [31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31];
 
    while (sm < em) {
        days += months[sm];
        sm++;
    }
 
    return days - sd + ed + 1;
};

H1 2824. Count Pairs Whose Sum is Less than Target

Given a 0-indexed integer array nums of length n and an integer target, return the number of pairs (i, j) where 0 <= i < j < n and nums[i] + nums[j] < target.

Example 1:

plaintext

Input: nums = [-1,1,2,3,1], target = 2
Output: 3
Explanation: There are 3 pairs of indices that satisfy the conditions in the statement:
- (0, 1) since 0 < 1 and nums[0] + nums[1] = 0 < target
- (0, 2) since 0 < 2 and nums[0] + nums[2] = 1 < target 
- (0, 4) since 0 < 4 and nums[0] + nums[4] = 0 < target
Note that (0, 3) is not counted since nums[0] + nums[3] is not strictly less than the target.

Solution:

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var countPairs = function(nums, target) {
    nums.sort((a, b) => a - b);
    let l = 0, r = nums.length - 1, count = 0;
    while (l < r) {
        if (nums[l] + nums[r] < target) {
            count += r - l;
            l++;
        } else {
            r--;
        }
    }
    return count;
};

H1 2864. Maximum Odd Binary Number

You are given a binary string s that contains at least one '1'.

You have to rearrange the bits in such a way that the resulting binary number is the maximum odd binary number that can be created from this combination.

Return a string representing the maximum odd binary number that can be created from the given combination.

Note that the resulting string can have leading zeros.

Example 1:

plaintext

Input: s = "010"
Output: "001"
Explanation: Because there is just one '1', it must be in the last position. So the answer is "001".

Solution:

/**
 * @param {string} s
 * @return {string}
 */
var maximumOddBinaryNumber = function (s) {
    const arr = s.split("1");
    const len = arr.length;
    return "1".repeat(len - 2) + arr.join("") + "1";
};

Note: The strategy is that we should put one 1 at the end and the rest of them should come first.

詩頌の博客 - 時不我待，只爭朝夕

H11. Two Sum

Next

Related Posts