Posts tagged as “hashtable”

花花酱 LeetCode 1865. Finding Pairs With a Certain Sum

By zxi on August 4, 2021

You are given two integer arrays nums1 and nums2. You are tasked to implement a data structure that supports queries of two types:

Add a positive integer to an element of a given index in the array nums2.
Count the number of pairs (i, j) such that nums1[i] + nums2[j] equals a given value (0 <= i < nums1.length and 0 <= j < nums2.length).

Implement the FindSumPairs class:

FindSumPairs(int[] nums1, int[] nums2) Initializes the FindSumPairs object with two integer arrays nums1 and nums2.
void add(int index, int val) Adds val to nums2[index], i.e., apply nums2[index] += val.
int count(int tot) Returns the number of pairs (i, j) such that nums1[i] + nums2[j] == tot.

Example 1:

Input
["FindSumPairs", "count", "add", "count", "count", "add", "add", "count"]
[[[1, 1, 2, 2, 2, 3], [1, 4, 5, 2, 5, 4]], [7], [3, 2], [8], [4], [0, 1], [1, 1], [7]]
Output
[null, 8, null, 2, 1, null, null, 11]
Explanation
FindSumPairs findSumPairs = new FindSumPairs([1, 1, 2, 2, 2, 3], [1, 4, 5, 2, 5, 4]);
findSumPairs.count(7); // return 8; pairs (2,2), (3,2), (4,2), (2,4), (3,4), (4,4) make 2 + 5 and pairs (5,1), (5,5) make 3 + 4
findSumPairs.add(3, 2); // now nums2 = [1,4,5,4,5,4] 
findSumPairs.count(8); // return 2; pairs (5,2), (5,4) make 3 + 5 
findSumPairs.count(4); // return 1; pair (5,0) makes 3 + 1 
findSumPairs.add(0, 1); // now nums2 = [2,4,5,4,5,4] 
findSumPairs.add(1, 1); // now nums2 = [2,5,5,4,5,4] 
findSumPairs.count(7); // return 11; pairs (2,1), (2,2), (2,4), (3,1), (3,2), (3,4), (4,1), (4,2), (4,4) make 2 + 5 and pairs (5,3), (5,5) make 3 + 4

Constraints:

1 <= nums1.length <= 1000
1 <= nums2.length <= 10⁵
1 <= nums1[i] <= 10⁹
1 <= nums2[i] <= 10⁵
0 <= index < nums2.length
1 <= val <= 10⁵
1 <= tot <= 10⁹
At most 1000 calls are made to add and count each.

Solution: HashTable

Note nums1 and nums2 are unbalanced. Brute force method will take O(m*n) = O(10³*10⁵) = O(10⁸) for each count call which will TLE. We could use a hashtable to store the counts of elements from nums2, and only iterate over nums1 to reduce the time complexity.

Time complexity:

init: O(m) + O(n)
add: O(1)
count: O(m)

Total time is less than O(10⁶)

Space complexity: O(m + n)

C++

// Author: Huahua

class FindSumPairs {

public:

FindSumPairs(vector<int>& nums1,

vector<int>& nums2): nums1_(nums1), nums2_(nums2) {

for (int x : nums2_) ++freq_[x];

}

void add(int index, int val) {

if (--freq_[nums2_[index]] == 0)

freq_.erase(nums2_[index]);

++freq_[nums2_[index] += val];

}

int count(int tot) {

int ans = 0;

for (int a : nums1_) {

auto it = freq_.find(tot - a);

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

}

return ans;

}

private:

vector<int> nums1_;

vector<int> nums2_;

unordered_map<int, int> freq_;

};

Python3

# Author: Huahua

class FindSumPairs:

def __init__(self, nums1: List[int], nums2: List[int]):

self.nums1 = nums1

self.nums2 = nums2

self.freq = Counter(nums2)

def add(self, index: int, val: int) -> None:

