LeetCode 75 Study Plan

9 July 2022 · 14 min read

CS Student

This study plan is for those who want to prepare for technical interviews but are uncertain which problems they should focus on. The problems have been carefully curated so that levels 1 and 2 will guide beginner and intermediate users through problems that cover the data structures and algorithms necessary to succeed in interviews with most mid-tier companies. While level 3 provides material to help users whose targets are top-tier companies. -- LeetCode

Day 1 Prefix Sum

1480. Running Sum of 1d Array

src: https://leetcode.com/problems/running-sum-of-1d-array

// Input: nums = [1,2,3,4]
// Output: [1,3,6,10]
// Explanation: Running sum is obtained as follows: [1, 1+2, 1+2+3, 1+2+3+4].

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var runningSum = function (nums) {
    const sum = Array(nums.length).fill(0);

    sum[0] = nums[0];
    for (let i = 1; i < nums.length; i++) {
        sum[i] = sum[i - 1] + nums[i];
    }
    return sum;
};

console.log(runningSum([1, 2, 3, 4])); // [1,3,6,10]


console.log(runningSum([1, 7, 3, 6, 5, 6]));
console.log(runningSum([1, 7, 3, 6, 5, 6].reverse()));

1// Input: nums = [1,2,3,4]
2// Output: [1,3,6,10]
3// Explanation: Running sum is obtained as follows: [1, 1+2, 1+2+3, 1+2+3+4].
4
5/**
6 * @param {number[]} nums
7 * @return {number[]}
8 */
9var runningSum = function (nums) {
10    const sum = Array(nums.length).fill(0);
11
12    sum[0] = nums[0];
13    for (let i = 1; i < nums.length; i++) {
14        sum[i] = sum[i - 1] + nums[i];
15    }
16    return sum;
17};
18
19console.log(runningSum([1, 2, 3, 4])); // [1,3,6,10]
20
21
22console.log(runningSum([1, 7, 3, 6, 5, 6]));
23console.log(runningSum([1, 7, 3, 6, 5, 6].reverse()));

724. Find Pivot Index

src: https://leetcode.com/problems/find-pivot-index

note

At a given index i, how do I get the value of leftSum and rightSum?

Ans:

leftSum of i-th element can be computed by summing up all the values on the left of the i-th element.
rightSum of i-th element is equal to the sum of the array minus the value of the current element and leftSum.

// e.g 1
// Input: nums = [1,7,3,6,5,6]
// Output: 3
// Explanation:
// The pivot index is 3.
// Left sum = nums[0] + nums[1] + nums[2] = 1 + 7 + 3 = 11
// Right sum = nums[4] + nums[5] = 5 + 6 = 11

// e.g. 2
// Input: nums = [1,2,3]
// Output: -1
// Explanation:
// There is no index that satisfies the conditions in the problem statement.

// e.g. 3
// Input: nums = [2,1,-1]
// Output: 0
// Explanation:
// The pivot index is 0.
// Left sum = 0 (no elements to the left of index 0)
// Right sum = nums[1] + nums[2] = 1 + -1 = 0

var pivotIndex = function (nums) {
    let leftSum = 0;
    let rightSum = sum(nums);
    for (let i = 0; i < nums.length; i++) {
        rightSum = rightSum - nums[i];
        if (leftSum === rightSum) return i;
        leftSum += nums[i];
    }

    return -1;
};


var runningSum = function (nums) {
    const sum = Array(nums.length).fill(0);

    sum[0] = nums[0];
    for (let i = 1; i < nums.length; i++) {
        sum[i] = sum[i - 1] + nums[i];
    }
    return sum;
};


//  0   1   2   3    4  5
// [1,  7,  3,  6,   5, 6]
// [1,  8,  11, 17, 22, 28] look at the element on the left of the i-th element
// [28, 27, 20, 17, 11, 6]  look at the element on the right of the i-th element
/**
 * @param {number[]} nums
 * @return {number}
 */
var pivotIndex1 = function (nums) {
    let leftRunningSum = runningSum(nums);
    let rightRunningSum = runningSum([...nums].reverse()).reverse();

    let leftSum = 0;
    let rightSum = 0;
    for (let i = 0; i < nums.length; i++) {
        leftSum = leftRunningSum[i - 1]
        rightSum = rightRunningSum[i + 1]
        if (leftSum === undefined) leftSum = 0;
        if (rightSum === undefined) rightSum = 0;


        if (leftSum === rightSum) return i;
    }

    return -1;
};

var sum = nums => nums.reduce((accumulator, currentValue) => accumulator + currentValue, 0)
/**
 * @param {number[]} nums
 * @return {number}
 */


console.log(pivotIndex([1, 7, 3, 6, 5, 6])); // 3
console.log(pivotIndex([1, 2, 3])); // -1
console.log(pivotIndex([2, 1, -1])); // 0

1// e.g 1
2// Input: nums = [1,7,3,6,5,6]
3// Output: 3
4// Explanation:
5// The pivot index is 3.
6// Left sum = nums[0] + nums[1] + nums[2] = 1 + 7 + 3 = 11
7// Right sum = nums[4] + nums[5] = 5 + 6 = 11
8
9// e.g. 2
10// Input: nums = [1,2,3]
11// Output: -1
12// Explanation:
13// There is no index that satisfies the conditions in the problem statement.
14
15// e.g. 3
16// Input: nums = [2,1,-1]
17// Output: 0
18// Explanation:
19// The pivot index is 0.
20// Left sum = 0 (no elements to the left of index 0)
21// Right sum = nums[1] + nums[2] = 1 + -1 = 0
22
23var pivotIndex = function (nums) {
24    let leftSum = 0;
25    let rightSum = sum(nums);
26    for (let i = 0; i < nums.length; i++) {
27        rightSum = rightSum - nums[i];
28        if (leftSum === rightSum) return i;
29        leftSum += nums[i];
30    }
31
32    return -1;
33};
34
35
36var runningSum = function (nums) {
37    const sum = Array(nums.length).fill(0);
38
39    sum[0] = nums[0];
40    for (let i = 1; i < nums.length; i++) {
41        sum[i] = sum[i - 1] + nums[i];
42    }
43    return sum;
44};
45
46
47//  0   1   2   3    4  5
48// [1,  7,  3,  6,   5, 6]
49// [1,  8,  11, 17, 22, 28] look at the element on the left of the i-th element
50// [28, 27, 20, 17, 11, 6]  look at the element on the right of the i-th element
51/**
52 * @param {number[]} nums
53 * @return {number}
54 */
55var pivotIndex1 = function (nums) {
56    let leftRunningSum = runningSum(nums);
57    let rightRunningSum = runningSum([...nums].reverse()).reverse();
58
59    let leftSum = 0;
60    let rightSum = 0;
61    for (let i = 0; i < nums.length; i++) {
62        leftSum = leftRunningSum[i - 1]
63        rightSum = rightRunningSum[i + 1]
64        if (leftSum === undefined) leftSum = 0;
65        if (rightSum === undefined) rightSum = 0;
66
67
68        if (leftSum === rightSum) return i;
69    }
70
71    return -1;
72};
73
74var sum = nums => nums.reduce((accumulator, currentValue) => accumulator + currentValue, 0)
75/**
76 * @param {number[]} nums
77 * @return {number}
78 */
79
80
81console.log(pivotIndex([1, 7, 3, 6, 5, 6])); // 3
82console.log(pivotIndex([1, 2, 3])); // -1
83console.log(pivotIndex([2, 1, -1])); // 0

Day 2 String

205. Isomorphic Strings

src: https://leetcode.com/problems/isomorphic-strings

note

Given two strings s and t, determine if they are isomorphic.

Two strings s and t are isomorphic if the characters in s can be replaced to get t.

All occurrences of a character must be replaced with another character while preserving the order of characters. No two characters may map to the same character, but a character may map to itself.

Should pay more attention on the last paragraph of the requirement. A character can only be mapped to one character. Therefore, create a set to store the values. i.e. one-to-one relationship.

input	map	result
egg -> add	`{e : a, g : d}`	`true`
badc -> baba	b -> b a -> a d -> b c -> a	`false`

For "badc -> baba", it has two characters that map to b (b and d) so it is not isomorphic.

/**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
var isIsomorphic = function (s, t) {
    if (s.length !== t.length) return false;
    const map = {};
    const values = new Set();

    for (let i = 0; i < s.length; i++) {
        const leftChar = s[i];
        const rightChar = t[i];

        if (map[leftChar] === undefined) {
            if (values.has(rightChar)) return false
            map[leftChar] = rightChar;
            values.add(rightChar)

            continue;
        }

        const mappedChar = map[leftChar];
        if (mappedChar !== rightChar) {
            return false
        }
    }
    return true
};

console.log(isIsomorphic("egg", "add")); // true
console.log(isIsomorphic("foo", "bar")); // false
console.log(isIsomorphic("paper", "title")); // true
console.log(isIsomorphic("badc", "baba")); // false  b->b   a->a   d->b  c->a

// No two characters may map to the same character, but a character may map to itself.

1/**
2 * @param {string} s
3 * @param {string} t
4 * @return {boolean}
5 */
6var isIsomorphic = function (s, t) {
7    if (s.length !== t.length) return false;
8    const map = {};
9    const values = new Set();
10
11    for (let i = 0; i < s.length; i++) {
12        const leftChar = s[i];
13        const rightChar = t[i];
14
15        if (map[leftChar] === undefined) {
16            if (values.has(rightChar)) return false
17            map[leftChar] = rightChar;
18            values.add(rightChar)
19
20            continue;
21        }
22
23        const mappedChar = map[leftChar];
24        if (mappedChar !== rightChar) {
25            return false
26        }
27    }
28    return true
29};
30
31console.log(isIsomorphic("egg", "add")); // true
32console.log(isIsomorphic("foo", "bar")); // false
33console.log(isIsomorphic("paper", "title")); // true
34console.log(isIsomorphic("badc", "baba")); // false  b->b   a->a   d->b  c->a
35
36// No two characters may map to the same character, but a character may map to itself.

392. Is Subsequence

src: https://leetcode.com/problems/is-subsequence

note

Given two strings s and t, return true if s is a subsequence of t, or false otherwise.

A subsequence of a string is a new string that is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (i.e., "ace" is a subsequence of "abcde" while "aec" is not).

A simple example isSubsequence("bc", "abagdc")

First, check if b in the string if it does exist then check the remaining characters to see if c exist.

