Posts tagged as “hashtable”

花花酱 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 2135. Count Words Obtained After Adding a Letter

By zxi on January 17, 2022

You are given two 0-indexed arrays of strings startWords and targetWords. Each string consists of lowercase English letters only.

For each string in targetWords, check if it is possible to choose a string from startWords and perform a conversion operation on it to be equal to that from targetWords.

The conversion operation is described in the following two steps:

Append any lowercase letter that is not present in the string to its end.
- For example, if the string is "abc", the letters 'd', 'e', or 'y' can be added to it, but not 'a'. If 'd' is added, the resulting string will be "abcd".
Rearrange the letters of the new string in any arbitrary order.
- For example, "abcd" can be rearranged to "acbd", "bacd", "cbda", and so on. Note that it can also be rearranged to "abcd" itself.

Return the number of strings in targetWords that can be obtained by performing the operations on any string of startWords.

Note that you will only be verifying if the string in targetWords can be obtained from a string in startWords by performing the operations. The strings in startWords do not actually change during this process.

Example 1:

Input: startWords = ["ant","act","tack"], targetWords = ["tack","act","acti"]
Output: 2
Explanation:
- In order to form targetWords[0] = "tack", we use startWords[1] = "act", append 'k' to it, and rearrange "actk" to "tack".
- There is no string in startWords that can be used to obtain targetWords[1] = "act".
  Note that "act" does exist in startWords, but we must append one letter to the string before rearranging it.
- In order to form targetWords[2] = "acti", we use startWords[1] = "act", append 'i' to it, and rearrange "acti" to "acti" itself.

Example 2:

Input: startWords = ["ab","a"], targetWords = ["abc","abcd"]
Output: 1
Explanation:
- In order to form targetWords[0] = "abc", we use startWords[0] = "ab", add 'c' to it, and rearrange it to "abc".
- There is no string in startWords that can be used to obtain targetWords[1] = "abcd".

Constraints:

1 <= startWords.length, targetWords.length <= 5 * 10⁴
1 <= startWords[i].length, targetWords[j].length <= 26
Each string of startWords and targetWords consists of lowercase English letters only.
No letter occurs more than once in any string of startWords or targetWords.

Solution: Bitmask w/ Hashtable

Since there is no duplicate letters in each word, we can use a bitmask to represent a word.

Step 1: For each word in startWords, we obtain its bitmask and insert it into a hashtable.
Step 2: For each word in targetWords, enumerate it’s letter and unset 1 bit (skip one letter) and see whether it’s in the hashtable or not.

E.g. for target word “abc”, its bitmask is 0…0111, and we test whether “ab” or “ac” or “bc” in the hashtable or not.

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

C++

// Author: Huahua

class Solution {

public:

int wordCount(vector<string>& startWords, vector<string>& targetWords) {

unordered_set<int> s;

auto getKey = [](const string& s) {

return accumulate(begin(s), end(s), 0, [](int key, char c) { return key | (1 << (c - 'a')); });

};

for (const string& w : startWords)

s.insert(getKey(w));

return accumulate(begin(targetWords), end(targetWords), 0, [&](int ans, const string& w) {

const int key = getKey(w);

return ans + any_of(begin(w), end(w), [&](char c) { return s.count(key ^ (1 << (c - 'a'))); });

});

}

};

花花酱 LeetCode 2131. Longest Palindrome by Concatenating Two Letter Words

By zxi on January 9, 2022

You are given an array of strings words. Each element of words consists of two lowercase English letters.

Create the longest possible palindrome by selecting some elements from words and concatenating them in any order. Each element can be selected at most once.

Return the length of the longest palindrome that you can create. If it is impossible to create any palindrome, return 0.

A palindrome is a string that reads the same forward and backward.

Example 1:

Input: words = ["lc","cl","gg"]
Output: 6
Explanation: One longest palindrome is "lc" + "gg" + "cl" = "lcggcl", of length 6.
Note that "clgglc" is another longest palindrome that can be created.

Example 2:

Input: words = ["ab","ty","yt","lc","cl","ab"]
Output: 8
Explanation: One longest palindrome is "ty" + "lc" + "cl" + "yt" = "tylcclyt", of length 8.
Note that "lcyttycl" is another longest palindrome that can be created.

Example 3:

Input: words = ["cc","ll","xx"]
Output: 2
Explanation: One longest palindrome is "cc", of length 2.
Note that "ll" is another longest palindrome that can be created, and so is "xx".

Constraints:

1 <= words.length <= 10⁵
words[i].length == 2
words[i] consists of lowercase English letters.

Solution: Match mirrored words

For any pair of mirrored words, e.g. ‘ab’ <-> ‘ba’ or ‘aa’ <-> ‘aa’, we can extend the existing longest palindrome, ans += 4.
For any unpaired words with same letter, e.g. ‘cc’, we can only use one and put in the middle of the pladrome, ans += 2.

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

C++

// Author: Huahua

