LeetCode Weekly Contest 369 Summary

Posted on In ,

Overview

LeetCode Weekly Contest 369

This article is a summary of the contest. I don't plan to discuss each problem in detail, but will provide general ideas. The point of this article is self-reflection and improvement.

After reviewing the contest, it is not so difficult. Here is a brief description of my performance on each problem:

  • Problem 1: Simple simulation problem, an easy one.
  • Problem 2: Not difficult, but requires consideration of multiple cases. Unfortunately, I didn't think thoroughly, resulting in 3 WA 😒.
  • Problem 3: a Medium-level DP problem. Initially struggled to come up with a solution, wasted time on the unsolved problem 4, but eventually solved it quickly 😋.
  • Problem 4: Despite being a hard-level problem and not solved during the contest, the code only exceeded time limits. After the contest, I figured out an optimization method by myself. Note that the messy logic during coding led to 2 WA 😒.

I. Find the K-or of an Array

Problem Description:

You are given a 0-indexed integer array nums, and an integer k.

The K-or of nums is a non-negative integer that satisfies the following:

  • The ith bit is set in the K-or if and only if there are at least k elements of nums in which bit i is set.

Return the K-or of nums.

Note that a bit i is set in x if (2i AND x) == 2i, where AND is the bitwise AND operator.

Example 1:

1
2
3
4
5
6
7
Input: nums = [7,12,9,8,9,15], k = 4
Output: 9
Explanation: Bit 0 is set at nums[0], nums[2], nums[4], and nums[5].
Bit 1 is set at nums[0], and nums[5].
Bit 2 is set at nums[0], nums[1], and nums[5].
Bit 3 is set at nums[1], nums[2], nums[3], nums[4], and nums[5].
Only bits 0 and 3 are set in at least k elements of the array, and bits i >= 4 are not set in any of the array's elements. Hence, the answer is 2^0 + 2^3 = 9.

Example 2:

1
2
3
Input: nums = [2,12,1,11,4,5], k = 6
Output: 0
Explanation: Since k == 6 == nums.length, the 6-or of the array is equal to the bitwise AND of all its elements. Hence, the answer is 2 AND 12 AND 1 AND 11 AND 4 AND 5 = 0.

Example 3:

1
2
3
Input: nums = [10,8,5,9,11,6,8], k = 1
Output: 15
Explanation: Since k == 1, the 1-or of the array is equal to the bitwise OR of all its elements. Hence, the answer is 10 OR 8 OR 5 OR 9 OR 11 OR 6 OR 8 = 15.

Constraints:

  • 1 <= nums.length <= 50
  • 0 <= nums[i] < 231
  • 1 <= k <= nums.length

The problem description is a bit hard to understand. Combining it with examples during the contest was necessary for quick understanding.

Bitwise simulation:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int findKOr(int[] nums, int k) {
        int ans = 0;
        for (int i = 0; i < 32; i++) {
            int count = 0;
            int val = 1 << i;
            for (int num : nums) {
                if ((num & val) > 0) count++;
            }
            if (count >= k)  {
                ans |= val;
            }
        }
        return ans;
    }
}

Time complexity: $O(n)$

II. Minimum Equal Sum of Two Arrays After Replacing Zeros

Problem Description:

You are given two arrays nums1 and nums2 consisting of positive integers.

You have to replace all the 0's in both arrays with strictly positive integers such that the sum of elements of both arrays becomes equal.

Return the minimum equal sum you can obtain, or -1 if it is impossible.

Example 1:

1
2
3
4
5
6
Input: nums1 = [3,2,0,1,0], nums2 = [6,5,0]
Output: 12
Explanation: We can replace 0's in the following way:
- Replace the two 0's in nums1 with the values 2 and 4. The resulting array is nums1 = [3,2,2,1,4].
- Replace the 0 in nums2 with the value 1. The resulting array is nums2 = [6,5,1].
Both arrays have an equal sum of 12. It can be shown that it is the minimum sum we can obtain.

Example 2:

1
2
3
Input: nums1 = [2,0,2,0], nums2 = [1,4]
Output: -1
Explanation: It is impossible to make the sum of both arrays equal.

Constraints:

  • 1 <= nums1.length, nums2.length <= 105
  • 0 <= nums1[i], nums2[i] <= 106
  • If there are k zeros in nums1, its sum must increase by at least k after replacement.
  • If nums1 has at least one zero, its sum after replacement can be any value greater than sum(nums1).
  • Similar for nums2.