self.freq.subtract((self.nums2[index],))

self.nums2[index] += val

self.freq.update((self.nums2[index],))

def count(self, tot: int) -> int:

return sum(self.freq[tot - a] for a in self.nums1)

花花酱 LeetCode 1832. Check if the Sentence Is Pangram

By zxi on April 18, 2021

A pangram is a sentence where every letter of the English alphabet appears at least once.

Given a string sentence containing only lowercase English letters, returntrue if sentence is a pangram, or false otherwise.

Example 1:

Input: sentence = "thequickbrownfoxjumpsoverthelazydog"
Output: true
Explanation: sentence contains at least one of every letter of the English alphabet.

Example 2:

Input: sentence = "leetcode"
Output: false

Constraints:

1 <= sentence.length <= 1000
sentence consists of lowercase English letters.

Solution: Hashset

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

C++

class Solution {

public:

bool checkIfPangram(string sentence) {

unordered_set<char> s;

for (char c : sentence)

s.insert(c);

return s.size() == 26;

}

};

Python3

class Solution:

def checkIfPangram(self, sentence: str) -> bool:

return len(set(sentence)) == 26

花花酱 LeetCode 1817. Finding the Users Active Minutes

By zxi on April 6, 2021

You are given the logs for users’ actions on LeetCode, and an integer k. The logs are represented by a 2D integer array logs where each logs[i] = [ID_i, time_i] indicates that the user with ID_i performed an action at the minute time_i.

Multiple users can perform actions simultaneously, and a single user can perform multiple actions in the same minute.

The user active minutes (UAM) for a given user is defined as the number of unique minutes in which the user performed an action on LeetCode. A minute can only be counted once, even if multiple actions occur during it.

You are to calculate a 1-indexed array answer of size k such that, for each j (1 <= j <= k), answer[j] is the number of users whose UAM equals j.

Return the array answer as described above.

Example 1:

Input: logs = [[0,5],[1,2],[0,2],[0,5],[1,3]], k = 5
Output: [0,2,0,0,0]
Explanation:
The user with ID=0 performed actions at minutes 5, 2, and 5 again. Hence, they have a UAM of 2 (minute 5 is only counted once).
The user with ID=1 performed actions at minutes 2 and 3. Hence, they have a UAM of 2.
Since both users have a UAM of 2, answer[2] is 2, and the remaining answer[j] values are 0.

Example 2:

Input: logs = [[1,1],[2,2],[2,3]], k = 4
Output: [1,1,0,0]
Explanation:
The user with ID=1 performed a single action at minute 1. Hence, they have a UAM of 1.
The user with ID=2 performed actions at minutes 2 and 3. Hence, they have a UAM of 2.
There is one user with a UAM of 1 and one with a UAM of 2.
Hence, answer[1] = 1, answer[2] = 1, and the remaining values are 0.

Constraints:

1 <= logs.length <= 10⁴
0 <= ID_i <= 10⁹
1 <= time_i <= 10⁵
k is in the range [The maximum UAM for a user, 10⁵].

Solution: Hashsets in a Hashtable

key: user_id, value: set{time}

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

C++

class Solution {

public:

vector<int> findingUsersActiveMinutes(vector<vector<int>>& logs, int k) {

unordered_map<int, unordered_set<int>> m;

vector<int> ans(k);

for (const auto& log : logs)

m[log[0]].insert(log[1]);

for (const auto& [id, s] : m)

++ans[s.size() - 1];

return ans;

}

};

花花酱 LeetCode 1814. Count Nice Pairs in an Array

By zxi on April 3, 2021

You are given an array nums that consists of non-negative integers. Let us define rev(x) as the reverse of the non-negative integer x. For example, rev(123) = 321, and rev(120) = 21. A pair of indices (i, j) is nice if it satisfies all of the following conditions:

0 <= i < j < nums.length
nums[i] + rev(nums[j]) == nums[j] + rev(nums[i])

