Huahua’s Tech Road

花花酱 LeetCode 2583. Kth Largest Sum in a Binary Tree

By zxi on March 5, 2023

You are given the root of a binary tree and a positive integer k.

The level sum in the tree is the sum of the values of the nodes that are on the same level.

Return the k^th largest level sum in the tree (not necessarily distinct). If there are fewer than k levels in the tree, return -1.

Note that two nodes are on the same level if they have the same distance from the root.

Example 1:

Input: root = [5,8,9,2,1,3,7,4,6], k = 2
Output: 13
Explanation: The level sums are the following:
- Level 1: 5.
- Level 2: 8 + 9 = 17.
- Level 3: 2 + 1 + 3 + 7 = 13.
- Level 4: 4 + 6 = 10.
The 2^nd largest level sum is 13.

Example 2:

Input: root = [1,2,null,3], k = 1
Output: 3
Explanation: The largest level sum is 3.

Constraints:

The number of nodes in the tree is n.
2 <= n <= 10⁵
1 <= Node.val <= 10⁶
1 <= k <= n

Solution: DFS + Sorting

Use DFS to traverse the tree and accumulate level sum. Once done, sort the level sums and find the k-th largest one.

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

Note: sum can be very large, use long long.

C++

// Author: Huahua

class Solution {

public:

long long kthLargestLevelSum(TreeNode* root, int k) {

vector<long long> sums;

function<void(TreeNode*, int)> dfs = [&](TreeNode* root, int d) {

if (!root) return;

while (d >= sums.size()) sums.push_back(0);

sums[d] += root->val;

dfs(root->left, d + 1);

dfs(root->right, d + 1);

};

dfs(root, 0);

if (sums.size() < k) return -1;

sort(rbegin(sums), rend(sums));

return sums[k - 1];

}

};

花花酱 LeetCode 2582. Pass the Pillow

By zxi on March 5, 2023

There are n people standing in a line labeled from 1 to n. The first person in the line is holding a pillow initially. Every second, the person holding the pillow passes it to the next person standing in the line. Once the pillow reaches the end of the line, the direction changes, and people continue passing the pillow in the opposite direction.

For example, once the pillow reaches the n^th person they pass it to the n - 1^th person, then to the n - 2^th person and so on.

Given the two positive integers n and time, return the index of the person holding the pillow after time seconds.

Example 1:

Input: n = 4, time = 5
Output: 2
Explanation: People pass the pillow in the following way: 1 -> 2 -> 3 -> 4 -> 3 -> 2.
Afer five seconds, the pillow is given to the 2^nd person.

Example 2:

Input: n = 3, time = 2
Output: 3
Explanation: People pass the pillow in the following way: 1 -> 2 -> 3.
Afer two seconds, the pillow is given to the 3^r^d person.

Constraints:

2 <= n <= 1000
1 <= time <= 1000

Solution: Math

It takes n – 1 seconds from 1 to n and takes another n – 1 seconds back from n to 1.
So one around takes 2 * (n – 1) seconds. We can mod time with 2 * (n – 1).

After that if time < n – 1 answer is time + 1, otherwise answer is n – (time – (n – 1))

Time complexity: O(1)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int passThePillow(int n, int time) {

time %= (2 * (n - 1));

return time > n - 1 ? n - (time - (n - 1)) : time + 1;

}

};

花花酱 LeetCode 2575. Find the Divisibility Array of a String

By zxi on February 25, 2023

You are given a 0-indexed string word of length n consisting of digits, and a positive integer m.

The divisibility array div of word is an integer array of length n such that:

div[i] = 1 if the numeric value of word[0,...,i] is divisible by m, or
div[i] = 0 otherwise.

Return the divisibility array of word.

Example 1:

Input: word = "998244353", m = 3
Output: [1,1,0,0,0,1,1,0,0]
Explanation: There are only 4 prefixes that are divisible by 3: "9", "99", "998244", and "9982443".

Example 2:

Input: word = "1010", m = 10
Output: [0,1,0,1]
Explanation: There are only 2 prefixes that are divisible by 10: "10", and "1010".

Constraints:

1 <= n <= 10⁵
word.length == n
word consists of digits from 0 to 9
1 <= m <= 10⁹

Solution: Big Integer Math

r = (r * 10 + word[i]) % m

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

C++

// Author: Huahua

class Solution {

public:

vector<int> divisibilityArray(string word, int m) {

vector<int> ans;

long long r = 0;

for (char c : word) {

r = (r * 10 + c - '0') % m;

ans.push_back(r == 0);

}

return ans;

}

};

