April LeetCoding Challenge 2021

Posted on | In

It’s been a year since doing LeetCoding challenge. Time flies. Coding in Go for 9 months and coding in JS for the last 3 months. I feel more confident coding in these two languages now, but I feel I still need to improve my algorithm skills. It’s more busy this year, sometimes I didn’t think deeply about each coding problems. Hope things go well this year and need to continue reading books like last year.

Week 1: April 1st - April 7th

Largest Unique Number

Given an array of integers A, return the largest integer that only occurs once.

If no integer occurs once, return -1.

Example 1:

1
2
3
4
Input: [5,7,3,9,4,9,8,3,1]
Output: 8
Explanation:
The maximum integer in the array is 9 but it is repeated. The number 8 occurs only once, so it's the answer.

Example 2:

1
2
3
4
Input: [9,9,8,8]
Output: -1
Explanation:
There is no number that occurs only once.

Note:

  1. 1 <= A.length <= 2000

  2. 0 <= A[i] <= 1000

Hint 1:

Find the number of occurrences of each value.

Hint 2:

Use an array or a hash table to do that.

Hint 3:

Look for the largest value with number of occurrences = 1.

Explanation

  1. We can use brute force to solve this problem. First sort the array. Then loop from the largest number to smallest number. If the large number A[i] is not equal to its previous number A[i-1], then we return this large number A[i]. While A[i] == A[i-1], we keep decreasing i. Outside the loop, we return -1.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int largestUniqueNumber(int[] A) {
        Arrays.sort(A);

        for (int i = A.length - 1; i >= 0; i--) {
            if (i == 0 || A[i] != A[i-1]) return A[i];

            while (i > 0 && A[i] == A[i-1]) i -= 1;
        }

        return -1;
    }
}

Palindrome Linked List

Given the head of a singly linked list, return true if it is a palindrome.

Example 1:

Palindrome Linked List

1
2
Input: head = [1,2,2,1]
Output: true

Example 2:

Palindrome Linked List

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

Constraints:

  • The number of nodes in the list is in the range [1, 10^5].

  • 0 <= Node.val <= 9

Follow up: Could you do it in O(n) time and O(1) space?

Explanation 1

  1. We can use two pointers technique to get to the middle element of the linked list. We also need a stack to store every slow pointer’s iterated value.

  2. Then start from the next element of the middle node, we can compare its value with stack’s pop node value. Note, if there are odd number nodes (fast.next ==null) in the linked list, we will pop one node first, then start to compare. If they are not equal, then we return false as the result until we finish moving the slow poitners to the end.

Solution 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/**
 * 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 {boolean}
 */
var isPalindrome = function (head) {
  if (!head.next) return true;
  let slow = head,
    fast = head;
  const st = [slow.val];

  while (fast.next && fast.next.next) {
    slow = slow.next;
    fast = fast.next.next;
    st.push(slow.val);
  }
  if (!fast.next) st.pop();

  slow = slow.next;
  while (st.length > 0 && st[st.length - 1] === slow.val) {
    st.pop();
    slow = slow.next;
  }

  return st.length === 0;
};

Explanation 2

  1. After we find the middle node, we can reverse the second half list, in other words, all the nodes from slow.next to the end of the list. Then, we can iterate and compare the first half’s node with the second half’s node. If there’s one node different, we return false. After iteration, we return true as the result.

Solution 2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
/**
 * 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 {boolean}
 */
var isPalindrome = function (head) {
  if (!head.next) return true;
  let slow = head,
    fast = head;

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

  let last = slow.next;
  while (last.next) {
    const temp = last.next;
    last.next = temp.next;
    temp.next = slow.next;
    slow.next = temp;
  }

  slow = slow.next;
  let pre = head;
  while (slow) {
    if (pre.val != slow.val) return false;
    pre = pre.next;
    slow = slow.next;
  }

  return true;
};

Ones and Zeroes

You are given an array of binary strings strs and two integers m and n.

Return the size of the largest subset of strs such that there are at most m 0’s and n 1’s in the subset.

A set x is a subset of a set y if all elements of x are also elements of y.

Example 1:

1
2
3
4
5
Input: strs = ["10","0001","111001","1","0"], m = 5, n = 3
Output: 4
Explanation: The largest subset with at most 5 0's and 3 1's is {"10", "0001", "1", "0"}, so the answer is 4.
Other valid but smaller subsets include {"0001", "1"} and {"10", "1", "0"}.
{"111001"} is an invalid subset because it contains 4 1's, greater than the maximum of 3.

Example 2:

1
2
3
Input: strs = ["10","0","1"], m = 1, n = 1
Output: 2
Explanation: The largest subset is {"0", "1"}, so the answer is 2.

