Posts published in “Hashtable”

花花酱 LeetCode 1726. Tuple with Same Product

By zxi on January 17, 2021

Given an array nums of distinct positive integers, return the number of tuples (a, b, c, d) such that a * b = c * d where a, b, c, and d are elements of nums, and a != b != c != d.

Example 1:

Input: nums = [2,3,4,6]
Output: 8
Explanation: There are 8 valid tuples:
(2,6,3,4) , (2,6,4,3) , (6,2,3,4) , (6,2,4,3)
(3,4,2,6) , (4,3,2,6) , (3,4,6,2) , (4,3,6,2)

Example 2:

Input: nums = [1,2,4,5,10]
Output: 16
Explanation: There are 16 valids tuples:
(1,10,2,5) , (1,10,5,2) , (10,1,2,5) , (10,1,5,2)
(2,5,1,10) , (2,5,10,1) , (5,2,1,10) , (5,2,10,1)
(2,10,4,5) , (2,10,5,4) , (10,2,4,5) , (10,2,4,5)
(4,5,2,10) , (4,5,10,2) , (5,4,2,10) , (5,4,10,2)

Example 3:

Input: nums = [2,3,4,6,8,12]
Output: 40

Example 4:

Input: nums = [2,3,5,7]
Output: 0

Constraints:

1 <= nums.length <= 1000
1 <= nums[i] <= 10⁴
All elements in nums are distinct.

Solution: HashTable

Similar idea to 花花酱 LeetCode 1. Two Sum

Use a hashtable to store all the pair product counts.

Enumerate all possible pairs, increase the answer by the same product counts * 8.

Why time 8? C(4,1) * C(1,1) * C(2,1) * C(1,1)

For pair one AxB, A can be placed at any position in a four tuple, B’s position is then fixed. For another pair CxD, C has two positions to choose from, D is fixed.

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

C++

// Author: Huahua

class Solution {

public:

int tupleSameProduct(vector<int>& nums) {

const int n = nums.size();

unordered_map<int, int> m;

int ans = 0;

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

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

ans += 8 * m[nums[i] * nums[j]]++;

return ans;

}

};

花花酱 LeetCode 1711. Count Good Meals

By zxi on January 2, 2021

A good meal is a meal that contains exactly two different food items with a sum of deliciousness equal to a power of two.

You can pick any two different foods to make a good meal.

Given an array of integers deliciousness where deliciousness[i] is the deliciousness of the i^th item of food, return the number of different good meals you can make from this list modulo 10⁹ + 7.

Note that items with different indices are considered different even if they have the same deliciousness value.

Example 1:

Input: deliciousness = [1,3,5,7,9]
Output: 4
Explanation: The good meals are (1,3), (1,7), (3,5) and, (7,9).
Their respective sums are 4, 8, 8, and 16, all of which are powers of 2.

Example 2:

Input: deliciousness = [1,1,1,3,3,3,7]
Output: 15
Explanation: The good meals are (1,1) with 3 ways, (1,3) with 9 ways, and (1,7) with 3 ways.

Constraints:

1 <= deliciousness.length <= 10⁵
0 <= deliciousness[i] <= 2²⁰

Solution: Hashtable

Same idea as LeetCode 1: Two Sum

Use a hashtable to store the occurrences of all the numbers added so far. For a new number x, check all possible 2^i – x. ans += freq[2^i – x] 0 <= i <= 21

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

C++

class Solution {

public:

int countPairs(vector<int>& A) {

constexpr int kMod = 1e9 + 7;

unordered_map<int, int> m;

long ans = 0;

for (int x : A) {

for (int t = 1; t <= 1 << 21; t *= 2) {

auto it = m.find(t - x);

if (it != end(m)) ans += it->second;

}

++m[x];

}

return ans % kMod;

}

};

Python3

class Solution:

def countPairs(self, deliciousness: List[int]) -> int:

sums = [1<<i for i in range(22)]

m = defaultdict(int)