花花酱 LeetCode 2574. Left and Right Sum Differences

By zxi on February 25, 2023

Given a 0-indexed integer array nums, find a 0-indexed integer array answer where:

answer.length == nums.length.
answer[i] = |leftSum[i] - rightSum[i]|.

Where:

leftSum[i] is the sum of elements to the left of the index i in the array nums. If there is no such element, leftSum[i] = 0.
rightSum[i] is the sum of elements to the right of the index i in the array nums. If there is no such element, rightSum[i] = 0.

Return the array answer.

Example 1:

Input: nums = [10,4,8,3]
Output: [15,1,11,22]
Explanation: The array leftSum is [0,10,14,22] and the array rightSum is [15,11,3,0].
The array answer is [|0 - 15|,|10 - 11|,|14 - 3|,|22 - 0|] = [15,1,11,22].

Example 2:

Input: nums = [1]
Output: [0]
Explanation: The array leftSum is [0] and the array rightSum is [0].
The array answer is [|0 - 0|] = [0].

Constraints:

1 <= nums.length <= 1000
1 <= nums[i] <= 10⁵

Solution: O(1) Space

Pre-compute the sum of all numbers as right sum, and accumulate left sum on the fly then we can achieve O(1) space.

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

C++

// Author: Huahua

class Solution {

public:

vector<int> leftRigthDifference(vector<int>& nums) {

int right = accumulate(begin(nums), end(nums), 0);

vector<int> ans;

for (int i = 0, left = 0; i < nums.size(); ++i) {

right -= nums[i];

ans.push_back(abs(left - right));

left += nums[i];

}

return ans;

}

};

花花酱 2570. Merge Two 2D Arrays by Summing Values

By zxi on February 18, 2023

You are given two 2D integer arrays nums1 and nums2.

nums1[i] = [id_i, val_i] indicate that the number with the id id_i has a value equal to val_i.
nums2[i] = [id_i, val_i] indicate that the number with the id id_i has a value equal to val_i.

Each array contains unique ids and is sorted in ascending order by id.

Merge the two arrays into one array that is sorted in ascending order by id, respecting the following conditions:

Only ids that appear in at least one of the two arrays should be included in the resulting array.
Each id should be included only once and its value should be the sum of the values of this id in the two arrays. If the id does not exist in one of the two arrays then its value in that array is considered to be 0.

Return the resulting array. The returned array must be sorted in ascending order by id.

Example 1:

Input: nums1 = [[1,2],[2,3],[4,5]], nums2 = [[1,4],[3,2],[4,1]]
Output: [[1,6],[2,3],[3,2],[4,6]]
Explanation: The resulting array contains the following:
- id = 1, the value of this id is 2 + 4 = 6.
- id = 2, the value of this id is 3.
- id = 3, the value of this id is 2.
- id = 4, the value of this id is 5 + 1 = 6.

Example 2:

Input: nums1 = [[2,4],[3,6],[5,5]], nums2 = [[1,3],[4,3]]
Output: [[1,3],[2,4],[3,6],[4,3],[5,5]]
Explanation: There are no common ids, so we just include each id with its value in the resulting list.

Constraints:

1 <= nums1.length, nums2.length <= 200
nums1[i].length == nums2[j].length == 2
1 <= id_i, val_i <= 1000
Both arrays contain unique ids.
Both arrays are in strictly ascending order by id.

Solution: Two Pointers

Time complexity: O(m + n)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

vector<vector<int>> mergeArrays(vector<vector<int>>& nums1, vector<vector<int>>& nums2) {

vector<vector<int>> ans;

for (int i = 0, j = 0; i < nums1.size() || j < nums2.size();) {

const int id1 = i < nums1.size() ? nums1[i][0] : INT_MAX;

const int id2 = j < nums2.size() ? nums2[j][0] : INT_MAX;

if (id1 == id2) {

ans.push_back({id1, nums1[i++][1] + nums2[j++][1]});

} else if (id1 < id2) {

ans.push_back(nums1[i++]);

} else {

ans.push_back(nums2[j++]);

}

return ans;

}

};

Huahua's Tech Road

花花酱 LeetCode 2583. Kth Largest Sum in a Binary Tree

Solution: DFS + Sorting

C++

花花酱 LeetCode 2582. Pass the Pillow

Solution: Math

C++

花花酱 LeetCode 2575. Find the Divisibility Array of a String

Solution: Big Integer Math

C++

花花酱 LeetCode 2574. Left and Right Sum Differences

C++

花花酱 2570. Merge Two 2D Arrays by Summing Values

Solution: Two Pointers

C++