Posts tagged as “medium”

花花酱 LeetCode 2640. Find the Score of All Prefixes of an Array

By zxi on April 29, 2023

We define the conversion array conver of an array arr as follows:

conver[i] = arr[i] + max(arr[0..i]) where max(arr[0..i]) is the maximum value of arr[j] over 0 <= j <= i.

We also define the score of an array arr as the sum of the values of the conversion array of arr.

Given a 0-indexed integer array nums of length n, return an array ans of length n where ans[i] is the score of the prefix nums[0..i].

Example 1:

Input: nums = [2,3,7,5,10]
Output: [4,10,24,36,56]
Explanation: 
For the prefix [2], the conversion array is [4] hence the score is 4
For the prefix [2, 3], the conversion array is [4, 6] hence the score is 10
For the prefix [2, 3, 7], the conversion array is [4, 6, 14] hence the score is 24
For the prefix [2, 3, 7, 5], the conversion array is [4, 6, 14, 12] hence the score is 36
For the prefix [2, 3, 7, 5, 10], the conversion array is [4, 6, 14, 12, 20] hence the score is 56

Example 2:

Input: nums = [1,1,2,4,8,16]
Output: [2,4,8,16,32,64]
Explanation: 
For the prefix [1], the conversion array is [2] hence the score is 2
For the prefix [1, 1], the conversion array is [2, 2] hence the score is 4
For the prefix [1, 1, 2], the conversion array is [2, 2, 4] hence the score is 8
For the prefix [1, 1, 2, 4], the conversion array is [2, 2, 4, 8] hence the score is 16
For the prefix [1, 1, 2, 4, 8], the conversion array is [2, 2, 4, 8, 16] hence the score is 32
For the prefix [1, 1, 2, 4, 8, 16], the conversion array is [2, 2, 4, 8, 16, 32] hence the score is 64

Constraints:

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

Solution: Prefix Sum

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

C++

// Author: Huahua

class Solution {

public:

vector<long long> findPrefixScore(vector<int>& nums) {

vector<long long> ans(nums.size());

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

m = max(m, nums[i]);

ans[i] = (i ? ans[i - 1] : 0) + nums[i] + m;

}

return ans;

}

};

花花酱 LeetCode 2644. Find the Maximum Divisibility Score

By zxi on April 28, 2023

You are given two 0-indexed integer arrays nums and divisors.

The divisibility score of divisors[i] is the number of indices j such that nums[j] is divisible by divisors[i].

Return the integer divisors[i] with the maximum divisibility score. If there is more than one integer with the maximum score, return the minimum of them.

Example 1:

Input: nums = [4,7,9,3,9], divisors = [5,2,3]
Output: 3
Explanation: The divisibility score for every element in divisors is:
The divisibility score of divisors[0] is 0 since no number in nums is divisible by 5.
The divisibility score of divisors[1] is 1 since nums[0] is divisible by 2.
The divisibility score of divisors[2] is 3 since nums[2], nums[3], and nums[4] are divisible by 3.
Since divisors[2] has the maximum divisibility score, we return it.

Example 2:

Input: nums = [20,14,21,10], divisors = [5,7,5]
Output: 5
Explanation: The divisibility score for every element in divisors is:
The divisibility score of divisors[0] is 2 since nums[0] and nums[3] are divisible by 5.
The divisibility score of divisors[1] is 2 since nums[1] and nums[2] are divisible by 7.
The divisibility score of divisors[2] is 2 since nums[0] and nums[3] are divisible by 5.
Since divisors[0], divisors[1], and divisors[2] all have the maximum divisibility score, we return the minimum of them (i.e., divisors[2]).

Example 3:

Input: nums = [12], divisors = [10,16]
Output: 10
Explanation: The divisibility score for every element in divisors is:
The divisibility score of divisors[0] is 0 since no number in nums is divisible by 10.
The divisibility score of divisors[1] is 0 since no number in nums is divisible by 16.
Since divisors[0] and divisors[1] both have the maximum divisibility score, we return the minimum of them (i.e., divisors[0]).

Constraints:

1 <= nums.length, divisors.length <= 1000
1 <= nums[i], divisors[i] <= 10⁹

Solution: Brute Force

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

C++

// Author: Huahua

class Solution {

public:

int maxDivScore(vector<int>& nums, vector<int>& divisors) {

int maxScore = 0;

int ans = INT_MAX;

for (int d : divisors) {

int score = 0;

for (int x : nums) {

score += x % d == 0;

}

if (score > maxScore) {

maxScore = score;

ans = d;

}

if (score == maxScore)

ans = min(ans, d);

}

return ans;

}

};

花花酱 LeetCode 2653. Sliding Subarray Beauty

By zxi on April 27, 2023

Given an integer array nums containing n integers, find the beauty of each subarray of size k.

The beauty of a subarray is the x^th smallest integer in the subarray if it is negative, or 0 if there are fewer than x negative integers.