Constraints:

  • 1 <= strs.length <= 600

  • 1 <= strs[i].length <= 100

  • strs[i] consists only of digits '0' and '1'.

  • 1 <= m, n <= 100

Explanation

  1. This is a knapsack problem. We can use dynamic programming to solve this problem.

  2. Dynamic state. We create a two dimensional array dp[i][j] which represents if we have i zeros and j ones, the maximum number of strings we can form.

  3. Dynamic init. All dp[i][j] are zeros.

  4. Dynamic function. We can either choose this string or not choose this string. If we choose the current string, then we have dp[i][j] = dp[i-zeros][j-ones] + 1. zeros means the number of 0s the current string has, ones means the number of 1s the current string has. If we don’t choose the current string, then dp[i][j] unchanged. Therefore, the dynamic function is dp[i][j] = max(dp[i][j], dp[i-zeros][j-ones]+1). Also, we need to loop from the bottom right to the top left. For the same string, if we loop from top left to bottom right, then we already calculated dp[i-zeros][j-ones], let say dp[i-zeros][j-ones]=1; now when the iteration is dp[i-zeros][j-ones]+1=1+1=2, which adding the extra previous result, in this case dp[i-zeros][j-ones] and it’s wrong. Instead, it should be dp[i-zeros][j-ones] + 1 = 0 + 1 = 1.

  5. Dynamic result is dp[m][n] when we have all m zeros and n ones, the maximum string we can form.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
 * @param {string[]} strs
 * @param {number} m
 * @param {number} n
 * @return {number}
 */
var findMaxForm = function(strs, m, n) {
    const dp = Array(m+1).fill(0).map(_ => Array(n+1).fill(0));
    for (const str of strs) {
        let zeros = 0;
        let ones = 0;
        for (const ch of str) {
            if (ch === '0') {
                zeros += 1;
            } else {
                ones += 1;
            }
        }

        for (let i = m; i >= zeros; i--) {
            for (let j = n; j >= ones; j--) {
                dp[i][j] = Math.max(dp[i][j], dp[i-zeros][j-ones] + 1);
            }
        }
    }

    return dp[m][n];
};

Longest Valid Parentheses

Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.

Example 1:

1
2
3
Input: s = "(()"
Output: 2
Explanation: The longest valid parentheses substring is "()".

Example 2:

1
2
3
Input: s = ")()())"
Output: 4
Explanation: The longest valid parentheses substring is "()()".

Example 3:

1
2
Input: s = ""
Output: 0

Constraints:

  • 0 <= s.length <= 3 * 10^4

  • s[i] is '(', or ')'.

Explanation

  1. We can loop through the string character by character. If the character is (, we push its index to the stack. Else if the character is ), we pop an element of the stack then the length will be the current index subtract the top element of the stack. If after we pop an element of the stack, the stack become empty, then the length will be the current index subtract the leftmost element. If Before we pop an element of the stack, the stack is empty, then we set the leftmost element to the current index.
1
2
3
4
5
6
7
8
9
10
11
12
  Example: s = ( ( ) ( ) ) ( ) )
  char      idx      leftmost      stack      pop      max
                      -1            E                  0
  (         0          -1            0                  0
  (         1          -1            01                 0
  )         2          -1            0         1       2-0
  (         3          -1            03                 2
  )         4          -1            0         3       4-0
  )         5          -1            E         0       5-(-1)
  (         6          -1            6                  6
  )         7          -1            E         6       7-(-1)
  )         8           8            E                  8

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/**
 * @param {string} s
 * @return {number}
 */
var longestValidParentheses = function(s) {
    if (s.length < 2) return 0;
    let res = 0;
    const st = [];
    let leftMost = -1;


    for (let i = 0; i < s.length; i++) {
        const ch = s[i];
        if (ch === '(') {
            st.push(i);
        } else {
            if (st.length === 0) {
                leftMost = i;
            } else {
                st.pop();
                if (st.length === 0) {
                    res = Math.max(res, i - leftMost);
                } else {
                    res = Math.max(res, i - st[st.length-1]);
                }
            }
        }
    }

    return res;
};

Design Circular Queue

Design your implementation of the circular queue. The circular queue is a linear data structure in which the operations are performed based on FIFO (First In First Out) principle and the last position is connected back to the first position to make a circle. It is also called “Ring Buffer”.

One of the benefits of the circular queue is that we can make use of the spaces in front of the queue. In a normal queue, once the queue becomes full, we cannot insert the next element even if there is a space in front of the queue. But using the circular queue, we can use the space to store new values.

Implementation the MyCircularQueue class:

  • MyCircularQueue(k) Initializes the object with the size of the queue to be k.

  • int Front() Gets the front item from the queue. If the queue is empty, return -1.

  • int Rear() Gets the last item from the queue. If the queue is empty, return -1.

  • boolean enQueue(int value) Inserts an element into the circular queue. Return true if the operation is successful.

  • boolean deQueue() Deletes an element from the circular queue. Return true if the operation is successful.

  • boolean isEmpty() Checks whether the circular queue is empty or not.

  • boolean isFull() Checks whether the circular queue is full or not.