/**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
var isSubsequence = function (s, t) {
    let startIdx = 0;
    let count = 0;
    for (let i = 0; i < s.length; i++) {
        const char = s[i];
        for (let j = startIdx; j < t.length; j++) {
            if (char === t[j]) {
                count++;
                startIdx = j + 1;
                break;
            }
        }
    }

    return s.length === count;
};


console.log(isSubsequence("abc", "ahbgdc")); // true
console.log(isSubsequence("axc", "ahbgdc")); // false

console.log(isSubsequence("bc", "abagdc")); // true
console.log(isSubsequence("aa", "abagdc")); // true

1/**
2 * @param {string} s
3 * @param {string} t
4 * @return {boolean}
5 */
6var isSubsequence = function (s, t) {
7    let startIdx = 0;
8    let count = 0;
9    for (let i = 0; i < s.length; i++) {
10        const char = s[i];
11        for (let j = startIdx; j < t.length; j++) {
12            if (char === t[j]) {
13                count++;
14                startIdx = j + 1;
15                break;
16            }
17        }
18    }
19
20    return s.length === count;
21};
22
23
24console.log(isSubsequence("abc", "ahbgdc")); // true
25console.log(isSubsequence("axc", "ahbgdc")); // false
26
27console.log(isSubsequence("bc", "abagdc")); // true
28console.log(isSubsequence("aa", "abagdc")); // true

Day 3 Linked List

21. Merge Two Sorted Lists

src: https://leetcode.com/problems/merge-two-sorted-lists

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) {
    const dummy = new ListNode();

    let current = dummy;
    let left = list1;
    let right = list2;
    while (left && right) {
        if (left.val <= right.val) {
            current.next = new ListNode(left.val)
            left = left.next
        } else {
            current.next = new ListNode(right.val);
            right = right.next
        }

        current = current.next;
    }

    // deal with the remaining numbers
    if (left || right) {
        current.next = left ? left : right
    }

    return dummy.next;
};

/**
 * 
 * @param {ListNode} root 
 */
function print(root) {
    let current = root;
    while (current) {
        console.log(current.val);
        current = current.next;
    }
}
/**
 * 
 * @param {number[]} nums 
 */
function toListNode(nums) {
    const dummy = new ListNode();
    let current = dummy;
    nums.forEach(num => {
        current.next = new ListNode(num);
        current = current.next
    })
    return dummy.next
}

print(mergeTwoLists(toListNode([1, 2, 4]), toListNode([1, 3, 4])))

1function ListNode(val, next) {
2    this.val = (val === undefined ? 0 : val)
3    this.next = (next === undefined ? null : next)
4}
5
6/**
7 * @param {ListNode} list1
8 * @param {ListNode} list2
9 * @return {ListNode}
10 */
11var mergeTwoLists = function (list1, list2) {
12    const dummy = new ListNode();
13
14    let current = dummy;
15    let left = list1;
16    let right = list2;
17    while (left && right) {
18        if (left.val <= right.val) {
19            current.next = new ListNode(left.val)
20            left = left.next
21        } else {
22            current.next = new ListNode(right.val);
23            right = right.next
24        }
25
26        current = current.next;
27    }
28
29    // deal with the remaining numbers
30    if (left || right) {
31        current.next = left ? left : right
32    }
33
34    return dummy.next;
35};
36
37/**
38 * 
39 * @param {ListNode} root 
40 */
41function print(root) {
42    let current = root;
43    while (current) {
44        console.log(current.val);
45        current = current.next;
46    }
47}
48/**
49 * 
50 * @param {number[]} nums 
51 */
52function toListNode(nums) {
53    const dummy = new ListNode();
54    let current = dummy;
55    nums.forEach(num => {
56        current.next = new ListNode(num);
57        current = current.next
58    })
59    return dummy.next
60}
61
62print(mergeTwoLists(toListNode([1, 2, 4]), toListNode([1, 3, 4])))

206. Reverse Linked List

src: https://leetcode.com/problems/reverse-linked-list

reverse linked list

tip

Change each node's next pointer to its left node.

null <- 1 <- 2 <- 3

function ListNode(val, next) {
    this.val = (val === undefined ? 0 : val)
    this.next = (next === undefined ? null : next)
}

var reverseList = function (head) {
    let prevHead = null;
    let nextHead = null;
    while (head) {
        nextHead = head.next;
        head.next = prevHead;

        prevHead = head;
        head = nextHead;
    }
    return prevHead;
};

/**
 * @param {ListNode} head
 * @return {ListNode} the reversed list
 */
var reverseList1 = function (head) {
    // no element []
    if (!head) return head;

    // only one element [1]
    if (!head.next) return head;

    // the first node's prev node is null
    let prevNode = null;
    let movingNode = head.next;
    // connect the first node's next to null
    head.next = prevNode;
    prevNode = head;

    while (movingNode) {
        let temp = movingNode.next;
        // connect to the moving node to the left node
        movingNode.next = prevNode;
        prevNode = movingNode;
        movingNode = temp;
    }

    return prevNode
};

/**
 * @param {ListNode} root 
 */
function print(root) {
    let current = root;
    const nums = [];
    while (current) {
        nums.push(current.val);
        current = current.next;
    }
    console.log(nums);
}
/**
 * @param {number[]} nums 
 */
function toListNode(nums) {
    const dummy = new ListNode();
    let current = dummy;
    nums.forEach(num => {
        current.next = new ListNode(num);
        current = current.next
    })
    return dummy.next
}

print(reverseList(toListNode([1, 2]))); // [2,1]
print(reverseList(toListNode([1, 2, 3, 4, 5]))); // [5,4,3,2,1]

1function ListNode(val, next) {
2    this.val = (val === undefined ? 0 : val)
3    this.next = (next === undefined ? null : next)
4}
5
6var reverseList = function (head) {
7    let prevHead = null;
8    let nextHead = null;
9    while (head) {
10        nextHead = head.next;
11        head.next = prevHead;
12
13        prevHead = head;
14        head = nextHead;
15    }
16    return prevHead;
17};
18
19/**
20 * @param {ListNode} head
21 * @return {ListNode} the reversed list
22 */
23var reverseList1 = function (head) {
24    // no element []
25    if (!head) return head;
26
27    // only one element [1]
28    if (!head.next) return head;
29
30    // the first node's prev node is null
31    let prevNode = null;
32    let movingNode = head.next;
33    // connect the first node's next to null
34    head.next = prevNode;
35    prevNode = head;
36
37    while (movingNode) {
38        let temp = movingNode.next;
39        // connect to the moving node to the left node
40        movingNode.next = prevNode;
41        prevNode = movingNode;
42        movingNode = temp;
43    }
44
45    return prevNode
46};
47
48/**
49 * @param {ListNode} root 
50 */
51function print(root) {
52    let current = root;
53    const nums = [];
54    while (current) {
55        nums.push(current.val);
56        current = current.next;
57    }
58    console.log(nums);
59}
60/**
61 * @param {number[]} nums 
62 */
63function toListNode(nums) {
64    const dummy = new ListNode();
65    let current = dummy;
66    nums.forEach(num => {
67        current.next = new ListNode(num);
68        current = current.next
69    })
70    return dummy.next
71}
72
73print(reverseList(toListNode([1, 2]))); // [2,1]
74print(reverseList(toListNode([1, 2, 3, 4, 5]))); // [5,4,3,2,1]
75

Day 4 Linked List

876. Middle of the Linked List

src: https://leetcode.com/problems/middle-of-the-linked-list

note

Given the head of a singly linked list, return the middle node of the linked list.

If there are two middle nodes, return the second middle node.

Example 1

example 1

Input: head = [1,2,3,4,5]
Output: [3,4,5]
Explanation: The middle node of the list is node 3.

Example 2

example 2

Input: head = [1,2,3,4,5,6]
Output: [4,5,6]
Explanation: Since the list has two middle nodes with values 3 and 4, we return the second one.

tip

Fast and Slow Pointer

When traversing the list with a pointer slow, make another pointer fast that traverses twice as fast.

slow = slow.next
fast = fast.next.next

When fast reaches the end of the list, slow must be in the middle.

function ListNode(val, next) {
    this.val = (val === undefined ? 0 : val)
    this.next = (next === undefined ? null : next)
}

var middleNode1 = function (head) {
    let length = 0;
    const dummy = new ListNode();
    dummy.next = head;

    while (head) {
        length++;
        head = head.next;
    }

    let middle = dummy.next;
    for (let i = 0; i < Math.floor(length / 2); i++) {
        middle = middle.next;
    }

    return middle;
};


/**
 * Fast and Slow Pointer
 * @param {ListNode} head
 * @return {ListNode}
 */
var middleNode = function (head) {
    let slow = head;
    let fast = head;

    while (fast && fast.next) {
        slow = slow.next;
        fast = fast.next.next;
    }

    return slow;
};

function print(root) {
    let current = root;
    const nums = [];
    while (current) {
        nums.push(current.val);
        current = current.next;
    }
    console.log(nums);
}

function toListNode(nums) {
    const dummy = new ListNode();
    let current = dummy;
    nums.forEach(num => {
        current.next = new ListNode(num);
        current = current.next
    })
    return dummy.next
}

print(middleNode(toListNode([1, 2, 3, 4, 5]))); // [3,4,5]
print(middleNode(toListNode([1, 2, 3, 4, 5, 6]))); // [4,5,6]

1function ListNode(val, next) {
2    this.val = (val === undefined ? 0 : val)
3    this.next = (next === undefined ? null : next)
4}
5
6var middleNode1 = function (head) {
7    let length = 0;
8    const dummy = new ListNode();
9    dummy.next = head;
10
11    while (head) {
12        length++;
13        head = head.next;
14    }
15
16    let middle = dummy.next;
17    for (let i = 0; i < Math.floor(length / 2); i++) {
18        middle = middle.next;
19    }
20
21    return middle;
22};
23
24
25/**
26 * Fast and Slow Pointer
27 * @param {ListNode} head
28 * @return {ListNode}
29 */
30var middleNode = function (head) {
31    let slow = head;
32    let fast = head;
33
34    while (fast && fast.next) {
35        slow = slow.next;
36        fast = fast.next.next;
37    }
38
39    return slow;
40};
41
42function print(root) {
43    let current = root;
44    const nums = [];
45    while (current) {
46        nums.push(current.val);
47        current = current.next;
48    }
49    console.log(nums);
50}
51
52function toListNode(nums) {
53    const dummy = new ListNode();
54    let current = dummy;
55    nums.forEach(num => {
56        current.next = new ListNode(num);
57        current = current.next
58    })
59    return dummy.next
60}
61
62print(middleNode(toListNode([1, 2, 3, 4, 5]))); // [3,4,5]
63print(middleNode(toListNode([1, 2, 3, 4, 5, 6]))); // [4,5,6]
64

142. Linked List Cycle II

src: https://leetcode.com/problems/linked-list-cycle-ii

