LeetCode Weekly Contest 370 Summary

Overview

LeetCode Weekly Contest 370

This article is a summary of the weekly contest. I do not plan to discuss each problem in detail; for some problems, I will only provide a rough outline. The point of this article is self-reflection and improvement.

Achieved AC in the first three problems within 23 minutes, resulting in a ranking around 300 - more like a typing contest emphasizing speed rather than a coding contest. Brief description of problem-solving:

• Problem 1: Easy problem but got stuck for 5 minutes 😒;
• Problem 2: Similar to the first one in terms of background, also easy problem, but solved faster 😋;
• Problem 3: A real medium-level problem that required a bit more thought, solved in 15 minutes, not bad 😋;
• Problem 4: Couldn’t solve. If the data range is small, it’s a simple DP problem, but couldn’t find an optimization 😒;

I. Find Champion I

Problem Description:

There are n teams numbered from 0 to n - 1 in a tournament.

Given a 0-indexed 2D boolean matrix grid of size n * n. For all i, j that 0 <= i, j <= n - 1 and i != j team i is stronger than team j if grid[i][j] == 1, otherwise, team j is stronger than team i.

Team a will be the champion of the tournament if there is no team b that is stronger than team a.

Return the team that will be the champion of the tournament.

Example 1:

Input: grid = [[0,1],[0,0]]
Output: 0
Explanation: There are two teams in this tournament.
grid[0][1] == 1 means that team 0 is stronger than team 1. So team 0 will be the champion.

Example 2:

Input: grid = [[0,0,1],[1,0,1],[0,0,0]]
Output: 1
Explanation: There are three teams in this tournament.
grid[1][0] == 1 means that team 1 is stronger than team 0.
grid[1][2] == 1 means that team 1 is stronger than team 2.
So team 1 will be the champion.

Constraints:

• n == grid.length
• n == grid[i].length
• 2 <= n <= 100
• grid[i][j] is either 0 or 1.
• For all i grid[i][i] is 0.
• For all i, j that i != j, grid[i][j] != grid[j][i].
• The input is generated such that if team a is stronger than team b and team b is stronger than team c, then team a is stronger than team c.

‘Team a will be the champion of the tournament if there is no team b that is stronger than team a.’ Use count[i] to represent the number of teams stronger than i. The answer is the i with $count[i] = 0$.

class Solution {
    public int findChampion(int[][] grid) {
        int n = grid.length;
        int[] count = new int[n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i == j) continue;
                if (grid[i][j] == 1) count[j]++;
                else count[i]++;
            }
        }
        for (int i = 0; i < n; i++) {
            if (count[i] == 0) return i;
        }
        return -1;
    }
}

II. Find Champion II

Problem Description:

There are n teams numbered from 0 to n - 1 in a tournament; each team is also a node in a DAG.

You are given the integer n and a 0-indexed 2D integer array edges of length m representing the DAG, where edges[i] = [ui, vi] indicates that there is a directed edge from team ui to team vi in the graph.

A directed edge from a to b in the graph means that team a is stronger than team b and team b is weaker than team a.

Team a will be the champion of the tournament if there is no team b that is stronger than team a.

Return the team that will be the champion of the tournament if there is a unique champion, otherwise, return -1.

Notes

• A cycle is a series of nodes a1, a2, ..., an, an+1 such that node a1 is the same node as node an+1, the nodes a1, a2, ..., an are distinct, and there is a directed edge from the node ai to node ai+1 for every i in the range [1, n].
• A DAG is a directed graph that does not have any cycle.

Example 1:

Input: n = 3, edges = [[0,1],[1,2]]
Output: 0
Explanation: Team 1 is weaker than team 0. Team 2 is weaker than team 1. So the champion is team 0.

Example 2:

Input: n = 4, edges = [[0,2],[1,3],[1,2]]
Output: -1
Explanation: Team 2 is weaker than team 0 and team 1. Team 3 is weaker than team 1. But team 1 and team 0 are not weaker than any other teams. So the answer is -1.

Constraints:

• 1 <= n <= 100
• m == edges.length
• 0 <= m <= n * (n - 1) / 2
• edges[i].length == 2
• 0 <= edge[i][j] <= n - 1
• edges[i][0] != edges[i][1]
• The input is generated such that if team a is stronger than team b, team b is not stronger than team a.
• The input is generated such that if team a is stronger than team b and team b is stronger than team c, then team a is stronger than team c.

Use directed edges to represent who is stronger, making it easier to understand than the first problem. Edge $(a,b)$ means a is stronger than b, so the teams with the strongest members have an in-degree of 0. Count the in-degrees.

import java.util.Arrays;