Example 1:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
Input
["MyCircularQueue", "enQueue", "enQueue", "enQueue", "enQueue", "Rear", "isFull", "deQueue", "enQueue", "Rear"]
[[3], [1], [2], [3], [4], [], [], [], [4], []]
Output
[null, true, true, true, false, 3, true, true, true, 4]

Explanation
MyCircularQueue myCircularQueue = new MyCircularQueue(3);
myCircularQueue.enQueue(1); // return True
myCircularQueue.enQueue(2); // return True
myCircularQueue.enQueue(3); // return True
myCircularQueue.enQueue(4); // return False
myCircularQueue.Rear();     // return 3
myCircularQueue.isFull();   // return True
myCircularQueue.deQueue();  // return True
myCircularQueue.enQueue(4); // return True
myCircularQueue.Rear();     // return 4

Constraints:

  • 1 <= k <= 1000

  • 0 <= value <= 1000

  • At most 3000 calls will be made to enQueue, deQueue, Front, Rear, isEmpty, and isFull.

Follow up: Could you solve the problem without using the built-in queue?

Explanation

  1. For circular queue or array question, after insert an element, the next pointer will always be (i + 1) % size. For this problem, we use two pointers beforeHead and nextTail. Also, we use size to record the maximum size we can have, cnt to count how many elements are in the queue, and data[] to store the elements.

  2. We can sovle the easy method first. isEmpty and isFull can be solved using cnt == 0 and cnt == size.

  3. For method Front(), we first check if isEmpty, if not empty, then we return data[beforeHead + 1], but we need to module size, so return data[(beforeHead + 1) % size].

  4. For method Rear(), we first check if isEmpty, if not empty, then we return data[nextTail - 1], but we need to module size and avoid negative number, so we return data[(nextTail - 1 + size) % size].

  5. For method enQueue, we first check if isFull, if not full, then we can insert the element into index nextTail, then increase nextTail by (nextTail + 1) % size. Also remember to increase cnt.

  6. For method deQueue, we first check if isEmpty, if not empty, then we can just increase beforeHead by (beforeHead + 1) % size. Also remember to decrease cnt.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
/**
 * @param {number} k
 */
var MyCircularQueue = function(k) {
    this.size = k;
    this.beforeHead = k - 1;
    this.nextTail = 0;
    this.cnt = 0;
    this.data = [];
};

/**
 * @param {number} value
 * @return {boolean}
 */
MyCircularQueue.prototype.enQueue = function(value) {
    if (this.isFull()) return false;
    this.data[this.nextTail] = value;
    this.nextTail = (this.nextTail + 1) % this.size;
    this.cnt += 1;
    return true;
};

/**
 * @return {boolean}
 */
MyCircularQueue.prototype.deQueue = function() {
    if (this.isEmpty()) return false;
    this.beforeHead = (this.beforeHead + 1) % this.size;
    this.cnt -= 1;
    return true;
};

/**
 * @return {number}
 */
MyCircularQueue.prototype.Front = function() {
    return this.isEmpty() ? -1 : this.data[(this.beforeHead + 1) % this.size];
};

/**
 * @return {number}
 */
MyCircularQueue.prototype.Rear = function() {
    return this.isEmpty() ? -1 : this.data[(this.nextTail - 1 + this.size) % this.size];
};

/**
 * @return {boolean}
 */
MyCircularQueue.prototype.isEmpty = function() {
    return this.cnt === 0;
};

/**
 * @return {boolean}
 */
MyCircularQueue.prototype.isFull = function() {
    return this.cnt === this.size;
};

/**
 * Your MyCircularQueue object will be instantiated and called as such:
 * var obj = new MyCircularQueue(k)
 * var param_1 = obj.enQueue(value)
 * var param_2 = obj.deQueue()
 * var param_3 = obj.Front()
 * var param_4 = obj.Rear()
 * var param_5 = obj.isEmpty()
 * var param_6 = obj.isFull()
 */

Global and Local Inversions

We have some permutation A of [0, 1, ..., N - 1], where N is the length of A.

The number of (global) inversions is the number of i < j with 0 <= i < j < N and A[i] > A[j].

The number of local inversions is the number of i with 0 <= i < N and A[i] > A[i+1].

Return true if and only if the number of global inversions is equal to the number of local inversions.

Example 1:

1
2
3
Input: A = [1,0,2]
Output: true
Explanation: There is 1 global inversion, and 1 local inversion.

Example 2:

1
2
3
Input: A = [1,2,0]
Output: false
Explanation: There are 2 global inversions, and 1 local inversion.

