Posts tagged as “medium”

花花酱 LeetCode 1674. Minimum Moves to Make Array Complementary

By zxi on November 29, 2020

You are given an integer array nums of even length n and an integer limit. In one move, you can replace any integer from nums with another integer between 1 and limit, inclusive.

The array nums is complementary if for all indices i (0-indexed), nums[i] + nums[n - 1 - i] equals the same number. For example, the array [1,2,3,4] is complementary because for all indices i, nums[i] + nums[n - 1 - i] = 5.

Return the minimum number of moves required to make nums complementary.

Example 1:

Input: nums = [1,2,4,3], limit = 4
Output: 1
Explanation: In 1 move, you can change nums to [1,2,2,3] (underlined elements are changed).
nums[0] + nums[3] = 1 + 3 = 4.
nums[1] + nums[2] = 2 + 2 = 4.
nums[2] + nums[1] = 2 + 2 = 4.
nums[3] + nums[0] = 3 + 1 = 4.
Therefore, nums[i] + nums[n-1-i] = 4 for every i, so nums is complementary.

Example 2:

Input: nums = [1,2,2,1], limit = 2
Output: 2
Explanation: In 2 moves, you can change nums to [2,2,2,2]. You cannot change any number to 3 since 3 > limit.

Example 3:

Input: nums = [1,2,1,2], limit = 2
Output: 0
Explanation: nums is already complementary.

Constraints:

n == nums.length
2 <= n <= 10⁵
1 <= nums[i] <= limit <= 10⁵
n is even.

Solution: Sweep Line / Prefix Sum

Let a = min(nums[i], nums[n-i-1]), b = max(nums[i], nums[n-i-1])
The key to this problem is how many moves do we need to make a + b == T.

if 2 <= T < a + 1, two moves, lower both a and b.
if a +1 <= T < a + b, one move, lower b
if a + b == T, zero move
if a + b + 1 <= T < b + limit + 1, one move, increase a
if b + limit + 1 <= T <= 2*limit, two moves, increase both a and b.

Time complexity: O(n + limit) or O(nlogn) if limit >>n
Space complexity: O(limit) or O(n)

C++

// Author: Huahua

class Solution {

public:

int minMoves(vector<int>& nums, int limit) {

const int n = nums.size();

vector<int> delta(limit * 2 + 2);

for (int i = 0; i < n / 2; ++i) {

const int a = min(nums[i], nums[n - i - 1]);

const int b = max(nums[i], nums[n - i - 1]);

delta[2] += 2; // dec a, dec b

--delta[a + 1]; // dec a

--delta[a + b]; // no op

++delta[a + b + 1]; // inc a

++delta[b + limit + 1]; // inc a, inc b

}

int ans = n;

for (int t = 2, cur = 0; t <= limit * 2; ++t) {

cur += delta[t];

ans = min(ans, cur);

}

return ans;

}

};

花花酱 LeetCode 1664. Ways to Make a Fair Array

By zxi on November 22, 2020

You are given an integer array nums. You can choose exactly one index (0-indexed) and remove the element. Notice that the index of the elements may change after the removal.

For example, if nums = [6,1,7,4,1]:

Choosing to remove index 1 results in nums = [6,7,4,1].
Choosing to remove index 2 results in nums = [6,1,4,1].
Choosing to remove index 4 results in nums = [6,1,7,4].

An array is fair if the sum of the odd-indexed values equals the sum of the even-indexed values.

Return the number of indices that you could choose such that after the removal, numsis fair.

Example 1:

Input: nums = [2,1,6,4]
Output: 1
Explanation:
Remove index 0: [1,6,4] -> Even sum: 1 + 4 = 5. Odd sum: 6. Not fair.
Remove index 1: [2,6,4] -> Even sum: 2 + 4 = 6. Odd sum: 6. Fair.
Remove index 2: [2,1,4] -> Even sum: 2 + 4 = 6. Odd sum: 1. Not fair.
Remove index 3: [2,1,6] -> Even sum: 2 + 6 = 8. Odd sum: 1. Not fair.
There is 1 index that you can remove to make nums fair.

Example 2:

Input: nums = [1,1,1]
Output: 3
Explanation: You can remove any index and the remaining array is fair.

Example 3:

Input: nums = [1,2,3]
Output: 0
Explanation: You cannot make a fair array after removing any index.

Constraints:

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

Solution: Prefix Sum

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

C++

// Author: Huahua

class Solution {

public:

int waysToMakeFair(vector<int>& nums) {

int n = nums.size();

vector<int> odds(n + 1);

vector<int> evens(n + 1);

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

odds[i + 1] = odds[i] + (i % 2 == 1) * nums[i];

evens[i + 1] = evens[i] + (i % 2 == 0) * nums[i];

}

int ans = 0;

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

const int odd = odds[i] + (evens[n] - evens[i + 1]);

const int even = evens[i] + (odds[n] - odds[i + 1]);

ans += odd == even;

}

return ans;

}

};

花花酱 LeetCode 1658. Minimum Operations to Reduce X to Zero

By zxi on November 14, 2020

You are given an integer array nums and an integer x. In one operation, you can either remove the leftmost or the rightmost element from the array nums and subtract its value from x. Note that this modifies the array for future operations.

Return the minimum number of operations to reduce x to exactly 0 if it’s possible, otherwise, return -1.

Example 1:

Input: nums = [1,1,4,2,3], x = 5
Output: 2
Explanation: The optimal solution is to remove the last two elements to reduce x to zero.

Example 2:

Input: nums = [5,6,7,8,9], x = 4
Output: -1

Example 3:

Input: nums = [3,2,20,1,1,3], x = 10
Output: 5
Explanation: The optimal solution is to remove the last three elements and the first two elements (5 operations in total) to reduce x to zero.

Constraints:

1 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁴
1 <= x <= 10⁹

Solution1: Prefix Sum + Hashtable

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

C++

// Author: Huahua

class Solution {

public:

int minOperations(vector<int>& nums, int x) {

const int n = nums.size();

vector<int> l(n), r(n);

unordered_map<int, int> ml, mr;

ml[0] = mr[0] = -1;

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

l[i] = nums[i] + (i > 0 ? l[i - 1] : 0);

r[i] = nums[n - i - 1] + (i > 0 ? r[i - 1]: 0);

ml[l[i]] = mr[r[i]] = i;

}

int ans = INT_MAX;

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

int s1 = x - l[i];

auto it1 = mr.find(s1);

if (it1 != mr.end()) ans = min(ans, i + 1 + it1->second + 1);

int s2 = x - r[i];

auto it2 = ml.find(s2);

if (it2 != ml.end()) ans = min(ans, i + 1 + it2->second + 1);

}

return ans > n ? -1 : ans;

}

};

Solution2: Sliding Window

Find the longest sliding window whose sum of elements equals sum(nums) – x
ans = n – window_size

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

C++

// Author: Huahua

class Solution {

public:

int minOperations(vector<int>& nums, int x) {

const int n = nums.size();

int target = accumulate(begin(nums), end(nums), 0) - x;

int ans = INT_MAX;

for (int s = 0, l = 0, r = 0; r < n; ++r) {

s += nums[r];

while (s > target && l <= r) s -= nums[l++];

if (s == target) ans = min(ans, n - (r - l + 1));

}

return ans > n ? -1 : ans;

}

};

花花酱 LeetCode 1657. Determine if Two Strings Are Close

By zxi on November 14, 2020

Two strings are considered close if you can attain one from the other using the following operations:

Operation 1: Swap any two existing characters.
- For example, abcde -> aecdb
Operation 2: Transform every occurrence of one existing character into another existing character, and do the same with the other character.
- For example, aacabb -> bbcbaa (all a‘s turn into b‘s, and all b‘s turn into a‘s)

You can use the operations on either string as many times as necessary.

Given two strings, word1 and word2, return true if word1 and word2 are close, and false otherwise.

Example 1:

Input: word1 = "abc", word2 = "bca"
Output: true
Explanation: You can attain word2 from word1 in 2 operations.
Apply Operation 1: "abc" -> "acb"
Apply Operation 1: "acb" -> "bca"

Example 2:

Input: word1 = "a", word2 = "aa"
Output: false
Explanation: It is impossible to attain word2 from word1, or vice versa, in any number of operations.

Example 3:

Input: word1 = "cabbba", word2 = "abbccc"
Output: true
Explanation: You can attain word2 from word1 in 3 operations.
Apply Operation 1: "cabbba" -> "caabbb"
Apply Operation 2: "caabbb" -> "baaccc"
Apply Operation 2: "baaccc" -> "abbccc"

Example 4:

Input: word1 = "cabbba", word2 = "aabbss"
Output: false
Explanation: It is impossible to attain word2 from word1, or vice versa, in any amount of operations.

Constraints:

1 <= word1.length, word2.length <= 10⁵
word1 and word2 contain only lowercase English letters.

Solution: Hashtable

Two strings are close:
1. Have the same length, ccabbb => 6 == aabccc => 6
2. Have the same char set, ccabbb => (a, b, c) == aabccc => (a, b, c)
3. Have the same sorted char counts ccabbb => (1, 2, 3) == aabccc => (1, 2, 3)

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

C++

// Author: Huahua

class Solution {

public:

bool closeStrings(string word1, string word2) {

const int l1 = word1.length();

const int l2 = word2.length();

if (l1 != l2) return false;

vector<int> f1(128), f2(128);

vector<int> s1(128), s2(128);

for (char c: word1) ++f1[c], s1[c] = 1;

for (char c: word2) ++f2[c], s2[c] = 1;

sort(begin(f1), end(f1));

sort(begin(f2), end(f2));

return f1 == f2 && s1 == s2;

}

};

Python3

# Author: Huahua

class Solution:

def closeStrings(self, word1: str, word2: str) -> bool:

c1, c2 = Counter(word1), Counter(word2)

return all([len(word1) == len(word2),

c1.keys() == c2.keys(),

sorted(c1.values()) == sorted(c2.values())])

Posts tagged as “medium”

花花酱 LeetCode 1674. Minimum Moves to Make Array Complementary

Solution: Sweep Line / Prefix Sum

C++

花花酱 LeetCode 1669. Merge In Between Linked Lists

Solution: List Operations

C++

花花酱 LeetCode 1664. Ways to Make a Fair Array

Solution: Prefix Sum

C++

花花酱 LeetCode 1658. Minimum Operations to Reduce X to Zero

Solution1: Prefix Sum + Hashtable

C++

Solution2: Sliding Window

C++

花花酱 LeetCode 1657. Determine if Two Strings Are Close

Solution: Hashtable

C++

Python3