Posts tagged as “array”

花花酱 LeetCode 2176. Count Equal and Divisible Pairs in an Array

By zxi on March 4, 2022

Given a 0-indexed integer array nums of length n and an integer k, return the number of pairs(i, j)where0 <= i < j < n, such thatnums[i] == nums[j]and(i * j)is divisible byk.

Example 1:

Input: nums = [3,1,2,2,2,1,3], k = 2
Output: 4
Explanation:
There are 4 pairs that meet all the requirements:
- nums[0] == nums[6], and 0 * 6 == 0, which is divisible by 2.
- nums[2] == nums[3], and 2 * 3 == 6, which is divisible by 2.
- nums[2] == nums[4], and 2 * 4 == 8, which is divisible by 2.
- nums[3] == nums[4], and 3 * 4 == 12, which is divisible by 2.

Example 2:

Input: nums = [1,2,3,4], k = 1
Output: 0
Explanation: Since no value in nums is repeated, there are no pairs (i,j) that meet all the requirements.

Constraints:

1 <= nums.length <= 100
1 <= nums[i], k <= 100

Solution: Brute Force

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

C++

// Author: Huahua

class Solution {

public:

int countPairs(vector<int>& nums, int k) {

const int n = nums.size();

int ans = 0;

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

for (int j = i + 1; j < n; ++j)

ans += (nums[i] == nums[j]) && (i * j % k == 0);

return ans;

}

};

花花酱 LeetCode 2170. Minimum Operations to Make the Array Alternating

By zxi on February 13, 2022

You are given a 0-indexed array nums consisting of n positive integers.

The array nums is called alternating if:

nums[i - 2] == nums[i], where 2 <= i <= n - 1.
nums[i - 1] != nums[i], where 1 <= i <= n - 1.

In one operation, you can choose an index i and change nums[i] into any positive integer.

Return the minimum number of operations required to make the array alternating.

Example 1:

Input: nums = [3,1,3,2,4,3]
Output: 3
Explanation:
One way to make the array alternating is by converting it to [3,1,3,1,3,1].
The number of operations required in this case is 3.
It can be proven that it is not possible to make the array alternating in less than 3 operations.

Example 2:

Input: nums = [1,2,2,2,2]
Output: 2
Explanation:
One way to make the array alternating is by converting it to [1,2,1,2,1].
The number of operations required in this case is 2.
Note that the array cannot be converted to [2,2,2,2,2] because in this case nums[0] == nums[1] which violates the conditions of an alternating array.

Constraints:

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

Solution: Greedy

Count and sort the frequency of numbers at odd and even positions.

Case 1: top frequency numbers are different, change the rest of numbers to them respectively.
Case 2: top frequency numbers are the same, compare top 1 odd + top 2 even vs top 2 even + top 1 odd.

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

C++

// Author: Huahua

class Solution {

public:

int minimumOperations(vector<int>& nums) {

const int n = nums.size();

if (n == 1) return 0;

unordered_map<int, int> odd, even;

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

((i & 1 ? odd : even)[nums[i]])++;

vector<pair<int, int>> o, e;

for (const auto [k, v] : odd)

o.emplace_back(v, k);

for (const auto [k, v] : even)

e.emplace_back(v, k);

sort(rbegin(o), rend(o));

sort(rbegin(e), rend(e));

if (o[0].second != e[0].second)

return n - o[0].first - e[0].first;

int mo = o[0].first + (e.size() > 1 ? e[1].first : 0);

int me = e[0].first + (o.size() > 1 ? o[1].first : 0);

return n - max(mo, me);

}

};

花花酱 LeetCode 2149. Rearrange Array Elements by Sign

By zxi on February 4, 2022

You are given a 0-indexed integer array nums of even length consisting of an equal number of positive and negative integers.

You should rearrange the elements of nums such that the modified array follows the given conditions:

Every consecutive pair of integers have opposite signs.
For all integers with the same sign, the order in which they were present in nums is preserved.
The rearranged array begins with a positive integer.

Return the modified array after rearranging the elements to satisfy the aforementioned conditions.

Example 1:

Input: nums = [3,1,-2,-5,2,-4]
Output: [3,-2,1,-5,2,-4]
Explanation:
The positive integers in nums are [3,1,2]. The negative integers are [-2,-5,-4].
The only possible way to rearrange them such that they satisfy all conditions is [3,-2,1,-5,2,-4].
Other ways such as [1,-2,2,-5,3,-4], [3,1,2,-2,-5,-4], [-2,3,-5,1,-4,2] are incorrect because they do not satisfy one or more conditions.

Example 2:

Input: nums = [-1,1]
Output: [1,-1]
Explanation:
1 is the only positive integer and -1 the only negative integer in nums.
So nums is rearranged to [1,-1].

Constraints:

2 <= nums.length <= 2 * 10⁵
nums.length is even
1 <= |nums[i]| <= 10⁵
nums consists of equal number of positive and negative integers.

Solution 1: Split and merge

Create two arrays to store positive and negative numbers.

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

C++

// Author: Huahua

class Solution {

public:

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

vector<int> pos;

vector<int> neg;

for (int x : nums)

(x > 0 ? pos : neg).push_back(x);

vector<int> ans;

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

ans.push_back(pos[i]);

ans.push_back(neg[i]);

}

return ans;

}

};

Solution 2: Two Pointers

Use two pointers to store the next pos / neg.

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

C++

// Author: Huahua

class Solution {

public:

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

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

int pos = 0;

int neg = 1;

for (int x : nums) {

int& index = x > 0 ? pos : neg;

ans[index] = x;

index += 2;

}

return ans;

}

};

花花酱 LeetCode 2148. Count Elements With Strictly Smaller and Greater Elements

By zxi on February 4, 2022

Given an integer array nums, return the number of elements that have both a strictly smaller and a strictly greater element appear in nums.

Example 1:

Input: nums = [11,7,2,15]
Output: 2
Explanation: The element 7 has the element 2 strictly smaller than it and the element 11 strictly greater than it.
Element 11 has element 7 strictly smaller than it and element 15 strictly greater than it.
In total there are 2 elements having both a strictly smaller and a strictly greater element appear in nums.

Example 2:

Input: nums = [-3,3,3,90]
Output: 2
Explanation: The element 3 has the element -3 strictly smaller than it and the element 90 strictly greater than it.
Since there are two elements with the value 3, in total there are 2 elements having both a strictly smaller and a strictly greater element appear in nums.

Constraints:

1 <= nums.length <= 100
-10⁵ <= nums[i] <= 10⁵

Solution: Min / Max elements

Find min and max of the array, count elements other than those two.

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

C++

// Author: Huahua

class Solution {

public:

int countElements(vector<int>& nums) {

auto [it1, it2] = minmax_element(begin(nums), end(nums));

return count_if(begin(nums), end(nums), [lo=*it1, hi=*it2](int x) {

return x != lo && x != hi;

});

}

};

花花酱 LeetCode 2144. Minimum Cost of Buying Candies With Discount

By zxi on January 30, 2022

A shop is selling candies at a discount. For every two candies sold, the shop gives a third candy for free.

The customer can choose any candy to take away for free as long as the cost of the chosen candy is less than or equal to the minimum cost of the two candies bought.

For example, if there are 4 candies with costs 1, 2, 3, and 4, and the customer buys candies with costs 2 and 3, they can take the candy with cost 1 for free, but not the candy with cost 4.

Given a 0-indexed integer array cost, where cost[i] denotes the cost of the i^th candy, return the minimum cost of buying all the candies.

Example 1:

Input: cost = [1,2,3]
Output: 5
Explanation: We buy the candies with costs 2 and 3, and take the candy with cost 1 for free.
The total cost of buying all candies is 2 + 3 = 5. This is the only way we can buy the candies.
Note that we cannot buy candies with costs 1 and 3, and then take the candy with cost 2 for free.
The cost of the free candy has to be less than or equal to the minimum cost of the purchased candies.

Example 2:

Input: cost = [6,5,7,9,2,2]
Output: 23
Explanation: The way in which we can get the minimum cost is described below:
- Buy candies with costs 9 and 7
- Take the candy with cost 6 for free
- We buy candies with costs 5 and 2
- Take the last remaining candy with cost 2 for free
Hence, the minimum cost to buy all candies is 9 + 7 + 5 + 2 = 23.

Example 3:

Input: cost = [5,5]
Output: 10
Explanation: Since there are only 2 candies, we buy both of them. There is not a third candy we can take for free.
Hence, the minimum cost to buy all candies is 5 + 5 = 10.

Constraints:

1 <= cost.length <= 100
1 <= cost[i] <= 100

Solution: Greedy

Sort candies in descending order. Buy 1st, 2nd, take 3rd, buy 4th, 5th take 6th, …

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

C++

// Author: Huahua

class Solution {

public:

int minimumCost(vector<int>& cost) {

sort(rbegin(cost), rend(cost));

while (cost.size() % 3) cost.push_back(0);

int ans = 0;

for (int i = 0; i < cost.size(); i += 3)

ans += cost[i] + cost[i + 1];

return ans;

}

};