note

Given the head of a linked list, return the node where the cycle begins. If there is no cycle, return null.

function ListNode(val, next) {
    this.val = (val === undefined ? 0 : val)
    this.next = (next === undefined ? null : next)
}

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var detectCycle = function (head) {
    // There is a cycle in a linked list if there is some node in the list that can be reached again
    const s = new Set();
    while (head) {
        if (s.has(head)) return head;
        s.add(head);
        head = head.next;
    }

    return null;
};

1function ListNode(val, next) {
2    this.val = (val === undefined ? 0 : val)
3    this.next = (next === undefined ? null : next)
4}
5
6/**
7 * @param {ListNode} head
8 * @return {ListNode}
9 */
10var detectCycle = function (head) {
11    // There is a cycle in a linked list if there is some node in the list that can be reached again
12    const s = new Set();
13    while (head) {
14        if (s.has(head)) return head;
15        s.add(head);
16        head = head.next;
17    }
18
19    return null;
20};

Day 5 Greedy

121. Best Time to Buy and Sell Stock

src: https://leetcode.com/problems/best-time-to-buy-and-sell-stock

Two import information to keep track of:

min price
max profit

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit1 = function (prices) {
    if (prices.length === 1) return 0;

    let max = 0;
    let maxSellPrice = 0;
    let maxSellPriceIdx = -1;
    for (let i = 0; i < prices.length; i++) {
        const buyPrice = prices[i];
        // find max sell price after current day
        if (i >= maxSellPriceIdx) {
            const remainingPrices = prices.slice(i);
            maxSellPrice = Math.max(...remainingPrices);
            maxSellPriceIdx = remainingPrices.lastIndexOf(maxSellPrice);
        }
        max = Math.max(maxSellPrice - buyPrice, max);

    }
    return max;
};

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function (prices) {
    let maxProfit = 0;
    let minPrice = Number.MAX_VALUE;

    prices.forEach(price => {
        minPrice = Math.min(minPrice, price);
        let profit = price - minPrice;
        maxProfit = Math.max(maxProfit, profit)
    })

    return maxProfit
}

console.log(maxProfit([7, 1, 5, 3, 6, 4])); // 5
console.log(maxProfit([7, 6, 4, 3, 1])); // 0
console.log(maxProfit([1])); // 0
console.log(maxProfit([1, 2])); // 1

1/**
2 * @param {number[]} prices
3 * @return {number}
4 */
5var maxProfit1 = function (prices) {
6    if (prices.length === 1) return 0;
7
8    let max = 0;
9    let maxSellPrice = 0;
10    let maxSellPriceIdx = -1;
11    for (let i = 0; i < prices.length; i++) {
12        const buyPrice = prices[i];
13        // find max sell price after current day
14        if (i >= maxSellPriceIdx) {
15            const remainingPrices = prices.slice(i);
16            maxSellPrice = Math.max(...remainingPrices);
17            maxSellPriceIdx = remainingPrices.lastIndexOf(maxSellPrice);
18        }
19        max = Math.max(maxSellPrice - buyPrice, max);
20
21    }
22    return max;
23};
24
25/**
26 * @param {number[]} prices
27 * @return {number}
28 */
29var maxProfit = function (prices) {
30    let maxProfit = 0;
31    let minPrice = Number.MAX_VALUE;
32
33    prices.forEach(price => {
34        minPrice = Math.min(minPrice, price);
35        let profit = price - minPrice;
36        maxProfit = Math.max(maxProfit, profit)
37    })
38
39    return maxProfit
40}
41
42console.log(maxProfit([7, 1, 5, 3, 6, 4])); // 5
43console.log(maxProfit([7, 6, 4, 3, 1])); // 0
44console.log(maxProfit([1])); // 0
45console.log(maxProfit([1, 2])); // 1

409. Longest Palindrome

src: https://leetcode.com/problems/longest-palindrome

note

Given a string s which consists of lowercase or uppercase letters, return the length of the longest palindrome that can be built with those letters.

Imagine we build a palindrome string, it will have as many as partnered letters as possible, plus possibly a unique center character.

If the number of occurrences of a letter is even, add the count to the total length of the palindrome.
If the number of occurrences of a letter is odd, subtract the count by 1 and add it to the total length of the palindrome.
If the palindrome haven't added a unique character to the center, add 1 to the length of the palindrome if a character with the number of occurrences equals 1 is found.
- e.g. {b : 2, f : 1, c : 1}, f can be added to the center of the palindrome and it is the only character that is unique.

warning

We can only insert 1 unique character and it has to be at the center.
aa, abba are palindrome strings. The center of the palindrome can have 2 characters.

/**
 * @param {string} s
 * @return {number}
 */
var longestPalindrome = function (s) {
    if (s.length === 1) return 1;

    const termFreq = tf(s);
    console.log(termFreq);
    let length = 0;

    for (const count of Object.values(termFreq)) {
        if (count % 2 === 0) {
            length += count;
        } else {
            length += count - 1;
        }

        // we can only add 1 unique char to the center
        // length % 2 === 0 means we haven't added a unique center char
        if (length % 2 === 0 && count % 2 === 1) {
            length++;
        }
    }

    return length
};
/**
 * Get the term frequency of a string
 * @param {string} s 
 */
function tf(s) {
    const termFreq = {};
    for (let i = 0; i < s.length; i++) {
        const char = s[i];
        if (termFreq[char]) {
            termFreq[char] += 1
        } else {
            termFreq[char] = 1;
        }
    }
    const sortable = Object.fromEntries(
        Object.entries(termFreq).sort(([, a], [, b]) => b - a)
    );

    return sortable;
}

console.log(longestPalindrome("abccccdde") === 7); // 7, e.g., dccaccd | ccdcc
console.log(longestPalindrome("a") === 1); // 1
console.log(longestPalindrome("bb") === 2); // 2

console.log(longestPalindrome("bananas") === 5); // 5 e.g. naban | odd even
console.log(longestPalindrome("ccccdd") === 6); // 6 e.g. ccddcc

console.log(longestPalindrome("aaaa") === 4);
console.log(longestPalindrome("tattarrattat") === 12);
console.log(longestPalindrome("tattarrattatxx") === 14); // tatta  rxxr attat

1/**
2 * @param {string} s
3 * @return {number}
4 */
5var longestPalindrome = function (s) {
6    if (s.length === 1) return 1;
7
8    const termFreq = tf(s);
9    console.log(termFreq);
10    let length = 0;
11
12    for (const count of Object.values(termFreq)) {
13        if (count % 2 === 0) {
14            length += count;
15        } else {
16            length += count - 1;
17        }
18
19        // we can only add 1 unique char to the center
20        // length % 2 === 0 means we haven't added a unique center char
21        if (length % 2 === 0 && count % 2 === 1) {
22            length++;
23        }
24    }
25
26    return length
27};
28/**
29 * Get the term frequency of a string
30 * @param {string} s 
31 */
32function tf(s) {
33    const termFreq = {};
34    for (let i = 0; i < s.length; i++) {
35        const char = s[i];
36        if (termFreq[char]) {
37            termFreq[char] += 1
38        } else {
39            termFreq[char] = 1;
40        }
41    }
42    const sortable = Object.fromEntries(
43        Object.entries(termFreq).sort(([, a], [, b]) => b - a)
44    );
45
46    return sortable;
47}
48
49console.log(longestPalindrome("abccccdde") === 7); // 7, e.g., dccaccd | ccdcc
50console.log(longestPalindrome("a") === 1); // 1
51console.log(longestPalindrome("bb") === 2); // 2
52
53console.log(longestPalindrome("bananas") === 5); // 5 e.g. naban | odd even
54console.log(longestPalindrome("ccccdd") === 6); // 6 e.g. ccddcc
55
56console.log(longestPalindrome("aaaa") === 4);
57console.log(longestPalindrome("tattarrattat") === 12);
58console.log(longestPalindrome("tattarrattatxx") === 14); // tatta  rxxr attat

Day 6 Tree

589. N-ary Tree Preorder Traversal

src: https://leetcode.com/problems/n-ary-tree-preorder-traversal

note

example 1

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

Pre-order traversal is root -> left -> right.

/**
 * Definition for a Node.
 * @param {number} val 
 * @param {Node[]} children 
 */
function TreeNode(val, children) {
    this.val = val;
    this.children = children;
};

/**
 * @param {Node|null} root
 * @return {number[]}
 */
var preorderRecursive = function (root) {
    // root left right
    const result = [];
    _preorder(root, result);
    return result
};

var _preorder = function (root, array) {
    if (!root) return
    array.push(root.val)
    root.children?.forEach(node => {
        _preorder(node, array)
    })
}

// preorderIterative
const preorder = (root) => {
    if (!root) return [];

    const result = [];
    const stack = [root];

    while (stack.length) {
        const node = stack.pop()
        if (node.children) {
            stack.push(...node.children.reverse())
        }
        result.push(node.val)
    }

    return result;
}

const root = new TreeNode(1);
const three = new TreeNode(3);
const two = new TreeNode(2);
const four = new TreeNode(4);
const five = new TreeNode(5);
const six = new TreeNode(6);

root.children = [three, two, four]
three.children = [five, six];

console.log(preorder(root))

1/**
2 * Definition for a Node.
3 * @param {number} val 
4 * @param {Node[]} children 
5 */
6function TreeNode(val, children) {
7    this.val = val;
8    this.children = children;
9};
10
11/**
12 * @param {Node|null} root
13 * @return {number[]}
14 */
15var preorderRecursive = function (root) {
16    // root left right
17    const result = [];
18    _preorder(root, result);
19    return result
20};
21
22var _preorder = function (root, array) {
23    if (!root) return
24    array.push(root.val)
25    root.children?.forEach(node => {
26        _preorder(node, array)
27    })
28}
29
30// preorderIterative
31const preorder = (root) => {
32    if (!root) return [];
33
34    const result = [];
35    const stack = [root];
36
37    while (stack.length) {
38        const node = stack.pop()
39        if (node.children) {
40            stack.push(...node.children.reverse())
41        }
42        result.push(node.val)
43    }
44
45    return result;
46}
47
48const root = new TreeNode(1);
49const three = new TreeNode(3);
50const two = new TreeNode(2);
51const four = new TreeNode(4);
52const five = new TreeNode(5);
53const six = new TreeNode(6);
54
55root.children = [three, two, four]
56three.children = [five, six];
57
58console.log(preorder(root))

102. Binary Tree Level Order Traversal

src: https://leetcode.com/problems/binary-tree-level-order-traversal

note

level order traversal example

Input: root = [3,9,20,null,null,15,7]
Output: [[3],[9,20],[15,7]]