Return the number of nice pairs of indices. Since that number can be too large, return it modulo 10⁹ + 7.

Example 1:

Input: nums = [42,11,1,97]
Output: 2
Explanation: The two pairs are:
 - (0,3) : 42 + rev(97) = 42 + 79 = 121, 97 + rev(42) = 97 + 24 = 121.
 - (1,2) : 11 + rev(1) = 11 + 1 = 12, 1 + rev(11) = 1 + 11 = 12.

Example 2:

Input: nums = [13,10,35,24,76]
Output: 4

Constraints:

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

Solution: Two Sum

Key = x – rev(x)

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

C++

// Author: Huahua

class Solution {

public:

int countNicePairs(vector<int>& nums) {

constexpr int kMod = 1e9 + 7;

unordered_map<int, int> m;

long ans = 0;

for (int x : nums) {

string s = to_string(x);

reverse(begin(s), end(s));

ans += m[x - stoi(s)]++;

}

return ans % kMod;

}

};

花花酱 LeetCode 1807. Evaluate the Bracket Pairs of a String

By zxi on March 27, 2021

You are given a string s that contains some bracket pairs, with each pair containing a non-empty key.

For example, in the string "(name)is(age)yearsold", there are two bracket pairs that contain the keys "name" and "age".

You know the values of a wide range of keys. This is represented by a 2D string array knowledge where each knowledge[i] = [key_i, value_i] indicates that key key_i has a value of value_i.

You are tasked to evaluate all of the bracket pairs. When you evaluate a bracket pair that contains some key key_i, you will:

Replace key_i and the bracket pair with the key’s corresponding value_i.
If you do not know the value of the key, you will replace key_i and the bracket pair with a question mark "?" (without the quotation marks).

Each key will appear at most once in your knowledge. There will not be any nested brackets in s.

Return the resulting string after evaluating all of the bracket pairs.

Example 1:

Input: s = "(name)is(age)yearsold", knowledge = [["name","bob"],["age","two"]]
Output: "bobistwoyearsold"
Explanation:
The key "name" has a value of "bob", so replace "(name)" with "bob".
The key "age" has a value of "two", so replace "(age)" with "two".

Example 2:

Input: s = "hi(name)", knowledge = [["a","b"]]
Output: "hi?"
Explanation: As you do not know the value of the key "name", replace "(name)" with "?".

Example 3:

Input: s = "(a)(a)(a)aaa", knowledge = [["a","yes"]]
Output: "yesyesyesaaa"
Explanation: The same key can appear multiple times.
The key "a" has a value of "yes", so replace all occurrences of "(a)" with "yes".
Notice that the "a"s not in a bracket pair are not evaluated.

Example 4:

Input: s = "(a)(b)", knowledge = [["a","b"],["b","a"]]
Output: "ba"

Constraints:

1 <= s.length <= 10⁵
0 <= knowledge.length <= 10⁵
knowledge[i].length == 2
1 <= key_i.length, value_i.length <= 10
s consists of lowercase English letters and round brackets '(' and ')'.
Every open bracket '(' in s will have a corresponding close bracket ')'.
The key in each bracket pair of s will be non-empty.
There will not be any nested bracket pairs in s.
key_i and value_i consist of lowercase English letters.
Each key_i in knowledge is unique.

Solution: Hashtable + Simulation

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

C++

// Author: Huahua

class Solution {

public:

string evaluate(string s, vector<vector<string>>& knowledge) {

unordered_map<string, string> m;

for (const auto& p : knowledge)

m[p[0]] = p[1];

string ans;

string cur;

bool in = false;

for (char c : s) {

if (c == '(') {

in = true;

} else if (c == ')') {

if (m.count(cur))

ans += m[cur];

else

ans += "?";

cur.clear();

in = false;

} else {

if (!in) ans += c;

else cur += c;

}

return ans;

}

};