Note:

  • A will be a permutation of [0, 1, ..., A.length - 1].

  • A will have length in range [1, 5000].

  • The time limit for this problem has been reduced.

Hint 1:

Where can the 0 be placed in an ideal permutation? What about the 1?

Explanation

  1. Local inversion is also global inversion. If we find any global version that is A[i] > A[j] where i + 2 <= j, then we return false.

  2. Global inversion A[j] compares with A[j - 2], A[j - 3], A[j - 4], we can take the maximum of A[j - 2], A[j - 3], A[j - 4] as curMax and compares with A[j]. In other words, max(curMax, A[i]) and compare with A[j].

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/**
 * @param {number[]} A
 * @return {boolean}
 */
var isIdealPermutation = function(A) {
    let curMax = 0;

    for (let i = 0; i < A.length - 2; i++) {
        curMax = Math.max(curMax, A[i]);
        if (curMax > A[i + 2]) return false;
    }

    return true;
};

Minimum Operations to Make Array Equal

You have an array arr of length n where arr[i] = (2 * i) + 1 for all valid values of i (i.e. 0 <= i < n).

In one operation, you can select two indices x and y where 0 <= x, y < n and subtract 1 from arr[x] and add 1 to arr[y] (i.e. perform arr[x] -=1 and arr[y] += 1). The goal is to make all the elements of the array equal. It is guaranteed that all the elements of the array can be made equal using some operations.

Given an integer n, the length of the array. Return the minimum number of operations needed to make all the elements of arr equal.

Example 1:

1
2
3
4
5
Input: n = 3
Output: 2
Explanation: arr = [1, 3, 5]
First operation choose x = 2 and y = 0, this leads arr to be [2, 3, 4]
In the second operation choose x = 2 and y = 0 again, thus arr = [3, 3, 3].

Example 2:

1
2
Input: n = 6
Output: 9

Constraints:

  • 1 <= n <= 10^4

Hint 1:

Build the array arr using the given formula, define target = sum(arr) / n

Hint 2:

What is the number of operations needed to convert arr so that all elements equal target ?

Explanation

  1. If n is odd, for example n = 5, we have [1, 3, 5, 7, 9]. The average number is 5. We need to subtract 2 from 7 and add 2 to 3, we also need to subtract 4 from 9 and add 4 to 1. Total steps is 2 + 4 = 6.

  2. If n is even, for example n = 4, we have [1, 3, 5, 7]. The average number is 4. We need to subtract 1 from 5 and add 1 to 3, we also need to subtract 3 from 7 and add 3 to 1. Total step is 1 + 3 = 4.

  3. Let cnt = n / 2. If n is odd, the result is the first half even number, so res = cnt * (cnt + 1). If n is even, the result is the first half odd number, so res = cnt * cnt.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
/**
 * @param {number} n
 * @return {number}
 */
var minOperations = function(n) {
    if (n % 2) {
        const cnt = (n - 1) / 2;
        return cnt * (cnt + 1);
    } else {
        const cnt = n / 2;
        return cnt * cnt;
    }
};

Determine if String Halves Are Alike

You are given a string s of even length. Split this string into two halves of equal lengths, and let a be the first half and b be the second half.

Two strings are alike if they have the same number of vowels ('a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'). Notice that s contains uppercase and lowercase letters.

Return true if a and b are alike. Otherwise, return false.

Example 1:

1
2
3
Input: s = "book"
Output: true
Explanation: a = "bo" and b = "ok". a has 1 vowel and b has 1 vowel. Therefore, they are alike.

Example 2:

1
2
3
4
Input: s = "textbook"
Output: false
Explanation: a = "text" and b = "book". a has 1 vowel whereas b has 2. Therefore, they are not alike.
Notice that the vowel o is counted twice.

Example 3:

1
2
Input: s = "MerryChristmas"
Output: false

Example 4:

1
2
Input: s = "AbCdEfGh"
Output: true

Constraints:

  • 2 <= s.length <= 1000

  • s.length is even.

  • s consists of uppercase and lowercase letters.

Hint 1:

Create a function that checks if a character is a vowel, either uppercase or lowercase.

Explanation

  1. First create a set of all vowels. Use pointer i to count the first half string’s vowels, and use pointer j to count the second half string’s volwels. Finally, if first half string’s number of vowels equals to second half string’s vowels, return true, else return false.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
/**
 * @param {string} s
 * @return {boolean}
 */
var halvesAreAlike = function(s) {
    const set = new Set(['a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U']);
    let a = 0, b = 0;
    for (let i = 0, j = s.length - 1; i < j; i++, j--) {
        a += set.has(s[i]) ? 1 : 0;
        b += set.has(s[j]) ? 1 : 0;
    }
    return a === b;
};