Enqueue all nodes of a level.
Process the tree level-by-level.
- Enqueue all children of each node in the current level.
- How to process level-by-level? This is achieved by checking the number of nodes in a level before processing a level.

// 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 levelOrder = function (root) {
    if (!root) return [];
    const result = []
    const queue = [root];

    while (queue.length) {
        const numNodes = queue.length;

        const level = [];
        // enqueue all the children of each node in the current level
        for (let i = 0; i < numNodes; i++) {
            const node = queue.shift();
            level.push(node.val);
            node.left && queue.push(node.left);
            node.right && queue.push(node.right);
        }
        // finish current level
        result.push(level);
    }

    return result
};

const three = new TreeNode(3);
const nine = new TreeNode(9);
const twenty = new TreeNode(20);
const fifteen = new TreeNode(15);
const seven = new TreeNode(7);
const one = new TreeNode(1);

three.left = nine;
three.right = twenty;

twenty.left = fifteen;
twenty.right = seven

nine.left = one

// Output: [[3],[9,20],[15,7]]
console.log(levelOrder(three));

1// Definition for a binary tree node.
2function TreeNode(val, left, right) {
3    this.val = (val === undefined ? 0 : val)
4    this.left = (left === undefined ? null : left)
5    this.right = (right === undefined ? null : right)
6}
7/**
8 * @param {TreeNode} root
9 * @return {number[][]}
10 */
11var levelOrder = function (root) {
12    if (!root) return [];
13    const result = []
14    const queue = [root];
15
16    while (queue.length) {
17        const numNodes = queue.length;
18
19        const level = [];
20        // enqueue all the children of each node in the current level
21        for (let i = 0; i < numNodes; i++) {
22            const node = queue.shift();
23            level.push(node.val);
24            node.left && queue.push(node.left);
25            node.right && queue.push(node.right);
26        }
27        // finish current level
28        result.push(level);
29    }
30
31    return result
32};
33
34const three = new TreeNode(3);
35const nine = new TreeNode(9);
36const twenty = new TreeNode(20);
37const fifteen = new TreeNode(15);
38const seven = new TreeNode(7);
39const one = new TreeNode(1);
40
41three.left = nine;
42three.right = twenty;
43
44twenty.left = fifteen;
45twenty.right = seven
46
47nine.left = one
48
49// Output: [[3],[9,20],[15,7]]
50console.log(levelOrder(three));

Day 7 Binary Search

704. Binary Search

src: https://leetcode.com/problems/binary-search

note

Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, then return its index. Otherwise, return -1.

Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4
Explanation: 9 exists in nums and its index is 4

Input: nums = [-1,0,3,5,9,12], target = 2
Output: -1
Explanation: 2 does not exist in nums so return -1

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var search = function (nums, target) {
    let left = 0;
    let right = nums.length - 1;

    while (left <= right) {
        let middle = Math.floor((right + left) / 2);
        const middleNum = nums[middle];
        if (middleNum < target) {
            left = middle + 1;
        } else if (middleNum > target) {
            right = middle - 1;
        } else {
            return middle;
        }
    }
    return -1;
};

console.log(search([-1, 0, 3, 5, 9, 12], 9)); // 4
console.log(search([-1, 0, 3, 5, 9, 12, 88], 2)); // -1
console.log(search([5], 5)); // 0
console.log(search([-1, 0, 3, 5, 9, 12], 9)); // 4

1/**
2 * @param {number[]} nums
3 * @param {number} target
4 * @return {number}
5 */
6var search = function (nums, target) {
7    let left = 0;
8    let right = nums.length - 1;
9
10    while (left <= right) {
11        let middle = Math.floor((right + left) / 2);
12        const middleNum = nums[middle];
13        if (middleNum < target) {
14            left = middle + 1;
15        } else if (middleNum > target) {
16            right = middle - 1;
17        } else {
18            return middle;
19        }
20    }
21    return -1;
22};
23
24console.log(search([-1, 0, 3, 5, 9, 12], 9)); // 4
25console.log(search([-1, 0, 3, 5, 9, 12, 88], 2)); // -1
26console.log(search([5], 5)); // 0
27console.log(search([-1, 0, 3, 5, 9, 12], 9)); // 4

278. First Bad Version

src: https://leetcode.com/problems/first-bad-version

// give up

1// give up

Day 8 Binary Search Tree

98. Validate Binary Search Tree

src: https://leetcode.com/problems/validate-binary-search-tree

note

Given the root of a binary tree, determine if it is a valid binary search tree (BST).

A valid BST is defined as follows:

The left subtree of a node contains only nodes with keys less than the node's key.
The right subtree of a node contains only nodes with keys greater than the node's key.
Both the left and right subtrees must also be binary search trees.

Example 1

example 1

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

example 2

Input: root = [5,1,4,null,null,3,6]
Output: false
Explanation: The root node's value is 5 but its right child's value is 4.

Solution 1

solution

Main idea: Check if the current node's value is within the valid range (floor/ceiling).

Base case: root=null, the tree is a valid binary search tree.
Recursively check the valid range of each node floor < root.val < ceiling:
- Initially, the valid range of the root node is $[\infty, +\infty]$
- After visiting the root, we start restricting the valid range.
  - If we move to the left child, the ceiling of the left child will be updated to root.val.
  - If we move to the right child, the floor of the right child will be updated to root.val.

var isValidBST = function (root, floor = -Infinity, ceiling = Infinity) {
  if (!root) return true;

  if (!(floor < root.val && root.val < ceiling)) {
    return false;
  }

  return (
    isValidBST(root.left, floor, root.val) &&
    isValidBST(root.right, root.val, ceiling)
  );
};

Solution 2

Use in-order traversal to collect all the values of a binary search tree, then check if the values are in the correct order (ascending).

var isValidBST = function (root) {
    const nums = [];
    in_order_traversal(root, (val) => nums.push(val));

    // check if the values are in the correct order
    for (let i = 0; i < nums.length - 1; i++) {
        if (!(nums[i] < nums[i + 1])) {
            return false
        }
    }
    return true
}

function in_order_traversal(root, cb) {
    if (!root) return
    in_order_traversal(root.left, cb);
    root && cb(root.val);
    in_order_traversal(root.right, cb);
}

// 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)
}

/**
 * Create a binary tree from array and return the root
 * @param {number[]} nums 
 * @return {TreeNode} The root of the binary tree
 */
function createTree(nums) {
    const nodes = nums.map((num => num !== null ? new TreeNode(num) : null));
    let current = null;

    for (let idx = 0; idx < nums.length; idx++) {
        // left child: idx * 2 + 1
        // right child: idx * 2 + 2
        current = nodes[idx];
        if (!current) continue
        current.left = nodes[idx * 2 + 1]
        current.right = nodes[idx * 2 + 2]
    }
    return nodes[0];
}

// in_order_traversal(createTree([3, 1, 5, 0, 2, 4, 6]), console.log)
console.log(isValidBST(createTree([2, 1, 3])) === true); // true
console.log(isValidBST(createTree([5, 4, 6, null, null, 3, 7])) === false); // false
console.log(isValidBST(createTree([32, 26, 47, 19, null, null, 56, null, 27])) === false); // false
console.log(isValidBST(createTree([3, 1, 5, 0, 2, 4, 6])) === true); // true
console.log(isValidBST(createTree([120, 70, 140, 50, 100, 130, 160, 20, 55, 75, 110, 119, 135, 150, 200])) === false); // false

1var isValidBST = function (root) {
2    const nums = [];
3    in_order_traversal(root, (val) => nums.push(val));
4
5    // check if the values are in the correct order
6    for (let i = 0; i < nums.length - 1; i++) {
7        if (!(nums[i] < nums[i + 1])) {
8            return false
9        }
10    }
11    return true
12}
13
14function in_order_traversal(root, cb) {
15    if (!root) return
16    in_order_traversal(root.left, cb);
17    root && cb(root.val);
18    in_order_traversal(root.right, cb);
19}
20
21// Definition for a binary tree node.
22function TreeNode(val, left, right) {
23    this.val = (val === undefined ? 0 : val)
24    this.left = (left === undefined ? null : left)
25    this.right = (right === undefined ? null : right)
26}
27
28/**
29 * Create a binary tree from array and return the root
30 * @param {number[]} nums 
31 * @return {TreeNode} The root of the binary tree
32 */
33function createTree(nums) {
34    const nodes = nums.map((num => num !== null ? new TreeNode(num) : null));
35    let current = null;
36
37    for (let idx = 0; idx < nums.length; idx++) {
38        // left child: idx * 2 + 1
39        // right child: idx * 2 + 2
40        current = nodes[idx];
41        if (!current) continue
42        current.left = nodes[idx * 2 + 1]
43        current.right = nodes[idx * 2 + 2]
44    }
45    return nodes[0];
46}
47
48// in_order_traversal(createTree([3, 1, 5, 0, 2, 4, 6]), console.log)
49console.log(isValidBST(createTree([2, 1, 3])) === true); // true
50console.log(isValidBST(createTree([5, 4, 6, null, null, 3, 7])) === false); // false
51console.log(isValidBST(createTree([32, 26, 47, 19, null, null, 56, null, 27])) === false); // false
52console.log(isValidBST(createTree([3, 1, 5, 0, 2, 4, 6])) === true); // true
53console.log(isValidBST(createTree([120, 70, 140, 50, 100, 130, 160, 20, 55, 75, 110, 119, 135, 150, 200])) === false); // false

235. Lowest Common Ancestor of a Binary Search Tree

src: https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree

note

Given a binary search tree (BST), find the lowest common ancestor (LCA) node of two given nodes in the BST.

“The lowest common ancestor is defined between two nodes p and q as the lowest node in Tree that has both p and q as descendants (where we allow a node to be a descendant of itself).”

Example 1:

eg 1

Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
Output: 6
Explanation: The LCA of nodes 2 and 8 is 6.

Example 2:

eg 2

Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
Output: 2
Explanation: The LCA of nodes 2 and 4 is 2,
since a node can be a descendant of itself according to the LCA definition.

Solution 1

Level order traversal, callback(node, levelNum)
- Search for the target nodes based on the current node.
  - Found target nodes - update the lowest common ancestor
  - Not found - break

Solution 2

solution

If both target nodes are less than the current node, pick the left child as the potential common ancestor.
If both target nodes are greater than the current node, pick the right child as the potential common ancestor.
If the current node is causing a diverging, return the current node. e.g. 0 and 5 go for different subtrees at node 2. So node 2 is the lowest common ancestor.

info

There are some special constraints:

All Node.val are unique.
p != q
p and q will exist in the BST.

// 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)
}