class Solution {

public:

int longestPalindrome(vector<string>& words) {

int ans = 0;

int same = 0;

vector<vector<int>> m(26, vector<int>(26));

for (const string& word : words) {

const int a = word[0] - 'a';

const int b = word[1] - 'a';

if (m[b][a]) {

--m[b][a];

ans += 4;

} else {

++m[a][b];

}

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

if (m[i][i]) {

ans += 2;

break;

}

return ans;

}

};

花花酱 LeetCode 1912. Design Movie Rental System

By zxi on January 1, 2022

You have a movie renting company consisting of n shops. You want to implement a renting system that supports searching for, booking, and returning movies. The system should also support generating a report of the currently rented movies.

Each movie is given as a 2D integer array entries where entries[i] = [shop_i, movie_i, price_i] indicates that there is a copy of movie movie_i at shop shop_i with a rental price of price_i. Each shop carries at most one copy of a movie movie_i.

The system should support the following functions:

Search: Finds the cheapest 5 shops that have an unrented copy of a given movie. The shops should be sorted by price in ascending order, and in case of a tie, the one with the smaller shop_i should appear first. If there are less than 5 matching shops, then all of them should be returned. If no shop has an unrented copy, then an empty list should be returned.
Rent: Rents an unrented copy of a given movie from a given shop.
Drop: Drops off a previously rented copy of a given movie at a given shop.
Report: Returns the cheapest 5 rented movies (possibly of the same movie ID) as a 2D list res where res[j] = [shop_j, movie_j] describes that the j^th cheapest rented movie movie_j was rented from the shop shop_j. The movies in res should be sorted by price in ascending order, and in case of a tie, the one with the smaller shop_j should appear first, and if there is still tie, the one with the smaller movie_j should appear first. If there are fewer than 5 rented movies, then all of them should be returned. If no movies are currently being rented, then an empty list should be returned.

Implement the MovieRentingSystem class:

MovieRentingSystem(int n, int[][] entries) Initializes the MovieRentingSystem object with n shops and the movies in entries.
List<Integer> search(int movie) Returns a list of shops that have an unrented copy of the given movie as described above.
void rent(int shop, int movie) Rents the given movie from the given shop.
void drop(int shop, int movie) Drops off a previously rented movie at the given shop.
List<List<Integer>> report() Returns a list of cheapest rented movies as described above.

Note: The test cases will be generated such that rent will only be called if the shop has an unrented copy of the movie, and drop will only be called if the shop had previously rented out the movie.

Example 1:

Input
["MovieRentingSystem", "search", "rent", "rent", "report", "drop", "search"]
[[3, [[0, 1, 5], [0, 2, 6], [0, 3, 7], [1, 1, 4], [1, 2, 7], [2, 1, 5]]], [1], [0, 1], [1, 2], [], [1, 2], [2]]
Output
[null, [1, 0, 2], null, null, [[0, 1], [1, 2]], null, [0, 1]]

Explanation
MovieRentingSystem movieRentingSystem = new MovieRentingSystem(3, [[0, 1, 5], [0, 2, 6], [0, 3, 7], [1, 1, 4], [1, 2, 7], [2, 1, 5]]);
movieRentingSystem.search(1);  // return [1, 0, 2], Movies of ID 1 are unrented at shops 1, 0, and 2. Shop 1 is cheapest; shop 0 and 2 are the same price, so order by shop number.
movieRentingSystem.rent(0, 1); // Rent movie 1 from shop 0. Unrented movies at shop 0 are now [2,3].
movieRentingSystem.rent(1, 2); // Rent movie 2 from shop 1. Unrented movies at shop 1 are now [1].
movieRentingSystem.report();   // return [[0, 1], [1, 2]]. Movie 1 from shop 0 is cheapest, followed by movie 2 from shop 1.
movieRentingSystem.drop(1, 2); // Drop off movie 2 at shop 1. Unrented movies at shop 1 are now [1,2].
movieRentingSystem.search(2);  // return [0, 1]. Movies of ID 2 are unrented at shops 0 and 1. Shop 0 is cheapest, followed by shop 1.

Constraints:

1 <= n <= 3 * 10⁵
1 <= entries.length <= 10⁵
0 <= shop_i < n
1 <= movie_i, price_i <= 10⁴
Each shop carries at most one copy of a movie movie_i.
At most 10⁵ calls in total will be made to search, rent, drop and report.

Solution: Hashtable + TreeSet

We need three containers:
1. movies tracks the {movie -> price} of each shop. This is readonly to get the price of a movie for generating keys for treesets.
2. unrented tracks unrented movies keyed by movie id, value is a treeset ordered by {price, shop}.
3. rented tracks rented movies, a treeset ordered by {price, shop, movie}

Note: By using array<int, 3> we can unpack values like below:
array<int, 3> entries; // {price, shop, movie}
for (const auto [price, shop, moive] : entries)
…

Time complexity:
Init: O(nlogn)
rent / drop: O(logn)
search / report: O(1)

Space complexity: O(n)

C++

// Author: Huahua

class MovieRentingSystem {

public:

MovieRentingSystem(int n, vector<vector<int>>& entries): movies(n) {

for (const auto& e : entries) {

const int shop = e[0];

const int movie = e[1];

const int price = e[2];

movies[shop].emplace(movie, price);

unrented[movie].emplace(price, shop);

}

vector<int> search(int movie) {

vector<int> shops;

for (const auto [price, shop] : unrented[movie]) {

shops.push_back(shop);

if (shops.size() == 5) break;

}

return shops;

}

void rent(int shop, int movie) {

const int price = movies[shop][movie];

unrented[movie].erase({price, shop});

rented.insert({price, shop, movie});

}

void drop(int shop, int movie) {

const int price = movies[shop][movie];

rented.erase({price, shop, movie});

unrented[movie].emplace(price, shop);

}

vector<vector<int>> report() {

vector<vector<int>> ans;

for (const auto& [price, shop, movie] : rented) {

ans.push_back({shop, movie});

if (ans.size() == 5) break;

}

return ans;

}

private:

vector<unordered_map<int, int>> movies; // shop -> {movie -> price}

unordered_map<int, set<pair<int, int>>> unrented; // movie -> {price, shop}

set<array<int, 3>> rented; // {price, shop, movie}

};

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

}

};