ans = 0

for x in deliciousness:

for t in sums:

if t - x in m: ans += m[t - x]

m[x] += 1

return ans % (10**9 + 7)

花花酱 LeetCode 1684. Count the Number of Consistent Strings

By zxi on December 12, 2020

You are given a string allowed consisting of distinct characters and an array of strings words. A string is consistent if all characters in the string appear in the string allowed.

Return the number of consistent strings in the array words.

Example 1:

Input: allowed = "ab", words = ["ad","bd","aaab","baa","badab"]
Output: 2
Explanation: Strings "aaab" and "baa" are consistent since they only contain characters 'a' and 'b'.

Example 2:

Input: allowed = "abc", words = ["a","b","c","ab","ac","bc","abc"]
Output: 7
Explanation: All strings are consistent.

Example 3:

Input: allowed = "cad", words = ["cc","acd","b","ba","bac","bad","ac","d"]
Output: 4
Explanation: Strings "cc", "acd", "ac", and "d" are consistent.

Constraints:

1 <= words.length <= 10⁴
1 <= allowed.length <=26
1 <= words[i].length <= 10
The characters in allowed are distinct.
words[i] and allowed contain only lowercase English letters.

Solution: Hashtable

Time complexity: O(sum(len(word))
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int countConsistentStrings(string allowed, vector<string>& words) {

vector<int> m(26);

for (char c : allowed) m[c - 'a'] = 1;

int ans = 0;

for (const string& w : words)

ans += all_of(begin(w), end(w), [&m](char c) { return m[c - 'a']; });

return ans;

}

};

Python3

# Author: Huahua

class Solution:

def countConsistentStrings(self, allowed: str, words: List[str]) -> int:

return sum(all(c in allowed for c in w) for w in words)

花花酱 LeetCode 1679. Max Number of K-Sum Pairs

By zxi on December 6, 2020

You are given an integer array nums and an integer k.

In one operation, you can pick two numbers from the array whose sum equals k and remove them from the array.

Return the maximum number of operations you can perform on the array.

Example 1:

Input: nums = [1,2,3,4], k = 5
Output: 2
Explanation: Starting with nums = [1,2,3,4]:
- Remove numbers 1 and 4, then nums = [2,3]
- Remove numbers 2 and 3, then nums = []
There are no more pairs that sum up to 5, hence a total of 2 operations.

Example 2:

Input: nums = [3,1,3,4,3], k = 6
Output: 1
Explanation: Starting with nums = [3,1,3,4,3]:
- Remove the first two 3's, then nums = [1,4,3]
There are no more pairs that sum up to 6, hence a total of 1 operation.

Constraints:

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

Solution 1: Frequency Map

For each x, check freq[x] and freq[k – x]. Note: there is a special case when x + x == k.

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

C++

class Solution {

public:

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

unordered_map<int, int> m;

int ans = 0;

for (int x : nums) ++m[x];

for (int x : nums) {

if (m[x] < 1 || m[k - x] < 1 + (x + x == k)) continue;

--m[x];

--m[k - x];

++ans;

}

return ans;

}

};

Python3

class Solution:

def maxOperations(self, nums: List[int], k: int) -> int:

m = defaultdict(int)

ans = 0

for x in nums: m[x] += 1

for x in nums:

if m[x] < 1 or m[k - x] < 1 + (x + x == k): continue

m[x] -= 1

m[k - x] -= 1

ans += 1

return ans

Solution 2: Two Pointers

Sort the number, start from i = 0, j = n – 1, compare s = nums[i] + nums[j] with k and move i, j accordingly.

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

C++

class Solution {

public:

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

sort(begin(nums), end(nums));

int i = 0, j = nums.size() - 1;

int ans = 0;

while (i < j) {

const int s = nums[i] + nums[j];

if (s == k) {

++ans;

++i; --j;

} else if (s < k) {

++i;

} else {

--j;

}

return ans;

}

};

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

}

};