/**
 * Create a binary tree from array and return the root
 * @param {number[]} nums 
 * @return {TreeNode} The root of the binary tree
 */
function createTree(nums) {
    const nodes = nums.map((num => num !== null ? new TreeNode(num) : null));
    let current = null;

    for (let idx = 0; idx < nums.length; idx++) {
        // left child: idx * 2 + 1
        // right child: idx * 2 + 2
        current = nodes[idx];
        if (!current) continue
        current.left = nodes[idx * 2 + 1]
        current.right = nodes[idx * 2 + 2]
    }
    return nodes[0];
}

function levelOrderTraversal(root, cb) {
    const queue = [root];
    let levelNum = 0;
    while (queue.length !== 0) {
        // num nodes at the current level
        const numNodes = queue.length;
        for (let i = 0; i < numNodes; i++) {
            let currentNode = queue.shift();
            currentNode.left && queue.push(currentNode.left);
            currentNode.right && queue.push(currentNode.right);
            if (cb(currentNode, levelNum)) return
        }
        levelNum++;
    }
}

/**
 * Search a node in a binary search tree. Use the `.val` to make comparison
 * @param {TreeNode} root root of a binary search tree
 * @param {TreeNode} target the target node to search
 * @return {TreeNode} If the node is found, return the node otherwise null.
 */
function search(root, target) {
    if (!root) return null;
    if (root.val === target.val) return root;
    if (target.val < root.val) return search(root.left, target);
    if (target.val > root.val) return search(root.right, target);
    return null;
}

/**
 * @param {TreeNode} root
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {TreeNode}
 */
var lowestCommonAncestor = function (root, p, q) {
    let maxLevel = -Infinity
    let commonAncestor = null;
    // level order traversal
    levelOrderTraversal(root, (node, levelNum) => {
        // search for p, q
        if (search(node, p) && search(node, q)) {
            if (levelNum > maxLevel) {
                maxLevel = levelNum;
                commonAncestor = node;
            }
        } else {
            return false
        }
    })

    return commonAncestor;

};

function eg1() {
    const root = createTree([6, 2, 8, 0, 4, 7, 9, null, null, 3, 5]);
    const p = root.left;
    const q = root.right;
    console.log(lowestCommonAncestor(root, p, q).val);
}

function eg2() {
    const root = createTree([6, 2, 8, 0, 4, 7, 9, null, null, 3, 5]);
    const p = root.left;
    const q = p.right;
    console.log(lowestCommonAncestor(root, p, q).val);
}

eg1();
eg2();

1// Definition for a binary tree node.
2function TreeNode(val, left, right) {
3    this.val = (val === undefined ? 0 : val)
4    this.left = (left === undefined ? null : left)
5    this.right = (right === undefined ? null : right)
6}
7
8/**
9 * Create a binary tree from array and return the root
10 * @param {number[]} nums 
11 * @return {TreeNode} The root of the binary tree
12 */
13function createTree(nums) {
14    const nodes = nums.map((num => num !== null ? new TreeNode(num) : null));
15    let current = null;
16
17    for (let idx = 0; idx < nums.length; idx++) {
18        // left child: idx * 2 + 1
19        // right child: idx * 2 + 2
20        current = nodes[idx];
21        if (!current) continue
22        current.left = nodes[idx * 2 + 1]
23        current.right = nodes[idx * 2 + 2]
24    }
25    return nodes[0];
26}
27
28function levelOrderTraversal(root, cb) {
29    const queue = [root];
30    let levelNum = 0;
31    while (queue.length !== 0) {
32        // num nodes at the current level
33        const numNodes = queue.length;
34        for (let i = 0; i < numNodes; i++) {
35            let currentNode = queue.shift();
36            currentNode.left && queue.push(currentNode.left);
37            currentNode.right && queue.push(currentNode.right);
38            if (cb(currentNode, levelNum)) return
39        }
40        levelNum++;
41    }
42}
43
44/**
45 * Search a node in a binary search tree. Use the `.val` to make comparison
46 * @param {TreeNode} root root of a binary search tree
47 * @param {TreeNode} target the target node to search
48 * @return {TreeNode} If the node is found, return the node otherwise null.
49 */
50function search(root, target) {
51    if (!root) return null;
52    if (root.val === target.val) return root;
53    if (target.val < root.val) return search(root.left, target);
54    if (target.val > root.val) return search(root.right, target);
55    return null;
56}
57
58/**
59 * @param {TreeNode} root
60 * @param {TreeNode} p
61 * @param {TreeNode} q
62 * @return {TreeNode}
63 */
64var lowestCommonAncestor = function (root, p, q) {
65    let maxLevel = -Infinity
66    let commonAncestor = null;
67    // level order traversal
68    levelOrderTraversal(root, (node, levelNum) => {
69        // search for p, q
70        if (search(node, p) && search(node, q)) {
71            if (levelNum > maxLevel) {
72                maxLevel = levelNum;
73                commonAncestor = node;
74            }
75        } else {
76            return false
77        }
78    })
79
80    return commonAncestor;
81
82};
83
84function eg1() {
85    const root = createTree([6, 2, 8, 0, 4, 7, 9, null, null, 3, 5]);
86    const p = root.left;
87    const q = root.right;
88    console.log(lowestCommonAncestor(root, p, q).val);
89}
90
91function eg2() {
92    const root = createTree([6, 2, 8, 0, 4, 7, 9, null, null, 3, 5]);
93    const p = root.left;
94    const q = p.right;
95    console.log(lowestCommonAncestor(root, p, q).val);
96}
97
98eg1();
99eg2();

Day 9 Graph/BFS/DFS

733. Flood Fill

Array
Depth-First Search

src: https://leetcode.com/problems/flood-fill

note

You are given three integers sr, sc, and color. You should perform a flood fill on the image starting from the pixel image[sr][sc].

sr: starting row
sc: starting col

To perform a flood fill, consider the starting pixel, plus any pixels connected 4-directionally to the starting pixel of the same color as the starting pixel, plus any pixels connected 4-directionally to those pixels (also with the same color), and so on. Replace the color of all of the aforementioned pixels with color.

Example 1:

example 1

Input: image = [[1,1,1],[1,1,0],[1,0,1]], sr = 1, sc = 1, color = 2
Output: [[2,2,2],[2,2,0],[2,0,1]]

Example 2:

Input: image = [[0,0,0],[0,0,0]], sr = 0, sc = 0, color = 0
Output: [[0,0,0],[0,0,0]]

/**
 * @param {number[][]} image
 * @param {number} sr
 * @param {number} sc
 * @param {number} color
 * @return {number[][]}
 */
var floodFill = function (image, sr, sc, color, visited = new Set()) {
    const startingPixel = image[sr][sc];
    // any pixels connected 4-directionally to the starting pixel of the same color as the starting pixel
    // top, bottom, left, right
    const START = { row: sr, col: sc }
    const TOP = { row: sr - 1, col: sc }
    const BOTTOM = { row: sr + 1, col: sc };
    const LEFT = { row: sr, col: sc - 1 };
    const RIGHT = { row: sr, col: sc + 1 };
    const PIXELS = [START, TOP, BOTTOM, LEFT, RIGHT];
    // Replace the color of all of the aforementioned pixels with color.
    PIXELS.forEach(neighbor => {
        const position = `${neighbor.row}-${neighbor.col}`
        if (visited.has(position)) return;
        // should have the same color as the starting pixel
        if (image[neighbor.row] !== undefined && image[neighbor.row][neighbor.col] === startingPixel) {
            visited.add(position)
            floodFill(image, neighbor.row, neighbor.col, color, visited);
            image[neighbor.row][neighbor.col] = color;
        }
    })
    return image
};

function eg1() {
    const image = [[1, 1, 1], [1, 1, 0], [1, 0, 1]], sr = 1, sc = 1, color = 2
    console.log(floodFill(image, sr, sc, color))
}

function eg2() {
    const image = [[0, 0, 0], [0, 1, 0]], sr = 1, sc = 1, color = 2;
    console.log(floodFill(image, sr, sc, color))
}

eg1()
eg2()

1/**
2 * @param {number[][]} image
3 * @param {number} sr
4 * @param {number} sc
5 * @param {number} color
6 * @return {number[][]}
7 */
8var floodFill = function (image, sr, sc, color, visited = new Set()) {
9    const startingPixel = image[sr][sc];
10    // any pixels connected 4-directionally to the starting pixel of the same color as the starting pixel
11    // top, bottom, left, right
12    const START = { row: sr, col: sc }
13    const TOP = { row: sr - 1, col: sc }
14    const BOTTOM = { row: sr + 1, col: sc };
15    const LEFT = { row: sr, col: sc - 1 };
16    const RIGHT = { row: sr, col: sc + 1 };
17    const PIXELS = [START, TOP, BOTTOM, LEFT, RIGHT];
18    // Replace the color of all of the aforementioned pixels with color.
19    PIXELS.forEach(neighbor => {
20        const position = `${neighbor.row}-${neighbor.col}`
21        if (visited.has(position)) return;
22        // should have the same color as the starting pixel
23        if (image[neighbor.row] !== undefined && image[neighbor.row][neighbor.col] === startingPixel) {
24            visited.add(position)
25            floodFill(image, neighbor.row, neighbor.col, color, visited);
26            image[neighbor.row][neighbor.col] = color;
27        }
28    })
29    return image
30};
31
32function eg1() {
33    const image = [[1, 1, 1], [1, 1, 0], [1, 0, 1]], sr = 1, sc = 1, color = 2
34    console.log(floodFill(image, sr, sc, color))
35}
36
37function eg2() {
38    const image = [[0, 0, 0], [0, 1, 0]], sr = 1, sc = 1, color = 2;
39    console.log(floodFill(image, sr, sc, color))
40}
41
42eg1()
43eg2()

200. Number of Islands

Array
Depth-First Search

src: https://leetcode.com/problems/number-of-islands

note

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.

Solution

https://leetcode.com/problems/number-of-islands/discuss/56340/Python-Simple-DFS-Solution

Iterate through each of the cell and if it is a land, do DFS to mark the all adjacent lands, then increment the counter by 1.

def numIslands(self, grid):
    if not grid:
        return 0

    count = 0
    for i in range(len(grid)):
        for j in range(len(grid[0])):
            if grid[i][j] == '1':
                self.dfs(grid, i, j)
                count += 1
    return count

def dfs(self, grid, i, j):
    if i<0 or j<0 or i>=len(grid) or j>=len(grid[0]) or grid[i][j] != '1':
        return
    grid[i][j] = '#' # mark/exclude the entire land, only count it once in the main loop
    self.dfs(grid, i+1, j)
    self.dfs(grid, i-1, j)
    self.dfs(grid, i, j+1)
    self.dfs(grid, i, j-1)



