Posts tagged as “counter”

花花酱 LeetCode 2653. Sliding Subarray Beauty

By zxi on April 27, 2023

Given an integer array nums containing n integers, find the beauty of each subarray of size k.

The beauty of a subarray is the x^th smallest integer in the subarray if it is negative, or 0 if there are fewer than x negative integers.

Return an integer array containing n - k + 1 integers, which denote the beauty of the subarrays in order from the first index in the array.

A subarray is a contiguous non-empty sequence of elements within an array.

Example 1:

Input: nums = [1,-1,-3,-2,3], k = 3, x = 2
Output: [-1,-2,-2]
Explanation: There are 3 subarrays with size k = 3. 
The first subarray is [1, -1, -3] and the 2^nd smallest negative integer is -1. 
The second subarray is [-1, -3, -2] and the 2^nd smallest negative integer is -2. 
The third subarray is [-3, -2, 3] and the 2^nd smallest negative integer is -2.

Example 2:

Input: nums = [-1,-2,-3,-4,-5], k = 2, x = 2
Output: [-1,-2,-3,-4]
Explanation: There are 4 subarrays with size k = 2.
For [-1, -2], the 2^nd smallest negative integer is -1.
For [-2, -3], the 2^nd smallest negative integer is -2.
For [-3, -4], the 2^nd smallest negative integer is -3.
For [-4, -5], the 2^nd smallest negative integer is -4.

Example 3:

Input: nums = [-3,1,2,-3,0,-3], k = 2, x = 1
Output: [-3,0,-3,-3,-3]
Explanation: There are 5 subarrays with size k = 2.
For [-3, 1], the 1^st smallest negative integer is -3.
For [1, 2], there is no negative integer so the beauty is 0.
For [2, -3], the 1^st smallest negative integer is -3.
For [-3, 0], the 1^st smallest negative integer is -3.
For [0, -3], the 1^st smallest negative integer is -3.

Constraints:

n == nums.length
1 <= n <= 10⁵
1 <= k <= n
1 <= x <= k
-50 <= nums[i] <= 50

Solution: Sliding Window + Counter

Since the range of nums are very small (-50 ~ 50), we can use a counter to track the frequency of each element, s.t. we can find the k-the smallest element in O(50) instead of O(k).

Time complexity: O((n – k + 1) * 50)
Space complexity: O(50)

C++

// Author: Huahua

class Solution {

public:

vector<int> getSubarrayBeauty(vector<int>& nums, int k, int x) {

constexpr int kMax = 50;

const int n = nums.size();

vector<int> counts(2 * kMax + 1);

vector<int> ans;

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

if (i >= k)

--counts[nums[i - k] + kMax];

++counts[nums[i] + kMax];

if (i >= k - 1) {

int b = 0;

for (int j = 0, s = 0; j <= kMax; ++j) {

s += counts[j];

if (s >= x) {

b = j - kMax;

break;

}

ans.push_back(b);

}

return ans;

}

};

花花酱 LeetCode 2206. Divide Array Into Equal Pairs

By zxi on March 21, 2022

You are given an integer array nums consisting of 2 * n integers.

You need to divide nums into n pairs such that:

Each element belongs to exactly one pair.
The elements present in a pair are equal.

Return true if nums can be divided into n pairs, otherwise return false.

Example 1:

Input: nums = [3,2,3,2,2,2]
Output: true
Explanation: 
There are 6 elements in nums, so they should be divided into 6 / 2 = 3 pairs.
If nums is divided into the pairs (2, 2), (3, 3), and (2, 2), it will satisfy all the conditions.

Example 2:

Input: nums = [1,2,3,4]
Output: false
Explanation: 
There is no way to divide nums into 4 / 2 = 2 pairs such that the pairs satisfy every condition.

Constraints:

nums.length == 2 * n
1 <= n <= 500
1 <= nums[i] <= 500

Solution: Hashtable

Each number has to appear even numbers in order to be paired. Count the frequency of each number, return true if all of them are even numbers, return false otherwise.

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

C++

// Author: Huahua

class Solution {

public:

bool divideArray(vector<int>& nums) {

unordered_map<int, int> m;

for (int num : nums)

++m[num];

return all_of(begin(m), end(m), [](const auto& e) { return e.second % 2 == 0; });

}

};

花花酱 LeetCode 2150. Find All Lonely Numbers in the Array

By zxi on February 4, 2022

You are given an integer array nums. A number x is lonely when it appears only once, and no adjacent numbers (i.e. x + 1 and x - 1) appear in the array.

Return all lonely numbers in nums. You may return the answer in any order.

Example 1:

Input: nums = [10,6,5,8]
Output: [10,8]
Explanation: 
- 10 is a lonely number since it appears exactly once and 9 and 11 does not appear in nums.
- 8 is a lonely number since it appears exactly once and 7 and 9 does not appear in nums.
- 5 is not a lonely number since 6 appears in nums and vice versa.
Hence, the lonely numbers in nums are [10, 8].
Note that [8, 10] may also be returned.

Example 2:

Input: nums = [1,3,5,3]
Output: [1,5]
Explanation: 
- 1 is a lonely number since it appears exactly once and 0 and 2 does not appear in nums.
- 5 is a lonely number since it appears exactly once and 4 and 6 does not appear in nums.
- 3 is not a lonely number since it appears twice.
Hence, the lonely numbers in nums are [1, 5].
Note that [5, 1] may also be returned.

Constraints:

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

Solution: Counter

Computer the frequency of each number in the array, for a given number x with freq = 1, check freq of (x – 1) and (x + 1), if both of them are zero then x is lonely.

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

C++

// Author: Huahua

class Solution {

public:

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

unordered_map<int, int> m;

for (int x : nums)

++m[x];

vector<int> ans;

for (const auto [x, c] : m)

if (c == 1 && !m.count(x + 1) && !m.count(x - 1))

ans.push_back(x);

return ans;

}

};