Return type of the function is long. Array length is at most $10^5$, elements are at most $10^6$, and the sum is at most $10^{11}$, exceeding the limit of a 32-bit integer, which reminds us that all the intermediate results should be stored in long type. In fact, it is a common practice to replace int with long in coding contests to avoid integer overflow.

The key is to identify conditions where equality does not hold. A mistake in this aspect led to three WA:

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
import java.util.Arrays;

class Solution {
    public long minSum(int[] nums1, int[] nums2) {
        long sum1 = Arrays.stream(nums1).mapToLong(i -> i).sum();
        long sum2 = Arrays.stream(nums2).mapToLong(i -> i).sum();
        long c1 = Arrays.stream(nums1).filter(i -> i == 0).count();
        long c2 = Arrays.stream(nums2).filter(i -> i == 0).count();

        if (sum1 > sum2) {
            // sum2 can not increase
            if (c2 == 0) return -1;
            // sum1 can not increase, sum2 has c2 zeros, so sum2 will increase by at least c2
            if (c1 == 0 && c2 + sum2 > sum1) return -1;
        } else if (sum1 == sum2) {
            // one of sum1 or sum2 must increase, while the other one will not change
            if (c1 == 0 && c2 != 0) return -1;
            if (c1 != 0 && c2 == 0) return -1;
        } else {
            // same logic to the case where sum1 > sum2
            if (c1 == 0) return -1;
            if (c2 == 0 && c1 + sum1 > sum2) return -1;
        }
        return Math.max(sum1 + c1, sum2 + c2);
    }
}

III. Minimum Increment Operations to Make Array Beautiful

Problem Description:

You are given a 0-indexed integer array nums having length n, and an integer k.

You can perform the following increment operation any number of times (including zero):

  • Choose an index i in the range [0, n - 1], and increase nums[i] by 1.

An array is considered beautiful if, for any subarray with a size of 3 or more, its maximum element is greater than or equal to k.

Return an integer denoting the minimum number of increment operations needed to make nums beautiful.

A subarray is a contiguous non-empty sequence of elements within an array.

Example 1:

1
2
3
4
5
6
7
8
9
10
Input: nums = [2,3,0,0,2], k = 4
Output: 3
Explanation: We can perform the following increment operations to make nums beautiful:
Choose index i = 1 and increase nums[1] by 1 -> [2,4,0,0,2].
Choose index i = 4 and increase nums[4] by 1 -> [2,4,0,0,3].
Choose index i = 4 and increase nums[4] by 1 -> [2,4,0,0,4].
The subarrays with a size of 3 or more are: [2,4,0], [4,0,0], [0,0,4], [2,4,0,0], [4,0,0,4], [2,4,0,0,4].
In all the subarrays, the maximum element is equal to k = 4, so nums is now beautiful.
It can be shown that nums cannot be made beautiful with fewer than 3 increment operations.
Hence, the answer is 3.

Example 2:

1
2
3
4
5
6
7
8
9
Input: nums = [0,1,3,3], k = 5
Output: 2
Explanation: We can perform the following increment operations to make nums beautiful:
Choose index i = 2 and increase nums[2] by 1 -> [0,1,4,3].
Choose index i = 2 and increase nums[2] by 1 -> [0,1,5,3].
The subarrays with a size of 3 or more are: [0,1,5], [1,5,3], [0,1,5,3].
In all the subarrays, the maximum element is equal to k = 5, so nums is now beautiful.
It can be shown that nums cannot be made beautiful with fewer than 2 increment operations.
Hence, the answer is 2.

Example 3:

1
2
3
4
5
Input: nums = [1,1,2], k = 1
Output: 0
Explanation: The only subarray with a size of 3 or more in this example is [1,1,2].
The maximum element, 2, is already greater than k = 1, so we don't need any increment operation.
Hence, the answer is 0.

Constraints:

  • 3 <= n == nums.length <= 105
  • 0 <= nums[i] <= 109
  • 0 <= k <= 109

An array is considered beautiful if, for any subarray with a size of 3 or more, its maximum element is greater than or equal to k.

This condition is equivalent to having every subarray of length 3 with a maximum element $\ge k$.

Obviously, we should try to ensure that in every three consecutive elements, at least one element is $\ge k$. However, it is unclear which elements should be increased to $k$. To address this, let's use DP.

1️⃣DP definition: dp[i]: the minimum increment operations to make nums[0:i] a beautiful array and nums[i] $\ge k$. — Here are three bold points.