/**
 * @param {character[][]} grid
 * @return {number} The number of islands in the grid.
 */
var numIslands = function (grid) {

    function dfs(grid, sr, sc, visited) {
        const START = { row: sr, col: sc }
        const TOP = { row: sr - 1, col: sc }
        const BOTTOM = { row: sr + 1, col: sc };
        const LEFT = { row: sr, col: sc - 1 };
        const RIGHT = { row: sr, col: sc + 1 };
        const POSITIONS = [START, TOP, BOTTOM, LEFT, RIGHT];
        for (let i = 0; i < POSITIONS.length; i++) {
            const position = POSITIONS[i];
            const coordinate = `${position.row}-${position.col}`
            if (visited.has(coordinate)) continue
            if (grid[position.row] !== undefined && grid[position.row][position.col] === "1") {
                visited.add(coordinate);
                dfs(grid, position.row, position.col, visited);
            }
        }

    }
    const visited = new Set();
    let numVisited = -1;
    let count = 0;
    for (let row = 0; row < grid.length; row++) {
        for (let col = 0; col < grid[0].length; col++) {
            if (grid[row][col] === "0") continue
            const coordinate = `${row}-${col}`;
            if (visited.has(coordinate)) continue;
            dfs(grid, row, col, visited)
            if (visited.size > 0 && visited.size !== numVisited) {
                numVisited = visited.size;
                count++;
            }
        }
    }

    return count
};

// explore all 1s at the current region, when the stack is empty, increment numIslands by 1
// start from the water, find the land which has not visited
// if a land is found, exploring all 1s started from the land

function eg1() {
    const grid = [
        ["1", "1", "1", "1", "0"],
        ["1", "1", "0", "1", "0"],
        ["1", "1", "0", "0", "0"],
        ["0", "0", "0", "0", "0"]
    ]

    console.log(numIslands(grid)); // 1
}

function eg2() {
    const grid = [
        ["1", "1", "0", "0", "0"],
        ["1", "1", "0", "0", "0"],
        ["0", "0", "1", "0", "0"],
        ["0", "0", "0", "1", "1"]
    ]

    console.log(numIslands(grid)); // 3
}

function eg3() {
    const grid = [["0"]]
    console.log(numIslands(grid)); // 0
}

function eg4() {
    const grid = [
        ["0", "1", "0"],
        ["1", "0", "1"],
        ["0", "1", "0"]]

    console.log(numIslands(grid)); // 4
}


eg1();
eg2();
eg3();
eg4();

1
2
3/**
4 * @param {character[][]} grid
5 * @return {number} The number of islands in the grid.
6 */
7var numIslands = function (grid) {
8
9    function dfs(grid, sr, sc, visited) {
10        const START = { row: sr, col: sc }
11        const TOP = { row: sr - 1, col: sc }
12        const BOTTOM = { row: sr + 1, col: sc };
13        const LEFT = { row: sr, col: sc - 1 };
14        const RIGHT = { row: sr, col: sc + 1 };
15        const POSITIONS = [START, TOP, BOTTOM, LEFT, RIGHT];
16        for (let i = 0; i < POSITIONS.length; i++) {
17            const position = POSITIONS[i];
18            const coordinate = `${position.row}-${position.col}`
19            if (visited.has(coordinate)) continue
20            if (grid[position.row] !== undefined && grid[position.row][position.col] === "1") {
21                visited.add(coordinate);
22                dfs(grid, position.row, position.col, visited);
23            }
24        }
25
26    }
27    const visited = new Set();
28    let numVisited = -1;
29    let count = 0;
30    for (let row = 0; row < grid.length; row++) {
31        for (let col = 0; col < grid[0].length; col++) {
32            if (grid[row][col] === "0") continue
33            const coordinate = `${row}-${col}`;
34            if (visited.has(coordinate)) continue;
35            dfs(grid, row, col, visited)
36            if (visited.size > 0 && visited.size !== numVisited) {
37                numVisited = visited.size;
38                count++;
39            }
40        }
41    }
42
43    return count
44};
45
46// explore all 1s at the current region, when the stack is empty, increment numIslands by 1
47// start from the water, find the land which has not visited
48// if a land is found, exploring all 1s started from the land
49
50function eg1() {
51    const grid = [
52        ["1", "1", "1", "1", "0"],
53        ["1", "1", "0", "1", "0"],
54        ["1", "1", "0", "0", "0"],
55        ["0", "0", "0", "0", "0"]
56    ]
57
58    console.log(numIslands(grid)); // 1
59}
60
61function eg2() {
62    const grid = [
63        ["1", "1", "0", "0", "0"],
64        ["1", "1", "0", "0", "0"],
65        ["0", "0", "1", "0", "0"],
66        ["0", "0", "0", "1", "1"]
67    ]
68
69    console.log(numIslands(grid)); // 3
70}
71
72function eg3() {
73    const grid = [["0"]]
74    console.log(numIslands(grid)); // 0
75}
76
77function eg4() {
78    const grid = [
79        ["0", "1", "0"],
80        ["1", "0", "1"],
81        ["0", "1", "0"]]
82
83    console.log(numIslands(grid)); // 4
84}
85
86
87eg1();
88eg2();
89eg3();
90eg4();

Day 10 Dynamic Programming

509. Fibonacci Number

src: https://leetcode.com/problems/fibonacci-number

/**
 * @param {number} n
 * @return {number}
 */
var fib = function (n, memo = {}) {
    if (n in memo) {
        return memo[n];
    }
    if (n === 0) return 0;
    if (n === 1) return 1;
    const value = fib(n - 1, memo) + fib(n - 2, memo);
    memo[n] = value;
    return value;
};

function eg() {
    console.log(fib(2)); // 1
    console.log(fib(3)); // 2
    console.log(fib(4)); // 3
    console.log(fib(5)); // 5

}

eg()

1/**
2 * @param {number} n
3 * @return {number}
4 */
5var fib = function (n, memo = {}) {
6    if (n in memo) {
7        return memo[n];
8    }
9    if (n === 0) return 0;
10    if (n === 1) return 1;
11    const value = fib(n - 1, memo) + fib(n - 2, memo);
12    memo[n] = value;
13    return value;
14};
15
16function eg() {
17    console.log(fib(2)); // 1
18    console.log(fib(3)); // 2
19    console.log(fib(4)); // 3
20    console.log(fib(5)); // 5
21
22}
23
24eg()

70. Climbing Stairs

src: https://leetcode.com/problems/climbing-stairs

def climbStairs(n):
    if n == 1:
        return 1
    if n == 2:
        return 2
    return climbStairs(n-1) + climbStairs(n-2)

/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function (n, memo = {}) {
    if (n in memo) return memo[n];

    if (n === 0) return 0;
    if (n === 1) return 1;
    if (n === 2) return 2;
    const value = climbStairs(n - 1, memo) + climbStairs(n - 2, memo)
    memo[n] = value
    return value;
};

console.log(climbStairs(4)); // 5

1/**
2 * @param {number} n
3 * @return {number}
4 */
5var climbStairs = function (n, memo = {}) {
6    if (n in memo) return memo[n];
7
8    if (n === 0) return 0;
9    if (n === 1) return 1;
10    if (n === 2) return 2;
11    const value = climbStairs(n - 1, memo) + climbStairs(n - 2, memo)
12    memo[n] = value
13    return value;
14};
15
16console.log(climbStairs(4)); // 5

Day 11 Dynamic Programming

Dynamic Programming - Learn to Solve Algorithmic Problems

746. Min Cost Climbing Stairs

src: https://leetcode.com/problems/min-cost-climbing-stairs

/**
 * @param {number[]} cost
 * @return {number}
 */
var minCostClimbingStairs = function (cost) {
    for (let i = 0; i < cost.length; i++) {
        cost[i] += Math.min(cost[i - 1] ?? 0, cost[i - 2] ?? 0)
    }
    const n = cost.length;
    return Math.min(cost[n - 1], cost[n - 2]);
};

console.log(minCostClimbingStairs([10, 15, 20])); // 15
console.log(minCostClimbingStairs([1, 100, 1, 1, 1, 100, 1, 1, 100, 1])); // 6

1/**
2 * @param {number[]} cost
3 * @return {number}
4 */
5var minCostClimbingStairs = function (cost) {
6    for (let i = 0; i < cost.length; i++) {
7        cost[i] += Math.min(cost[i - 1] ?? 0, cost[i - 2] ?? 0)
8    }
9    const n = cost.length;
10    return Math.min(cost[n - 1], cost[n - 2]);
11};
12
13console.log(minCostClimbingStairs([10, 15, 20])); // 15
14console.log(minCostClimbingStairs([1, 100, 1, 1, 1, 100, 1, 1, 100, 1])); // 6
15

62. Unique Paths

src: https://leetcode.com/problems/unique-paths

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

    // initialize the table by filling ones to the bottom and right
    // fill the bottom line
    for (let col = 0; col < n; col++) {
        dp[m - 1][col] = 1;
    }
    // fill the right line
    for (let row = 0; row < m; row++) {
        dp[row][n - 1] = 1;
    }

    for (let row = m - 2; row >= 0; row--) {
        for (let col = n - 2; col >= 0; col--) {
            dp[row][col] = dp[row + 1][col] + dp[row][col + 1]
        }
    }

    return dp[0][0]
};

console.log(uniquePaths(3, 2)); // 3
console.log(uniquePaths(3, 7)); // 28

1/**
2 * @param {number} m
3 * @param {number} n
4 * @return {number}
5 */
6var uniquePaths = function (m, n) {
7    const dp = Array(m).fill(null).map(() => [...Array(n)].fill(0));
8
9    // initialize the table by filling ones to the bottom and right
10    // fill the bottom line
11    for (let col = 0; col < n; col++) {
12        dp[m - 1][col] = 1;
13    }
14    // fill the right line
15    for (let row = 0; row < m; row++) {
16        dp[row][n - 1] = 1;
17    }
18
19    for (let row = m - 2; row >= 0; row--) {
20        for (let col = n - 2; col >= 0; col--) {
21            dp[row][col] = dp[row + 1][col] + dp[row][col + 1]
22        }
23    }
24
25    return dp[0][0]
26};
27
28console.log(uniquePaths(3, 2)); // 3
29console.log(uniquePaths(3, 7)); // 28
30

Day 12 Sliding Window/Two Pointer

438. Find All Anagrams in a String

src: https://leetcode.com/problems/find-all-anagrams-in-a-string

Use sliding window technique, which is inspired by this https://leetcode.com/problems/find-all-anagrams-in-a-string/discuss/2052920/Clean-JavaScript

