Posts published in “Algorithms”

花花酱 LeetCode 2657. Find the Prefix Common Array of Two Arrays

By zxi on April 30, 2023

You are given two 0-indexed integer permutations A and B of length n.

A prefix common array of A and B is an array C such that C[i] is equal to the count of numbers that are present at or before the index i in both A and B.

Return the prefix common array of A and B.

A sequence of n integers is called a permutation if it contains all integers from 1 to n exactly once.

Example 1:

Input: A = [1,3,2,4], B = [3,1,2,4]
Output: [0,2,3,4]
Explanation: At i = 0: no number is common, so C[0] = 0.
At i = 1: 1 and 3 are common in A and B, so C[1] = 2.
At i = 2: 1, 2, and 3 are common in A and B, so C[2] = 3.
At i = 3: 1, 2, 3, and 4 are common in A and B, so C[3] = 4.

Example 2:

Input: A = [2,3,1], B = [3,1,2]
Output: [0,1,3]
Explanation: At i = 0: no number is common, so C[0] = 0.
At i = 1: only 3 is common in A and B, so C[1] = 1.
At i = 2: 1, 2, and 3 are common in A and B, so C[2] = 3.

Constraints:

1 <= A.length == B.length == n <= 50
1 <= A[i], B[i] <= n
It is guaranteed that A and B are both a permutation of n integers.

Solution 1: Bitset

Use bitsets to store the numbers seen so far for each array, and use sA & sB to count the common elements.

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

C++

// Author: Huahua

class Solution {

public:

vector<int> findThePrefixCommonArray(vector<int>& A, vector<int>& B) {

bitset<51> sA;

bitset<51> sB;

vector<int> ans;

for (int i = 0; i < A.size(); ++i) {

sA.set(A[i]);

sB.set(B[i]);

ans.push_back((sA & sB).count());

}

return ans;

}

};

Solution 2: Counter

Use a counter to track the frequency of each element, when the counter[x] == 2, we found a pair.

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

C++

// Author: Huahua

class Solution {

public:

vector<int> findThePrefixCommonArray(vector<int>& A, vector<int>& B) {

vector<int> count(A.size() + 1);

vector<int> ans;

for (int i = 0, s = 0; i < A.size(); ++i) {

if (++count[A[i]] == 2) ++s;

if (++count[B[i]] == 2) ++s;

ans.push_back(s);

}

return ans;

}

};

花花酱 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 2643. Row With Maximum Ones

By zxi on April 28, 2023

Given a m x n binary matrix mat, find the 0-indexed position of the row that contains the maximum count of ones, and the number of ones in that row.

In case there are multiple rows that have the maximum count of ones, the row with the smallest row number should be selected.

Return an array containing the index of the row, and the number of ones in it.

Example 1:

Input: mat = [[0,1],[1,0]]
Output: [0,1]
Explanation: Both rows have the same number of 1's. So we return the index of the smaller row, 0, and the maximum count of ones (1). So, the answer is [0,1].

Example 2:

Input: mat = [[0,0,0],[0,1,1]]
Output: [1,2]
Explanation: The row indexed 1 has the maximum count of ones (2). So we return its index, 1, and the count. So, the answer is [1,2].

Example 3:

Input: mat = [[0,0],[1,1],[0,0]]
Output: [1,2]
Explanation: The row indexed 1 has the maximum count of ones (2). So the answer is [1,2].

Constraints:

m == mat.length
n == mat[i].length
1 <= m, n <= 100
mat[i][j] is either 0 or 1.

Solution: Counting

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

C++

// Author: Huahua

class Solution {

public:

vector<int> rowAndMaximumOnes(vector<vector<int>>& mat) {

vector<int> ans(2);

for (int i = 0; i < mat.size(); ++i) {

int ones = accumulate(begin(mat[i]), end(mat[i]), 0);

if (ones > ans[1]) {

ans[0] = i;

ans[1] = ones;

}

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;

}

};