If nums[i] $\ge k$, then nums[i - 2 : i] forms a subarray of length 3 that can be covered, satisfying the condition for being a beautiful array. This coverage simultaneously indicates that we need to ensure nums[0:(i-3)] is also a beautiful array to make nums[0:i] a beautiful array. Results from dp[i - 3], dp[i - 2], and dp[i - 1] all satisfy this requirement; thus, we take the minimum value in them:

2️⃣Recurrence relation: $dp[i] = \max\set{0,k-nums[i]} + \min\set{dp[i - 1], dp[i - 2], dp[i - 3]}$

3️⃣Answer: Choose the minimum value among dp[n - 3], dp[n - 2], and dp[n - 1], all of which can guarantee nums being a beautiful array by DP definition.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import java.util.Arrays;

class Solution {
    public long minIncrementOperations(int[] nums, int k) {
        int n = nums.length;
        long[] dp = new long[n];
        // base case
        Arrays.fill(dp, Long.MAX_VALUE);
        // n >= 3 guarantees that we do not need to check whether dp[0], dp[1] or dp[2] exists
        dp[0] = Math.max(0, k - nums[0]);
        dp[1] = Math.max(0, k - nums[1]);
        dp[2] = Math.max(0, k - nums[2]);
        // recursively
        for (int i = 3; i < n; i++) {
            long v = Math.max(0, k - nums[i]);
            dp[i] = Math.min(dp[i], dp[i - 1] + v);
            dp[i] = Math.min(dp[i], dp[i - 2] + v);
            dp[i] = Math.min(dp[i], dp[i - 3] + v);
        }
        // answer
        return Math.min(dp[n - 1], Math.min(dp[n - 2], dp[n - 3]));
    }
}

IV. Maximum Points After Collecting Coins From All Nodes

Problem Description:

There exists an undirected tree rooted at node 0 with n nodes labeled from 0 to n - 1. You are given a 2D integer array edges of length n - 1, where edges[i] = [ai, bi] indicates that there is an edge between nodes ai and bi in the tree. You are also given a 0-indexed array coins of size n where coins[i] indicates the number of coins in the vertex i, and an integer k.

Starting from the root, you have to collect all the coins such that the coins at a node can only be collected if the coins of its ancestors have been already collected.

Coins at nodei can be collected in one of the following ways:

  • Collect all the coins, but you will get coins[i] - k points. If coins[i] - k is negative then you will lose abs(coins[i] - k) points.
  • Collect all the coins, but you will get floor(coins[i] / 2) points. If this way is used, then for all the nodej present in the subtree of nodei, coins[j] will get reduced to floor(coins[j] / 2).

Return the maximum points you can get after collecting the coins from all the tree nodes.

Example 1:

img

1
2
3
4
5
6
7
8
Input: edges = [[0,1],[1,2],[2,3]], coins = [10,10,3,3], k = 5
Output: 11                        
Explanation: 
Collect all the coins from node 0 using the first way. Total points = 10 - 5 = 5.
Collect all the coins from node 1 using the first way. Total points = 5 + (10 - 5) = 10.
Collect all the coins from node 2 using the second way so coins left at node 3 will be floor(3 / 2) = 1. Total points = 10 + floor(3 / 2) = 11.
Collect all the coins from node 3 using the second way. Total points = 11 + floor(1 / 2) = 11.
It can be shown that the maximum points we can get after collecting coins from all the nodes is 11.

Example 2:

img

1
2
3
4
Input: edges = [[0,1],[0,2]], coins = [8,4,4], k = 0
Output: 16
Explanation: 
Coins will be collected from all the nodes using the first way. Therefore, total points = (8 - 0) + (4 - 0) + (4 - 0) = 16.

Constraints:

  • n == coins.length
  • 2 <= n <= 105
  • 0 <= coins[i] <= 104
  • edges.length == n - 1
  • 0 <= edges[i][0], edges[i][1] < n
  • 0 <= k <= 104

1️⃣Build the tree. It's essentially building a graph, and we need to perform DFS starting from node 0 to simulate tree traversal.

2️⃣There are two ways to collect coins (the problem is intentionally written in complicated words, requiring simplification):

  • Option 1: Currently-collected coins plus coins[i] - k (regardless of sign).
  • Option 2: floor(coins[i] / 2) is essentially integer division, we should optimize the division using bitwise operation i.e., coins[i] >> 1. Bitwise operation also has the advantage that if the current node has $k$ ancestors choosing Option 2, then the coin count for that node is coins[i] >> k, avoiding the time cost of computing $2^k$ and division by $2^k$.

Based on these two options, we can write a recursive function for pre-order traversal:

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
/**
 * Pre-order traversal, collecting coins
 * @param root Root node of the subtree
 * @param half Number of times ancestors of the subtree chose Option 2
 * @return Maximum coins that can be collected in the subtree
 */