function getWordFreq(str) {
    const freq = {}
    for (const char of "abcdefghijklmnopqrstuvwxyz") {
        freq[char] = 0;
    }

    for (let i = 0; i < str.length; i++) {
        const char = str[i]
        freq[char] += 1;
    }

    return freq;
}

function isSameFreq(freq1, freq2) {
    for (const char of "abcdefghijklmnopqrstuvwxyz") {
        if (freq1[char] !== freq2[char]) {
            return false;
        }
    }

    return true;
}

/**
 * @param {string} s
 * @param {string} p
 * @return {number[]}
 */
var findAnagrams = function (s, p) {
    if (p.length > s.length) return []
    const wordFreq = getWordFreq(p);
    const indices = [];


    const sliceWordFreq = getWordFreq(s.slice(0, p.length));
    for (let i = 0; i < s.length; i++) {

        if (isSameFreq(wordFreq, sliceWordFreq)) indices.push(i);

        // remove the current char
        sliceWordFreq[s[i]] -= 1;
        // add the next char
        sliceWordFreq[s[i + p.length]] += 1;

    }
    return indices
};

console.log(findAnagrams("cbaebabacd", "abc")); // [0, 6]
console.log(findAnagrams("abab", "ab")); // [0, 1, 2]
console.log(findAnagrams("aaaaaaaaaa", "aaaaaaaaaaaaa"));

1function getWordFreq(str) {
2    const freq = {}
3    for (const char of "abcdefghijklmnopqrstuvwxyz") {
4        freq[char] = 0;
5    }
6
7    for (let i = 0; i < str.length; i++) {
8        const char = str[i]
9        freq[char] += 1;
10    }
11
12    return freq;
13}
14
15function isSameFreq(freq1, freq2) {
16    for (const char of "abcdefghijklmnopqrstuvwxyz") {
17        if (freq1[char] !== freq2[char]) {
18            return false;
19        }
20    }
21
22    return true;
23}
24
25/**
26 * @param {string} s
27 * @param {string} p
28 * @return {number[]}
29 */
30var findAnagrams = function (s, p) {
31    if (p.length > s.length) return []
32    const wordFreq = getWordFreq(p);
33    const indices = [];
34
35
36    const sliceWordFreq = getWordFreq(s.slice(0, p.length));
37    for (let i = 0; i < s.length; i++) {
38
39        if (isSameFreq(wordFreq, sliceWordFreq)) indices.push(i);
40
41        // remove the current char
42        sliceWordFreq[s[i]] -= 1;
43        // add the next char
44        sliceWordFreq[s[i + p.length]] += 1;
45
46    }
47    return indices
48};
49
50console.log(findAnagrams("cbaebabacd", "abc")); // [0, 6]
51console.log(findAnagrams("abab", "ab")); // [0, 1, 2]
52console.log(findAnagrams("aaaaaaaaaa", "aaaaaaaaaaaaa"));

424. Longest Repeating Character Replacement

src: https://leetcode.com/problems/longest-repeating-character-replacement

Inspired by this video: https://www.youtube.com/watch?v=gqXU1UyA8pk

function createFreq() {
    const freq = {}
    for (const char of "abcdefghijklmnopqrstuvwxyz".toUpperCase()) {
        freq[char] = 0;
    }
    return freq;
}

function findMaxFreq(freq) {
    return Math.max(...Object.values(freq));
}


/**
 * @param {string} s
 * @param {number} k
 * @return {number}
 */
var characterReplacement = function (s, k) {
    let left = 0;
    let right = 0;
    const freq = createFreq()

    let maxLength = 0;

    while (right < s.length) {
        freq[s.charAt(right)]++;

        const size = (right - left + 1);
        const isWindowValid = size - findMaxFreq(freq) <= k
        if (!isWindowValid) {
            freq[s.charAt(left)]--;
            left++;
        } else {
            maxLength = Math.max(size, maxLength)
        }
        right++;
    }

    return maxLength;
};

console.log(characterReplacement("AABABBA", 1)); // 4

console.log(characterReplacement("ABAB", 2)); // 4
console.log(characterReplacement("ABBB", 2)); // 4
console.log(characterReplacement("ABAA", 0)); // 2
console.log(characterReplacement("AAAB", 0)); // 3
console.log(characterReplacement("AABABBAAAABAAAA", 1)); // 9

1function createFreq() {
2    const freq = {}
3    for (const char of "abcdefghijklmnopqrstuvwxyz".toUpperCase()) {
4        freq[char] = 0;
5    }
6    return freq;
7}
8
9function findMaxFreq(freq) {
10    return Math.max(...Object.values(freq));
11}
12
13
14/**
15 * @param {string} s
16 * @param {number} k
17 * @return {number}
18 */
19var characterReplacement = function (s, k) {
20    let left = 0;
21    let right = 0;
22    const freq = createFreq()
23
24    let maxLength = 0;
25
26    while (right < s.length) {
27        freq[s.charAt(right)]++;
28
29        const size = (right - left + 1);
30        const isWindowValid = size - findMaxFreq(freq) <= k
31        if (!isWindowValid) {
32            freq[s.charAt(left)]--;
33            left++;
34        } else {
35            maxLength = Math.max(size, maxLength)
36        }
37        right++;
38    }
39
40    return maxLength;
41};
42
43console.log(characterReplacement("AABABBA", 1)); // 4
44
45console.log(characterReplacement("ABAB", 2)); // 4
46console.log(characterReplacement("ABBB", 2)); // 4
47console.log(characterReplacement("ABAA", 0)); // 2
48console.log(characterReplacement("AAAB", 0)); // 3
49console.log(characterReplacement("AABABBAAAABAAAA", 1)); // 9

Day 13 Hashmap

299. Bulls and Cows

src: https://leetcode.com/problems/bulls-and-cows

Given the secret number secret and your friend's guess, return the hint for your friend's guess.

The number of "bulls", which are digits in the guess that are in the correct position.
The number of "cows", which are digits in the guess that are in your secret number but are located in the wrong position. Specifically, the non-bull digits in the guess that could be rearranged such that they become bulls.

Input: secret = "1807", guess = "7810"
Output: "1A3B"
Explanation: Bulls are connected with a '|' and cows are underlined:
"1807"
  |
"7810"

Find the value of bulls and then find the value of guess.

function getNumFreq(num) {
  const freq = {};
  for (const char of "1234567890") {
    freq[char] = 0;
  }

  for (let i = 0; i < num.length; i++) {
    const char = num[i];
    freq[char] += 1;
  }

  return freq;
}

/**
 * @param {string} secret
 * @param {string} guess
 * @return {string}
 */
var getHint = function (secret, guess) {
  let bulls = 0;
  let cows = 0;

  const secretFreq = getNumFreq(secret);
  const guessFreq = getNumFreq(guess);
  for (let i = 0; i < secret.length; i++) {
    // find bulls - accurate match (same digit with same position)
    if (secret.charAt(i) === guess.charAt(i)) {
      bulls++;
      secretFreq[secret.charAt(i)]--;
      guessFreq[secret.charAt(i)]--;
    }
  }

  for (const digit of Object.keys(secretFreq)) {
    if (secretFreq[digit] !== 0) {
      if (guessFreq[digit] >= secretFreq[digit]) {
        cows += secretFreq[digit];
      } else {
        cows += guessFreq[digit];
      }
    }
  }

  return `${bulls}A${cows}B`;
};

console.log(getHint("1807", "7810")); // 1A3B
console.log(getHint("1123", "0111")); // 1A1B
console.log(getHint("1234", "0111")); // "0A1B"
console.log(getHint("1122", "0001")); // 0A1B

1function getNumFreq(num) {
2  const freq = {};
3  for (const char of "1234567890") {
4    freq[char] = 0;
5  }
6
7  for (let i = 0; i < num.length; i++) {
8    const char = num[i];
9    freq[char] += 1;
10  }
11
12  return freq;
13}
14
15/**
16 * @param {string} secret
17 * @param {string} guess
18 * @return {string}
19 */
20var getHint = function (secret, guess) {
21  let bulls = 0;
22  let cows = 0;
23
24  const secretFreq = getNumFreq(secret);
25  const guessFreq = getNumFreq(guess);
26  for (let i = 0; i < secret.length; i++) {
27    // find bulls - accurate match (same digit with same position)
28    if (secret.charAt(i) === guess.charAt(i)) {
29      bulls++;
30      secretFreq[secret.charAt(i)]--;
31      guessFreq[secret.charAt(i)]--;
32    }
33  }
34
35  for (const digit of Object.keys(secretFreq)) {
36    if (secretFreq[digit] !== 0) {
37      if (guessFreq[digit] >= secretFreq[digit]) {
38        cows += secretFreq[digit];
39      } else {
40        cows += guessFreq[digit];
41      }
42    }
43  }
44
45  return `${bulls}A${cows}B`;
46};
47
48console.log(getHint("1807", "7810")); // 1A3B
49console.log(getHint("1123", "0111")); // 1A1B
50console.log(getHint("1234", "0111")); // "0A1B"
51console.log(getHint("1122", "0001")); // 0A1B
52

Day 14 Stack

394. Decode String

src: https://leetcode.com/problems/decode-string

The encoding rule is: k[encoded_string], where the encoded_string inside the square brackets is being repeated exactly k times. Note that k is guaranteed to be a positive integer.

check for balanced brackets.

Inspired by NeetCode https://www.youtube.com/watch?v=qB0zZpBJlh8

note

"3[a2[c]]"

Push every char into the stack unless the char is ].

If ] is found, process the content inside the brackets, and push the processed result to the stack.

/**
 * @param {string} s
 * @return {string}
 */
var decodeString = function (s) {
  const stack = [];

  for (let i = 0; i < s.length; i++) {
    const char = s[i];
    if (char === "]") {
      let temp = "";
      let popped = stack.pop();
      while (popped !== "[") {
        temp = popped + temp;
        popped = stack.pop();
      }

      // repeat the content
      let k = "";
      while (/\d/.test(stack.at(-1))) {
        k = stack.pop() + k;
      }
      k = Number(k);

      let repeated = "";
      for (let j = 0; j < k; j++) {
        repeated += temp;
      }

      stack.push(repeated);
    } else {
      stack.push(char);
    }
  }

  return stack.join("");
};

console.log(decodeString("3[a]2[bc]")); // "aaabcbc"
console.log(decodeString("3[a2[c]]")); // "accaccacc"
console.log(decodeString("101[a2[c]]")); // "accaccacc"

