Huahua’s Tech Road

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

}

};

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

}

};

Huahua's Tech Road

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

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

Solution 1: Greedy + HashSet

C++

Solution 2: Two Pointers

C++