class Solution {
    public int findChampion(int n, int[][] edges) {
        int[] inDeg = new int[n];
        // Count in-degrees
        Arrays.stream(edges).forEach(e -> inDeg[e[1]]++);

        long count = Arrays.stream(inDeg).filter(i -> i == 0).count();
        // Not unique
        if (count != 1) return -1;

        for (int i = 0; i < n; i++) {
            if (inDeg[i] == 0) return i;
        }
        throw new Error();
    }
}

III. Maximum Score After Applying Operations on a Tree

Problem Description:

There is an undirected tree with n nodes labeled from 0 to n - 1, and rooted at node 0. 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 integer array values of length n, where values[i] is the value associated with the ith node.

You start with a score of 0. In one operation, you can:

• Pick any node i.
• Add values[i] to your score.
• Set values[i] to 0.

A tree is healthy if the sum of values on the path from the root to any leaf node is different than zero.

Return the maximum score you can obtain after performing these operations on the tree any number of times so that it remains healthy.

Example 1:

Input: edges = [[0,1],[0,2],[0,3],[2,4],[4,5]], values = [5,2,5,2,1,1]
Output: 11
Explanation: We can choose nodes 1, 2, 3, 4, and 5. The value of the root is non-zero. Hence, the sum of values on the path from the root to any leaf is different than zero. Therefore, the tree is healthy and the score is values[1] + values[2] + values[3] + values[4] + values[5] = 11.
It can be shown that 11 is the maximum score obtainable after any number of operations on the tree.

Example 2:

Input: edges = [[0,1],[0,2],[1,3],[1,4],[2,5],[2,6]], values = [20,10,9,7,4,3,5]
Output: 40
Explanation: We can choose nodes 0, 2, 3, and 4.
- The sum of values on the path from 0 to 4 is equal to 10.
- The sum of values on the path from 0 to 3 is equal to 10.
- The sum of values on the path from 0 to 5 is equal to 3.
- The sum of values on the path from 0 to 6 is equal to 5.
Therefore, the tree is healthy and the score is values[0] + values[2] + values[3] + values[4] = 40.
It can be shown that 40 is the maximum score obtainable after any number of operations on the tree.

Constraints:

• 2 <= n <= 2 * 104
• edges.length == n - 1
• edges[i].length == 2
• 0 <= ai, bi < n
• values.length == n
• 1 <= values[i] <= 109
• The input is generated such that edges represents a valid tree.

$\forall i, values[i] \ge 1$, and ‘the sum of values on the path from the root to any leaf node is different than zero’. Hence, when performing operations, we must leave one node untouched on each path from the root to a leaf (Multiple paths may share one untouched node).

Let the set of all nodes in the graph be $V$, and the set of nodes left untouched be $U$. The goal is to maximize the score, which is given by $\sum\limits_{v\in V} v - \sum\limits_{u\in U}u$. $\sum\limits_{v\in V} v$ is simply sum(values), so to maximize the score, we want to minimize $\sum\limits_{u\in U}u$. Which nodes should we leave untouched?

For any subtree of the tree, such as the one shown below:

Assume we do not operate on the root node 0, then all the remaining nodes can be modified; assume we operate on the root node 0, then there exist nodes in the remaining nodes that cannot be modified. Whatever the remaining nodes are, i.e. leaf nodes or multiple subtrees, it doesn’t affect this conclusion.

So when should we operate on the root node? Define the minimum sum of unoperated nodes in a healthy subtree rooted at $u$ as $res(u)$. Then, $\forall x, x$ is a child node of $u$, $res(u) = \min\set{values[u], \sum\limits_x res(x)}$

The meaning of this recursive formula is:

• Either do not operate on the root node $u$, in which case the subtree is healthy, and all descendants can be operated on;
• Or operate on the root node $u$, but all subtrees of $u$ must ensure they are healthy;
• By the definition, we need to obtain the minimum sum, so we take the smaller value of the two situations;

For the example above, $res(1) = 2,res(2) = 2,res(3) = 5$

$values[0] = 5 < \sum\limits_{x\in\set{1,2,3}}res(x) = 9$, so we do not operate on the root node 0 but operate on all nodes in its subtrees.

With the recurrence relation for $res(u)$, the value of $\sum\limits_{u\in U}u$ mentioned earlier is $res(0)$, hence the maximum score is sum(values) - res(0).

Code:

