Huahua’s Tech Road

花花酱 LeetCode 2395. Find Subarrays With Equal Sum

By zxi on September 7, 2022

Given a 0-indexed integer array nums, determine whether there exist two subarrays of length 2 with equal sum. Note that the two subarrays must begin at different indices.

Return true if these subarrays exist, and false otherwise.

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

Example 1:

Input: nums = [4,2,4]
Output: true
Explanation: The subarrays with elements [4,2] and [2,4] have the same sum of 6.

Example 2:

Input: nums = [1,2,3,4,5]
Output: false
Explanation: No two subarrays of size 2 have the same sum.

Example 3:

Input: nums = [0,0,0]
Output: true
Explanation: The subarrays [nums[0],nums[1]] and [nums[1],nums[2]] have the same sum of 0. 
Note that even though the subarrays have the same content, the two subarrays are considered different because they are in different positions in the original array.

Constraints:

2 <= nums.length <= 1000
-10⁹ <= nums[i] <= 10⁹

Solution: Hashset

Use a hashset to track all the sums seen so far.

Time complexity: O(n)
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

bool findSubarrays(vector<int>& nums) {

unordered_set<int> s;

for (int i = 1; i < nums.size(); ++i)

if (!s.emplace(nums[i] + nums[i - 1]).second) return true;

return false;

}

};

花花酱 LeetCode 2389. Longest Subsequence With Limited Sum

By zxi on September 1, 2022

You are given an integer array nums of length n, and an integer array queries of length m.

Return an array answer of length m where answer[i] is the maximum size of a subsequence that you can take from nums such that the sum of its elements is less than or equal to queries[i].

A subsequence is an array that can be derived from another array by deleting some or no elements without changing the order of the remaining elements.

Example 1:

Input: nums = [4,5,2,1], queries = [3,10,21]
Output: [2,3,4]
Explanation: We answer the queries as follows:
- The subsequence [2,1] has a sum less than or equal to 3. It can be proven that 2 is the maximum size of such a subsequence, so answer[0] = 2.
- The subsequence [4,5,1] has a sum less than or equal to 10. It can be proven that 3 is the maximum size of such a subsequence, so answer[1] = 3.
- The subsequence [4,5,2,1] has a sum less than or equal to 21. It can be proven that 4 is the maximum size of such a subsequence, so answer[2] = 4.

Example 2:

Input: nums = [2,3,4,5], queries = [1]
Output: [0]
Explanation: The empty subsequence is the only subsequence that has a sum less than or equal to 1, so answer[0] = 0.

Constraints:

n == nums.length
m == queries.length
1 <= n, m <= 1000
1 <= nums[i], queries[i] <= 10⁶

Solution: Sort + PrefixSum + Binary Search

Time complexity: O(nlogn + mlogn)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

vector<int> answerQueries(vector<int>& nums, vector<int>& queries) {

sort(begin(nums), end(nums));

partial_sum(begin(nums), end(nums), begin(nums));

vector<int> ans;

for (int q : queries)

ans.push_back(upper_bound(begin(nums), end(nums), q) - begin(nums));

return ans;

}

};

花花酱 LeetCode 2374. Node With Highest Edge Score

By zxi on August 14, 2022

You are given a directed graph with n nodes labeled from 0 to n - 1, where each node has exactly one outgoing edge.

The graph is represented by a given 0-indexed integer array edges of length n, where edges[i] indicates that there is a directed edge from node i to node edges[i].

The edge score of a node i is defined as the sum of the labels of all the nodes that have an edge pointing to i.

Return the node with the highest edge score. If multiple nodes have the same edge score, return the node with the smallest index.

Example 1:

Input: edges = [1,0,0,0,0,7,7,5]
Output: 7
Explanation:
- The nodes 1, 2, 3 and 4 have an edge pointing to node 0. The edge score of node 0 is 1 + 2 + 3 + 4 = 10.
- The node 0 has an edge pointing to node 1. The edge score of node 1 is 0.
- The node 7 has an edge pointing to node 5. The edge score of node 5 is 7.
- The nodes 5 and 6 have an edge pointing to node 7. The edge score of node 7 is 5 + 6 = 11.
Node 7 has the highest edge score so return 7.

Example 2:

Input: edges = [2,0,0,2]
Output: 0
Explanation:
- The nodes 1 and 2 have an edge pointing to node 0. The edge score of node 0 is 1 + 2 = 3.
- The nodes 0 and 3 have an edge pointing to node 2. The edge score of node 2 is 0 + 3 = 3.
Nodes 0 and 2 both have an edge score of 3. Since node 0 has a smaller index, we return 0.

