Huahua’s Tech Road

花花酱 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;

}

};

花花酱 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;

}

};

花花酱 LeetCode 2553. Separate the Digits in an Array

By zxi on February 13, 2023

Given an array of positive integers nums, return an array answer that consists of the digits of each integer in nums after separating them in the same order they appear in nums.

To separate the digits of an integer is to get all the digits it has in the same order.

For example, for the integer 10921, the separation of its digits is [1,0,9,2,1].

Example 1:

Input: nums = [13,25,83,77]
Output: [1,3,2,5,8,3,7,7]
Explanation: 
- The separation of 13 is [1,3].
- The separation of 25 is [2,5].
- The separation of 83 is [8,3].
- The separation of 77 is [7,7].
answer = [1,3,2,5,8,3,7,7]. Note that answer contains the separations in the same order.

Example 2:

Input: nums = [7,1,3,9]
Output: [7,1,3,9]
Explanation: The separation of each integer in nums is itself.
answer = [7,1,3,9].

Constraints:

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

Solution: Stack

Time complexity: O(sum(log(nums[i]))
Space complexity: O(log(nums[i]))

C++

// Author: Huahua

class Solution {

public:

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

vector<int> ans;

for (int n : nums) {

stack<int> cur;

for (int x = n; x; x /= 10)

cur.push(x % 10);

while (!cur.empty())

ans.push_back(cur.top()), cur.pop();

}

return ans;

}

};

花花酱 LeetCode 2564. Substring XOR Queries

By zxi on February 12, 2023

You are given a binary string s, and a 2D integer array queries where queries[i] = [first_i, second_i].

For the i^th query, find the shortest substring of s whose decimal value, val, yields second_i when bitwise XORed with first_i. In other words, val ^ first_i == second_i.

The answer to the i^th query is the endpoints (0-indexed) of the substring [left_i, right_i] or [-1, -1] if no such substring exists. If there are multiple answers, choose the one with the minimum left_i.

Return an array ans where ans[i] = [left_i, right_i] is the answer to the i^th query.

A substring is a contiguous non-empty sequence of characters within a string.

Example 1:

Input: s = "101101", queries = [[0,5],[1,2]]
Output: [[0,2],[2,3]]
Explanation: For the first query the substring in range [0,2] is "101" which has a decimal value of 5, and 5 ^ 0 = 5, hence the answer to the first query is [0,2]. In the second query, the substring in range [2,3] is "11", and has a decimal value of 3, and 3 ^ 1 = 2. So, [2,3] is returned for the second query.

Example 2:

Input: s = "0101", queries = [[12,8]]
Output: [[-1,-1]]
Explanation: In this example there is no substring that answers the query, hence [-1,-1] is returned.

Example 3:

Input: s = "1", queries = [[4,5]]
Output: [[0,0]]
Explanation: For this example, the substring in range [0,0] has a decimal value of 1, and 1 ^ 4 = 5. So, the answer is [0,0].

Constraints:

1 <= s.length <= 10⁴
s[i] is either '0' or '1'.
1 <= queries.length <= 10⁵
0 <= first_i, second_i <= 10⁹

Solution: Pre-compute

We can pre-compute all possible substrings

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

C++

// Author: Huahua

class Solution {

public:

vector<vector<int>> substringXorQueries(string s, vector<vector<int>>& queries) {

unordered_map<int, vector<int>> m;

const int l = s.length();

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

if (s[i] == '0') {

if (!m.count(0)) m[0] = {i, i};

continue;

}

for (int j = 0, cur = 0; j < 32 && i + j < l; ++j) {

cur = (cur << 1) | (s[i + j] - '0');

if (!m.count(cur))

m[cur] = {i, i + j};

}

vector<vector<int>> ans;

for (const auto& q : queries) {

int x = q[0] ^ q[1];

if (m.count(x))

ans.push_back(m[x]);

else

ans.push_back({-1, -1});

}

return ans;

}

};

花花酱 LeetCode 2563. Count the Number of Fair Pairs

By zxi on February 12, 2023

Given a 0-indexed integer array nums of size n and two integers lower and upper, return the number of fair pairs.

A pair (i, j) is fair if:

0 <= i < j < n, and
lower <= nums[i] + nums[j] <= upper

Example 1:

Input: nums = [0,1,7,4,4,5], lower = 3, upper = 6
Output: 6
Explanation: There are 6 fair pairs: (0,3), (0,4), (0,5), (1,3), (1,4), and (1,5).

Example 2:

Input: nums = [1,7,9,2,5], lower = 11, upper = 11
Output: 1
Explanation: There is a single fair pair: (2,3).

Constraints:

1 <= nums.length <= 10⁵
nums.length == n
-10⁹ <= nums[i] <= 10⁹
-10⁹ <= lower <= upper <= 10⁹

Solution: Two Pointers

Sort the array, use two pointers to find how # of pairs (i, j) s.t. nums[i] + nums[j] <= limit.
Ans = count(upper) – count(lower – 1)

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

C++

// Author: Huahua

class Solution {

public:

long long countFairPairs(vector<int>& nums, int lower, int upper) {

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

auto count = [&](int limit) -> long long {

long long ans = 0;

for (int i = 0, j = nums.size() - 1; i < j; ++i) {

while (i < j && nums[i] + nums[j] > limit) --j;

ans += j - i;

}

return ans;

};

return count(upper) - count(lower - 1);

}

};

Huahua's Tech Road

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

Solution: Two Pointers

C++

花花酱 LeetCode 2554. Maximum Number of Integers to Choose From a Range I

Solution 1: Greedy + HashSet

C++

Solution 2: Two Pointers

C++

花花酱 LeetCode 2553. Separate the Digits in an Array

Solution: Stack

C++

花花酱 LeetCode 2564. Substring XOR Queries

Solution: Pre-compute

C++

花花酱 LeetCode 2563. Count the Number of Fair Pairs

Solution: Two Pointers

C++