private long recur(Node root, long half) {
    if (root == null) return 0;
    // Node is a graph node, visited is used for traversal
    // Pre-order traversal is essentially DFS
    visited[root.index] = true;
    // Option 1
    long res1 = (root.val >> half) - k;
    for (Node child : root.children) {
        if (visited[child.index]) continue;
        res1 += recur(child, half);
    }

    // Option 2
    long res2 = (root.val >> (1 + half));
    for (Node child : root.children) {
        if (visited[child.index]) continue;
        res2 += recur(child, half + 1);
    }

    visited[root.index] = false;
    return Math.max(res1, res2);
}

Up to this point, I had written the code during the contest but still encountered a timeout. Later, I came up with the following optimization ideas:

3️⃣ $\forall i, coins[i] \le 10^4$, and $\log_2(10^4) \approx 13.8$. Thus, as long as the ancestors of the current subtree have chosen Option 2 at least 14 times, the coin count for all nodes in this subtree will continuously halve to 0.

This is basically a pruning technique, and we check it at the beginning of the recur function:

1
if (half >= 14) return 0;

4️⃣Speaking of recursion, we think about divide and conquer paradigms, which then lead to thoughts about DP paradigms. What is the difference between the two? — DP reuses results of subproblems, making it more efficient.

Although the process of traversing the tree cannot be written as an iteration, we can use a map to cache results of subproblems: the key is (nodes[i], half), and the value is the number of collected coins.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
private final HashMap<Node, HashMap<Long, Long>> dpMap = new HashMap<>();

private long recur(Node root, long half) {
    if (root == null) return 0;
    // Check cache, return directly if found
    HashMap<Long, Long> mp = dpMap.get(root);
    if (mp != null) {
        Long ans = mp.get(half);
        if (ans != null) return ans;
    }
    
    // Option 1 and Option 2 code...
    
    // Insert into cache
    long ans = Math.max(res1, res2);
    dpMap.putIfAbsent(root, new HashMap<>());
    dpMap.get(root).put(half, ans);
    
    return ans;
}

With these two optimization steps, the code successfully passed:

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
72
73
74
75
76
77
78
79
80
81
82
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.stream.IntStream;

class Solution {
    private static class Node {
        List<Node> children = new ArrayList<>();
        int val;
        int index;

        public Node(int val, int index) {
            this.val = val;
            this.index = index;
        }
    }

    private int k;
    private boolean[] visited;

    public int maximumPoints(int[][] edges, int[] coins, int k) {
        this.k = k;
        int n = coins.length;
        visited = new boolean[n];
        Node[] nodes = IntStream.range(0, n).mapToObj(i -> new Node(coins[i], i)).toArray(Node[]::new);
        for (int[] e : edges) {
            nodes[e[0]].children.add(nodes[e[1]]);
            nodes[e[1]].children.add(nodes[e[0]]);
        }
        return (int) recur(nodes[0], 0);
    }


    /**
     * Recursive result cache, elevates divide and conquer algorithm to DP algorithm for efficiency
     * <node, <half, result>>
     */
    private final HashMap<Node, HashMap<Long, Long>> dpMap = new HashMap<>();

    /**
     * Pre-order traversal, collecting coins
     *
     * @param root Root node of the subtree
     * @param half Number of times ancestors of the subtree chose Option 2
     * @return Maximum coins that can be collected in the subtree
     */
    private long recur(Node root, long half) {
        // coins[i] <= 10^4 -> log_2 (10^4) < 14
        if (half >= 14) return 0;
        if (root == null) return 0;
        // Check cache, return directly if found
        HashMap<Long, Long> mp = dpMap.get(root);
        if (mp != null) {
            Long ans = mp.get(half);
            if (ans != null) return ans;
        }
        // Node is a graph node, visited is used for traversal
        // Pre-order traversal is essentially DFS
        visited[root.index] = true;
        // Option 1
        long res1 = (root.val >> half) - k;
        for (Node child : root.children) {
            if (visited[child.index]) continue;
            res1 += recur(child, half);
        }

        // Option 2
        long res2 = (root.val >> (1 + half));
        for (Node child : root.children) {
            if (visited[child.index]) continue;
            res2 += recur(child, half + 1);
        }
        
        visited[root.index] = false;
        // Insert into cache
        long ans = Math.max(res1, res2);
        dpMap.putIfAbsent(root, new HashMap<>());
        dpMap.get(root).put(half, ans);

        return ans;
    }
}