Constraints:

n == edges.length
2 <= n <= 10⁵
0 <= edges[i] < n
edges[i] != i

Solution:

Use an array to store the score of each node.

Time complexity: O(n)
Space complexity: O(n)

use max_element to find the largest element.

C++

// Author: Huahua

class Solution {

public:

int edgeScore(vector<int>& edges) {

const int n = edges.size();

vector<long> s(n);

for (int i = 0; i < n; ++i)

s[edges[i]] += i;

return max_element(begin(s), end(s)) - begin(s);

}

};

花花酱 LeetCode 2373. Largest Local Values in a Matrix

By zxi on August 14, 2022

You are given an n x n integer matrix grid.

Generate an integer matrix maxLocal of size (n - 2) x (n - 2) such that:

maxLocal[i][j] is equal to the largest value of the 3 x 3 matrix in grid centered around row i + 1 and column j + 1.

In other words, we want to find the largest value in every contiguous 3 x 3 matrix in grid.

Return the generated matrix.

Example 1:

Input: grid = [[9,9,8,1],[5,6,2,6],[8,2,6,4],[6,2,2,2]]
Output: [[9,9],[8,6]]
Explanation: The diagram above shows the original matrix and the generated matrix.
Notice that each value in the generated matrix corresponds to the largest value of a contiguous 3 x 3 matrix in grid.

Example 2:

Input: grid = [[1,1,1,1,1],[1,1,1,1,1],[1,1,2,1,1],[1,1,1,1,1],[1,1,1,1,1]]
Output: [[2,2,2],[2,2,2],[2,2,2]]
Explanation: Notice that the 2 is contained within every contiguous 3 x 3 matrix in grid.

Constraints:

n == grid.length == grid[i].length
3 <= n <= 100
1 <= grid[i][j] <= 100

Solution: Brute Force

Time complexity: O(n*n*9)
Space complexity: O(n*n)

C++

// Author: Huahua

class Solution {

public:

vector<vector<int>> largestLocal(vector<vector<int>>& grid) {

const int m = grid.size() - 2;

vector<vector<int>> ans(m, vector<int>(m));

for (int i = 0; i < m; ++i)

for (int j = 0; j < m; ++j)

for (int dy = 0; dy <= 2; ++dy)

for (int dx = 0; dx <= 2; ++dx)

ans[i][j] = max(ans[i][j], grid[i + dy][j + dx]);

return ans;

}

};

花花酱 LeetCode 133. Clone Graph

By zxi on August 14, 2022

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

Return a deep copy (clone) of the graph.

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

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

Test case format:

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

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

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

Example 1:

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

Example 2:

Input: adjList = [[]]
Output: [[]]
Explanation: Note that the input contains one empty list. The graph consists of only one node with val = 1 and it does not have any neighbors.

Example 3:

Input: adjList = []
Output: []
Explanation: This an empty graph, it does not have any nodes.

Constraints:

The number of nodes in the graph is in the range [0, 100].
1 <= Node.val <= 100
Node.val is unique for each node.
There are no repeated edges and no self-loops in the graph.
The Graph is connected and all nodes can be visited starting from the given node.

Solution: DFS + Hashtable

Time complexity: O(V+E)
Space complexity: O(V+E)

C++

// Author: Huahua

class Solution {

public:

Node* cloneGraph(Node* node) {

if (!node) return nullptr;

unordered_map<Node*, Node*> m;

function<void(Node*)> dfs = [&](Node* u) {

m[u] = new Node(u->val);

for (Node* v : u->neighbors) {

if (!m.count(v)) dfs(v);

m[u]->neighbors.push_back(m[v]);

}

};

dfs(node);

return m[node];

}

};

Huahua's Tech Road

花花酱 LeetCode 2395. Find Subarrays With Equal Sum

Solution: Hashset

C++

花花酱 LeetCode 2389. Longest Subsequence With Limited Sum

Solution: Sort + PrefixSum + Binary Search

C++

花花酱 LeetCode 2374. Node With Highest Edge Score

Solution:

C++

花花酱 LeetCode 2373. Largest Local Values in a Matrix

Solution: Brute Force

C++

花花酱 LeetCode 133. Clone Graph

Solution: DFS + Hashtable

C++