Return an integer array containing n - k + 1 integers, which denote the beauty of the subarrays in order from the first index in the array.

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

Example 1:

Input: nums = [1,-1,-3,-2,3], k = 3, x = 2
Output: [-1,-2,-2]
Explanation: There are 3 subarrays with size k = 3. 
The first subarray is [1, -1, -3] and the 2^nd smallest negative integer is -1. 
The second subarray is [-1, -3, -2] and the 2^nd smallest negative integer is -2. 
The third subarray is [-3, -2, 3] and the 2^nd smallest negative integer is -2.

Example 2:

Input: nums = [-1,-2,-3,-4,-5], k = 2, x = 2
Output: [-1,-2,-3,-4]
Explanation: There are 4 subarrays with size k = 2.
For [-1, -2], the 2^nd smallest negative integer is -1.
For [-2, -3], the 2^nd smallest negative integer is -2.
For [-3, -4], the 2^nd smallest negative integer is -3.
For [-4, -5], the 2^nd smallest negative integer is -4.

Example 3:

Input: nums = [-3,1,2,-3,0,-3], k = 2, x = 1
Output: [-3,0,-3,-3,-3]
Explanation: There are 5 subarrays with size k = 2.
For [-3, 1], the 1^st smallest negative integer is -3.
For [1, 2], there is no negative integer so the beauty is 0.
For [2, -3], the 1^st smallest negative integer is -3.
For [-3, 0], the 1^st smallest negative integer is -3.
For [0, -3], the 1^st smallest negative integer is -3.

Constraints:

n == nums.length
1 <= n <= 10⁵
1 <= k <= n
1 <= x <= k
-50 <= nums[i] <= 50

Solution: Sliding Window + Counter

Since the range of nums are very small (-50 ~ 50), we can use a counter to track the frequency of each element, s.t. we can find the k-the smallest element in O(50) instead of O(k).

Time complexity: O((n – k + 1) * 50)
Space complexity: O(50)

C++

// Author: Huahua

class Solution {

public:

vector<int> getSubarrayBeauty(vector<int>& nums, int k, int x) {

constexpr int kMax = 50;

const int n = nums.size();

vector<int> counts(2 * kMax + 1);

vector<int> ans;

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

if (i >= k)

--counts[nums[i - k] + kMax];

++counts[nums[i] + kMax];

if (i >= k - 1) {

int b = 0;

for (int j = 0, s = 0; j <= kMax; ++j) {

s += counts[j];

if (s >= x) {

b = j - kMax;

break;

}

ans.push_back(b);

}

return ans;

}

};

花花酱 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 2554. Maximum Number of Integers to Choose From a Range I

By zxi on February 13, 2023

You are given an integer array banned and two integers n and maxSum. You are choosing some number of integers following the below rules:

The chosen integers have to be in the range [1, n].
Each integer can be chosen at most once.
The chosen integers should not be in the array banned.
The sum of the chosen integers should not exceed maxSum.

Return the maximum number of integers you can choose following the mentioned rules.

Example 1:

Input: banned = [1,6,5], n = 5, maxSum = 6
Output: 2
Explanation: You can choose the integers 2 and 4.
2 and 4 are from the range [1, 5], both did not appear in banned, and their sum is 6, which did not exceed maxSum.

Example 2:

Input: banned = [1,2,3,4,5,6,7], n = 8, maxSum = 1
Output: 0
Explanation: You cannot choose any integer while following the mentioned conditions.

Example 3:

Input: banned = [11], n = 7, maxSum = 50
Output: 7
Explanation: You can choose the integers 1, 2, 3, 4, 5, 6, and 7.
They are from the range [1, 7], all did not appear in banned, and their sum is 28, which did not exceed maxSum.

Constraints:

1 <= banned.length <= 10⁴
1 <= banned[i], n <= 10⁴
1 <= maxSum <= 10⁹

Solution 1: Greedy + HashSet

We would like to use the smallest numbers possible. Store all the banned numbers into a hashset, and enumerate numbers from 1 to n and check whether we can use that number.

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

C++

// Author: Huahua

class Solution {

public:

int maxCount(vector<int>& banned, int n, int maxSum) {

unordered_set<int> m(begin(banned), end(banned));

int ans = 0;

for (int i = 1, j = 0, sum = 0; i <= n; ++i) {

if (sum + i > maxSum) break;

if (m.count(i)) continue;

sum += i;

++ans;

}

return ans;

}

};

Solution 2: Two Pointers

Sort the banned numbers. Use one pointer j and compare with the current number i.

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

C++

// Author: Huahua

class Solution {

public:

int maxCount(vector<int>& banned, int n, int maxSum) {

sort(begin(banned), end(banned));

int ans = 0;

for (int i = 1, j = 0, sum = 0; i <= n; ++i) {

if (sum + i > maxSum) break;

while (j < banned.size() && banned[j] < i) ++j;

if (j < banned.size() && i == banned[j]) continue;

sum += i;

++ans;

}

return ans;

}

};