1/**
2 * @param {string} s
3 * @return {string}
4 */
5var decodeString = function (s) {
6  const stack = [];
7
8  for (let i = 0; i < s.length; i++) {
9    const char = s[i];
10    if (char === "]") {
11      let temp = "";
12      let popped = stack.pop();
13      while (popped !== "[") {
14        temp = popped + temp;
15        popped = stack.pop();
16      }
17
18      // repeat the content
19      let k = "";
20      while (/\d/.test(stack.at(-1))) {
21        k = stack.pop() + k;
22      }
23      k = Number(k);
24
25      let repeated = "";
26      for (let j = 0; j < k; j++) {
27        repeated += temp;
28      }
29
30      stack.push(repeated);
31    } else {
32      stack.push(char);
33    }
34  }
35
36  return stack.join("");
37};
38
39console.log(decodeString("3[a]2[bc]")); // "aaabcbc"
40console.log(decodeString("3[a2[c]]")); // "accaccacc"
41console.log(decodeString("101[a2[c]]")); // "accaccacc"
42

Day 15 Heap

1046. Last Stone Weight

You are given an array of integers stones where stones[i] is the weight of the ith stone.

Pick the heaviest two stones. Suppose the heaviest two stones have weights x`` and y with `x <= y. The result of this smash is:

x=y, both stones are destroyed.
x<y, the stone of weight x is destroyed, and the stone of weight y has a new weight y-x.

At the end of the game, there is at most one stone left. (could be zero stone left).

Return the weight of the last stone, if there are no stones left, return 0.

note

Push all elements into a max heap.
Pop the largest two stones, and do the smash.
Push the remaining stone after smashing into the max heap.

/**
 * @param {number[]} stones
 * @return {number}
 */
var lastStoneWeight = function (stones) {
  if (stones.length === 0) return 0;
  if (stones.length === 1) return stones[0];

  buildHeap(stones);
  let numStones = stones.length;
  while (numStones > 0) {
    const left = 1;
    const right = 2;
    let xIdx = stones[left] > stones[right] ? left : right;
    if (right >= stones.length) xIdx = left;

    const y = stones[0];
    const x = stones[xIdx];
    if (x === y) {
      stones[0] = 0;
      stones[xIdx] = 0;
      numStones -= 2;
    }
    if (x !== y) {
      stones[0] -= stones[xIdx];
      stones[xIdx] = 0;
      numStones--;
    }
    heapify(stones, xIdx);
    heapify(stones, 0);
  }
  return stones[0];
};

/**
 * Build a heap represented by an array.
 * @param {number[]} nums
 */
function buildHeap(nums) {
  // Total nodes
  const N = nums.length;
  // Last Non-leaf node index: (N/2)-1
  const startIdx = Math.ceil(N / 2) - 1;

  // heapify the nodes in reverse order level by level
  for (let i = startIdx; i >= 0; i--) {
    heapify(nums, i);
  }
}

/**
 *
 * @param {number[]} nums
 * @param {number} rootIdx The index of the node to heapify
 */
function heapify(nums, rootIdx) {
  let largest = rootIdx;
  const l = rootIdx * 2 + 1;
  const r = rootIdx * 2 + 2;

  if (l < nums.length && nums[l] > nums[largest]) {
    largest = l;
  }

  if (r < nums.length && nums[r] > nums[largest]) {
    largest = r;
  }

  // make the swap
  if (largest !== rootIdx) {
    const temp = nums[rootIdx];
    nums[rootIdx] = nums[largest];
    nums[largest] = temp;

    heapify(nums, largest);
  }
}

console.log(lastStoneWeight([9, 3, 2, 10])); // 0
console.log(lastStoneWeight([1, 3])); // 2
console.log(lastStoneWeight([1, 3, 5, 4, 6, 13, 10, 9, 8, 15, 17]));
console.log(lastStoneWeight([2, 7, 4, 1, 8, 1])); // 1
console.log(lastStoneWeight([1])); // 1

1/**
2 * @param {number[]} stones
3 * @return {number}
4 */
5var lastStoneWeight = function (stones) {
6  if (stones.length === 0) return 0;
7  if (stones.length === 1) return stones[0];
8
9  buildHeap(stones);
10  let numStones = stones.length;
11  while (numStones > 0) {
12    const left = 1;
13    const right = 2;
14    let xIdx = stones[left] > stones[right] ? left : right;
15    if (right >= stones.length) xIdx = left;
16
17    const y = stones[0];
18    const x = stones[xIdx];
19    if (x === y) {
20      stones[0] = 0;
21      stones[xIdx] = 0;
22      numStones -= 2;
23    }
24    if (x !== y) {
25      stones[0] -= stones[xIdx];
26      stones[xIdx] = 0;
27      numStones--;
28    }
29    heapify(stones, xIdx);
30    heapify(stones, 0);
31  }
32  return stones[0];
33};
34
35/**
36 * Build a heap represented by an array.
37 * @param {number[]} nums
38 */
39function buildHeap(nums) {
40  // Total nodes
41  const N = nums.length;
42  // Last Non-leaf node index: (N/2)-1
43  const startIdx = Math.ceil(N / 2) - 1;
44
45  // heapify the nodes in reverse order level by level
46  for (let i = startIdx; i >= 0; i--) {
47    heapify(nums, i);
48  }
49}
50
51/**
52 *
53 * @param {number[]} nums
54 * @param {number} rootIdx The index of the node to heapify
55 */
56function heapify(nums, rootIdx) {
57  let largest = rootIdx;
58  const l = rootIdx * 2 + 1;
59  const r = rootIdx * 2 + 2;
60
61  if (l < nums.length && nums[l] > nums[largest]) {
62    largest = l;
63  }
64
65  if (r < nums.length && nums[r] > nums[largest]) {
66    largest = r;
67  }
68
69  // make the swap
70  if (largest !== rootIdx) {
71    const temp = nums[rootIdx];
72    nums[rootIdx] = nums[largest];
73    nums[largest] = temp;
74
75    heapify(nums, largest);
76  }
77}
78
79console.log(lastStoneWeight([9, 3, 2, 10])); // 0
80console.log(lastStoneWeight([1, 3])); // 2
81console.log(lastStoneWeight([1, 3, 5, 4, 6, 13, 10, 9, 8, 15, 17]));
82console.log(lastStoneWeight([2, 7, 4, 1, 8, 1])); // 1
83console.log(lastStoneWeight([1])); // 1
84

692. Top K Frequent Words

Given an array of strings words and an integer k, return the k most frequent strings.

Return the answer sorted by the frequency from highest to lowest. Sort the words with the same frequency by their lexicographical order.

/**
 * @param {string[]} words
 * @param {number} k
 * @return {string[]}
 */
var topKFrequent = function (words, k) {
  const freq = {};
  words.forEach((word) => {
    if (!freq[word]) freq[word] = 1;
    else freq[word]++;
  });
  const results = Object.entries(freq).sort(
    (a, b) => b[1] - a[1] || a[0].localeCompare(b[0])
  );
  return results.slice(0, k).map((el) => el[0]);
};

console.log(
  topKFrequent(
    ["the", "day", "is", "sunny", "the", "the", "the", "sunny", "is", "is"],
    4
  )
);

console.log(topKFrequent(["i", "love", "leetcode", "i", "love", "coding"], 2));

1/**
2 * @param {string[]} words
3 * @param {number} k
4 * @return {string[]}
5 */
6var topKFrequent = function (words, k) {
7  const freq = {};
8  words.forEach((word) => {
9    if (!freq[word]) freq[word] = 1;
10    else freq[word]++;
11  });
12  const results = Object.entries(freq).sort(
13    (a, b) => b[1] - a[1] || a[0].localeCompare(b[0])
14  );
15  return results.slice(0, k).map((el) => el[0]);
16};
17
18console.log(
19  topKFrequent(
20    ["the", "day", "is", "sunny", "the", "the", "the", "sunny", "is", "is"],
21    4
22  )
23);
24
25console.log(topKFrequent(["i", "love", "leetcode", "i", "love", "coding"], 2));
26

Day 1 Prefix Sum​

1480. Running Sum of 1d Array​

724. Find Pivot Index​

Day 2 String​

205. Isomorphic Strings​

392. Is Subsequence​

Day 3 Linked List​

21. Merge Two Sorted Lists​

206. Reverse Linked List​

Day 4 Linked List​

876. Middle of the Linked List​

142. Linked List Cycle II​

Day 5 Greedy​

121. Best Time to Buy and Sell Stock​

409. Longest Palindrome​

Day 6 Tree​

589. N-ary Tree Preorder Traversal​

102. Binary Tree Level Order Traversal​

Day 7 Binary Search​

704. Binary Search​

278. First Bad Version​

Day 8 Binary Search Tree​

98. Validate Binary Search Tree​

Solution 1​

Solution 2​

235. Lowest Common Ancestor of a Binary Search Tree​

Solution 1​

Solution 2​

Day 9 Graph/BFS/DFS​

733. Flood Fill​

200. Number of Islands​

Solution​

Day 10 Dynamic Programming​

509. Fibonacci Number​

70. Climbing Stairs​

Day 11 Dynamic Programming​

746. Min Cost Climbing Stairs​

62. Unique Paths​

Day 12 Sliding Window/Two Pointer​

438. Find All Anagrams in a String​

424. Longest Repeating Character Replacement​

Day 13 Hashmap​

299. Bulls and Cows​

Day 14 Stack​

394. Decode String​

Day 15 Heap​

1046. Last Stone Weight​

692. Top K Frequent Words​

Day 1 Prefix Sum

1480. Running Sum of 1d Array

724. Find Pivot Index

Day 2 String

205. Isomorphic Strings

392. Is Subsequence

Day 3 Linked List

21. Merge Two Sorted Lists

206. Reverse Linked List

Day 4 Linked List

876. Middle of the Linked List

142. Linked List Cycle II

Day 5 Greedy

121. Best Time to Buy and Sell Stock

409. Longest Palindrome

Day 6 Tree

589. N-ary Tree Preorder Traversal

102. Binary Tree Level Order Traversal

Day 7 Binary Search

704. Binary Search

278. First Bad Version

Day 8 Binary Search Tree

98. Validate Binary Search Tree

Solution 1

Solution 2

235. Lowest Common Ancestor of a Binary Search Tree

Solution 1

Solution 2

Day 9 Graph/BFS/DFS

733. Flood Fill

200. Number of Islands

Solution

Day 10 Dynamic Programming

509. Fibonacci Number

70. Climbing Stairs

Day 11 Dynamic Programming

746. Min Cost Climbing Stairs

62. Unique Paths

Day 12 Sliding Window/Two Pointer

438. Find All Anagrams in a String

424. Longest Repeating Character Replacement

Day 13 Hashmap

299. Bulls and Cows

Day 14 Stack

394. Decode String

Day 15 Heap

1046. Last Stone Weight

692. Top K Frequent Words