Posts tagged as “array”

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

}

};

花花酱 LeetCode 2134. Minimum Swaps to Group All 1’s Together II

By zxi on January 17, 2022

A swap is defined as taking two distinct positions in an array and swapping the values in them.

A circular array is defined as an array where we consider the first element and the last element to be adjacent.

Given a binary circular array nums, return the minimum number of swaps required to group all 1‘s present in the array together at any location.

Example 1:

Input: nums = [0,1,0,1,1,0,0]
Output: 1
Explanation: Here are a few of the ways to group all the 1's together:
[0,0,1,1,1,0,0] using 1 swap.
[0,1,1,1,0,0,0] using 1 swap.
[1,1,0,0,0,0,1] using 2 swaps (using the circular property of the array).
There is no way to group all 1's together with 0 swaps.
Thus, the minimum number of swaps required is 1.

Example 2:

Input: nums = [0,1,1,1,0,0,1,1,0]
Output: 2
Explanation: Here are a few of the ways to group all the 1's together:
[1,1,1,0,0,0,0,1,1] using 2 swaps (using the circular property of the array).
[1,1,1,1,1,0,0,0,0] using 2 swaps.
There is no way to group all 1's together with 0 or 1 swaps.
Thus, the minimum number of swaps required is 2.

Example 3:

Input: nums = [1,1,0,0,1]
Output: 0
Explanation: All the 1's are already grouped together due to the circular property of the array.
Thus, the minimum number of swaps required is 0.

Constraints:

1 <= nums.length <= 10⁵
nums[i] is either 0 or 1.

Solution: Sliding Window

Step 1: Count how many ones are there in the array. Assume it’s K.
Step 2: For each window of size k, count how many ones in the window, we have to swap 0s out with 1s to fill the window. ans = min(ans, k – ones).

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

C++

// Author: Huahua

class Solution {

public:

int minSwaps(vector<int>& nums) {

const int n = nums.size();

const int k = accumulate(begin(nums), end(nums), 0);

int ans = INT_MAX;

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

if (i >= k) cur -= nums[(i - k + n) % n];

cur += nums[i % n];

ans = min(ans, k - cur);

}

return ans;

}

};

花花酱 LeetCode 1995. Count Special Quadruplets

By zxi on December 31, 2021

Given a 0-indexed integer array nums, return the number of distinct quadruplets (a, b, c, d) such that:

nums[a] + nums[b] + nums[c] == nums[d], and
a < b < c < d

Example 1:

Input: nums = [1,2,3,6]
Output: 1
Explanation: The only quadruplet that satisfies the requirement is (0, 1, 2, 3) because 1 + 2 + 3 == 6.

Example 2:

Input: nums = [3,3,6,4,5]
Output: 0
Explanation: There are no such quadruplets in [3,3,6,4,5].

Example 3:

Input: nums = [1,1,1,3,5]
Output: 4
Explanation: The 4 quadruplets that satisfy the requirement are:
- (0, 1, 2, 3): 1 + 1 + 1 == 3
- (0, 1, 3, 4): 1 + 1 + 3 == 5
- (0, 2, 3, 4): 1 + 1 + 3 == 5
- (1, 2, 3, 4): 1 + 1 + 3 == 5

Constraints:

4 <= nums.length <= 50
1 <= nums[i] <= 100

Solution 1: Brute force (224ms)

Enumerate a, b, c, d.

Time complexity: O(C(n, 4)) = O(n⁴/24)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int countQuadruplets(vector<int>& nums) {

const int n = nums.size();

int ans = 0;

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

for (int b = a + 1; b < n; ++b)

for (int c = b + 1; c < n; ++c)

for (int d = c + 1; d < n; ++d)

ans += nums[a] + nums[b] + nums[c] == nums[d];

return ans;

}

};

Solution 2: Static frequency table + binary search (39ms)

For each element, we store its indices (sorted).

Given a, b, c, target t = nums[a] + nums[b] + nums[c], we check the hashtable and use binary search to find how many times it occurred after index c.

Time complexity: O(n³/6*logn)
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

int countQuadruplets(vector<int>& nums) {

constexpr int kMax = 100;

const int n = nums.size();

int ans = 0;

vector<vector<int>> m(kMax + 1);

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

m[nums[i]].push_back(i);

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

for (int b = a + 1; b < n; ++b)

for (int c = b + 1; c < n; ++c) {

const int t = nums[a] + nums[b] + nums[c];

if (t > kMax) continue;

ans += end(m[t]) - lower_bound(begin(m[t]), end(m[t]), c + 1);

}

return ans;

}

};

Solution 3: Dynamic frequency table (29ms)

Similar to 花花酱 LeetCode 1. Two Sum, we dynamically add elements (from right to left) into the hashtable.

Time complexity: O(n³/6)
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

int countQuadruplets(vector<int>& nums) {

constexpr int kMax = 100;

const int n = nums.size();

int ans = 0;

vector<int> m(kMax + 1);

// for every c we had seen, we can use it as target (nums[d]).

for (int c = n - 1; c >= 0; ++m[nums[c--]])

for (int a = 0; a < c; ++a)

for (int b = a + 1; b < c; ++b) {

const int t = nums[a] + nums[b] + nums[c];

if (t > kMax) continue;

ans += m[t];

}

return ans;

}

};