花花酱 LeetCode 1737. Change Minimum Characters to Satisfy One of Three Conditions

By zxi on January 23, 2021

You are given two strings a and b that consist of lowercase letters. In one operation, you can change any character in a or b to any lowercase letter.

Your goal is to satisfy one of the following three conditions:

Every letter in a is strictly less than every letter in b in the alphabet.
Every letter in b is strictly less than every letter in a in the alphabet.
Both a and b consist of only one distinct letter.

Return the minimum number of operations needed to achieve your goal.

Example 1:

Input: a = "aba", b = "caa"
Output: 2
Explanation: Consider the best way to make each condition true:
1) Change b to "ccc" in 2 operations, then every letter in a is less than every letter in b.
2) Change a to "bbb" and b to "aaa" in 3 operations, then every letter in b is less than every letter in a.
3) Change a to "aaa" and b to "aaa" in 2 operations, then a and b consist of one distinct letter.
The best way was done in 2 operations (either condition 1 or condition 3).

Example 2:

Input: a = "dabadd", b = "cda"
Output: 3
Explanation: The best way is to make condition 1 true by changing b to "eee".

Constraints:

1 <= a.length, b.length <= 10⁵
a and b consist only of lowercase letters.

Solution: Brute Force

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

C++

// Author: Huahua

class Solution {

public:

int minCharacters(string a, string b) {

auto change = [](const string& a, const string& b) {

int ans = INT_MAX;

for (char c = 'a'; c < 'z'; ++c) {

int ops = 0;

for (char x : a) ops += x > c;

for (char x : b) ops += x <= c;

ans = min(ans, ops);

}

return ans;

};

int ans = min(change(a, b), change(b, a));

for (char c = 'a'; c <= 'z'; ++c) {

int ops = a.size() - count(begin(a), end(a), c) +

b.size() - count(begin(b), end(b), c);

ans = min(ans, ops);

}

return ans;

}

};

花花酱 LeetCode 383. Ransom Note

By zxi on March 15, 2018

题目大意：给你一个字符串，问能否用它其中的字符组成另外一个字符串，每个字符只能使用一次。

Problem:

Given an arbitrary ransom note string and another string containing letters from all the magazines, write a function that will return true if the ransom note can be constructed from the magazines ; otherwise, it will return false.

Each letter in the magazine string can only be used once in your ransom note.

Note:
You may assume that both strings contain only lowercase letters.

canConstruct("a", "b") -> false
canConstruct("aa", "ab") -> false
canConstruct("aa", "aab") -> true

Solution: HashTable

Time complexity: O(n + m)

Space complexity: O(128)

C++

// Author: Huahua

// Running time: 24 ms

class Solution {

public:

bool canConstruct(string ransomNote, string magazine) {

vector<int> counts(128, 0);

for (const char c : magazine)

++counts[c];

for (const char c : ransomNote)

if (--counts[c] < 0) return false;

return true;

}

};

// Author: Huahua

// Running time: 9 ms (beats 100%)

static int x=[](){

std::ios::sync_with_stdio(false);

cin.tie(NULL);

return 0;

}();

class Solution {

public:

bool canConstruct(const string& ransomNote, const string& magazine) {

vector<int> counts(128, 0);

for (const char c : magazine)

++counts[c];

for (const char c : ransomNote)

if (--counts[c] < 0) return false;

return true;

}

};

Python3

"""

Author: Huahua

Running time: 64 ms

"""

class Solution:

def canConstruct(self, ransomNote, magazine):

return not collections.Counter(ransomNote) - collections.Counter(magazine);