import java.util.ArrayList;
import java.util.Arrays;
import java.util.stream.IntStream;

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

        ArrayList<Node> children = new ArrayList<>();
        int val;
        int index;
    }

    public long maximumScoreAfterOperations(int[][] edges, int[] values) {
        int n = values.length;
        // Build the tree, essentially building a graph
        Node[] nodes = IntStream.range(0, n).mapToObj(i -> new Node(values[i], i)).toArray(Node[]::new);
        Arrays.stream(edges).forEach(e -> {
            nodes[e[0]].children.add(nodes[e[1]]);
            nodes[e[1]].children.add(nodes[e[0]]);
        });

        boolean[] visited = new boolean[n];
        visited[0] = true;
        // values[i] <= 10^9，pay attention to mapToLong
        long sum = Arrays.stream(values).mapToLong(i -> i).sum();
        long min = dfs(nodes[0], visited);
        return sum - min;
    }

    /**
     * @param root Root node
     * @return res(root)
     */
    private long dfs(Node root, boolean[] visited) {
        // count # visited neighbors
        int count = 0;
        // min = sum(res(children))
        long min = 0;
        for (Node child : root.children) {
            if (visited[child.index]) {
                count++;
                continue;
            }
            visited[child.index] = true;
            min += dfs(child, visited);
            visited[child.index] = false;
        }
        // this node is a leaf, return its val directly
        if (count == root.children.size()) {
            return root.val;
        }
        return Math.min(root.val, min);
    }
}

IV. Maximum Balanced Subsequence Sum

Problem Description:

You are given a 0-indexed integer array nums.

A subsequence of nums having length k and consisting of indices i0 < i1 < ... < ik-1 is balanced if the following holds:

• nums[ij] - nums[ij-1] >= ij - ij-1, for every j in the range [1, k - 1].

A subsequence of nums having length 1 is considered balanced.

Return an integer denoting the maximum possible sum of elements in a balanced subsequence of nums.

A subsequence of an array is a new non-empty array that is formed from the original array by deleting some (possibly none) of the elements without disturbing the relative positions of the remaining elements.

Example 1:

Input: nums = [3,3,5,6]
Output: 14
Explanation: In this example, the subsequence [3,5,6] consisting of indices 0, 2, and 3 can be selected.
nums[2] - nums[0] >= 2 - 0.
nums[3] - nums[2] >= 3 - 2.
Hence, it is a balanced subsequence, and its sum is the maximum among the balanced subsequences of nums.
The subsequence consisting of indices 1, 2, and 3 is also valid.
It can be shown that it is not possible to get a balanced subsequence with a sum greater than 14.

Example 2:

Input: nums = [5,-1,-3,8]
Output: 13
Explanation: In this example, the subsequence [5,8] consisting of indices 0 and 3 can be selected.
nums[3] - nums[0] >= 3 - 0.
Hence, it is a balanced subsequence, and its sum is the maximum among the balanced subsequences of nums.
It can be shown that it is not possible to get a balanced subsequence with a sum greater than 13.

Example 3:

Input: nums = [-2,-1]
Output: -1
Explanation: In this example, the subsequence [-1] can be selected.
It is a balanced subsequence, and its sum is the maximum among the balanced subsequences of nums.

Constraints:

• 1 <= nums.length <= 105
• -109 <= nums[i] <= 109

Let’s change the formulation of the problem: consecutive elements nums[i] and nums[j] in a balanced subsequence must satisfy $i < j$ and $nums[j] - nums[i] \ge j - i$.

By rearranging the inequality above, we get $nums[j] - j \ge nums[i] - i$, which means the requirement for each element in a balanced subsequence only depends on its own value and index, not those of other elements.

Therefore, this problem is similar to the Longest Increasing Subsequence, and we can solve it using DP:

DP Definition: dp[j] represents the maximum sum of elements in a balanced subsequence ending at nums[j].

Recurrence relation: $dp[j] = nums[j] + \max\set{dp[i] | (i < j) ∧ (nums[j] - j \ge nums[i] - i)}$

Code:

class Solution {
    public long maxBalancedSubsequenceSum(int[] nums) {
        int n = nums.length;
        long ans = Long.MIN_VALUE;

        // dp[i]: maximum sum of elements in a subsequence ending at nums[i]
        long[] dp = new long[n];
        for (int j = 0; j < n; j++) {
            dp[j] = nums[j];
            long max = 0;
            for (int i = 0; i < j; i++) {
                if (nums[j] - j >= nums[i] - i) {
                    max = Math.max(max, dp[i]);
                }
            }
            dp[j] += max;

            ans = Math.max(ans, dp[j]);
        }
        return ans;
    }
}

Obviously, this solution has a time complexity of $O(n^2)$, which is bad. Until end of the contest, I couldn’t figure out an optimization strategy.

I plan to describe in detail how to solve this problem in the next post, based on insights from an expert’s solution. For now, I’ll focus on studying the relevant knowledge.