Posts published in “Hashtable”

花花酱 LeetCode 1640. Check Array Formation Through Concatenation

By zxi on October 31, 2020

You are given an array of distinct integers arr and an array of integer arrays pieces, where the integers in pieces are distinct. Your goal is to form arr by concatenating the arrays in pieces in any order. However, you are not allowed to reorder the integers in each array pieces[i].

Return true if it is possible to form the array arr from pieces. Otherwise, return false.

Example 1:

Input: arr = [85], pieces = [[85]]
Output: true

Example 2:

Input: arr = [15,88], pieces = [[88],[15]]
Output: true
Explanation: Concatenate [15] then [88]

Example 3:

Input: arr = [49,18,16], pieces = [[16,18,49]]
Output: false
Explanation: Even though the numbers match, we cannot reorder pieces[0].

Example 4:

Input: arr = [91,4,64,78], pieces = [[78],[4,64],[91]]
Output: true
Explanation: Concatenate [91] then [4,64] then [78]

Example 5:

Input: arr = [1,3,5,7], pieces = [[2,4,6,8]]
Output: false

Constraints:

1 <= pieces.length <= arr.length <= 100
sum(pieces[i].length) == arr.length
1 <= pieces[i].length <= arr.length
1 <= arr[i], pieces[i][j] <= 100
The integers in arr are distinct.
The integers in pieces are distinct (i.e., If we flatten pieces in a 1D array, all the integers in this array are distinct).

Solution: Hashtable

Store the index of the first number of each piece, for each number a in arr, concat the entire piece array whose first element equals to a.

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

C++

class Solution {

public:

bool canFormArray(vector<int>& arr, vector<vector<int>>& pieces) {

unordered_map<int, int> m;

for (int i = 0; i < pieces.size(); ++i)

m[pieces[i][0]] = i;

vector<int> ans;

for (int a : arr) {

if (!m.count(a)) continue;

ans.insert(end(ans), begin(pieces[m[a]]), end(pieces[m[a]]));

}

return ans == arr;

}

};

花花酱 LeetCode 1636. Sort Array by Increasing Frequency

By zxi on October 31, 2020

Given an array of integers nums, sort the array in increasing order based on the frequency of the values. If multiple values have the same frequency, sort them in decreasing order.

Return the sorted array.

Example 1:

Input: nums = [1,1,2,2,2,3]
Output: [3,1,1,2,2,2]
Explanation: '3' has a frequency of 1, '1' has a frequency of 2, and '2' has a frequency of 3.

Example 2:

Input: nums = [2,3,1,3,2]
Output: [1,3,3,2,2]
Explanation: '2' and '3' both have a frequency of 2, so they are sorted in decreasing order.

Example 3:

Input: nums = [-1,1,-6,4,5,-6,1,4,1]
Output: [5,-1,4,4,-6,-6,1,1,1]

Constraints:

1 <= nums.length <= 100
-100 <= nums[i] <= 100

Solution: Hashtable + Sorting

Use a hashtable to track the frequency of each number.

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

C++

class Solution {

public:

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

unordered_map<int, int> freq;

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

sort(begin(nums), end(nums), [&](int a, int b) {

if (freq[a] != freq[b]) return freq[a] < freq[b];

return a > b;

});

return nums;

}

};

花花酱 LeetCode 1624. Largest Substring Between Two Equal Characters

By zxi on October 18, 2020

Given a string s, return the length of the longest substring between two equal characters, excluding the two characters. If there is no such substring return -1.

A substring is a contiguous sequence of characters within a string.

Example 1:

Input: s = "aa"
Output: 0
Explanation: The optimal substring here is an empty substring between the two 'a's.

Example 2:

Input: s = "abca"
Output: 2
Explanation: The optimal substring here is "bc".

Example 3:

Input: s = "cbzxy"
Output: -1
Explanation: There are no characters that appear twice in s.

Example 4:

Input: s = "cabbac"
Output: 4
Explanation: The optimal substring here is "abba". Other non-optimal substrings include "bb" and "".

Constraints:

1 <= s.length <= 300
s contains only lowercase English letters.

Solution: Hashtable

Remember the first position each letter occurs.

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

C++

class Solution {

public:

int maxLengthBetweenEqualCharacters(string s) {

vector<int> first(26, -1);

int ans = -1;

for (int i = 0; i < s.length(); ++i) {

int& p = first[s[i] - 'a'];

if (p != -1) {

ans = max(ans, i - p - 1);

} else {

p = i;

}

return ans;

}

};

花花酱 LeetCode 1604. Alert Using Same Key-Card Three or More Times in a One Hour Period

By zxi on October 3, 2020

Leetcode company workers use key-cards to unlock office doors. Each time a worker uses their key-card, the security system saves the worker’s name and the time when it was used. The system emits an alert if any worker uses the key-card three or more times in a one-hour period.

You are given a list of strings keyName and keyTime where [keyName[i], keyTime[i]] corresponds to a person’s name and the time when their key-card was used in a single day.

Access times are given in the 24-hour time format “HH:MM”, such as "23:51" and "09:49".

Return a list of unique worker names who received an alert for frequent keycard use. Sort the names in ascending order alphabetically.

Notice that "10:00" – "11:00" is considered to be within a one-hour period, while "23:51" – "00:10" is not considered to be within a one-hour period.

Example 1:

Input: keyName = ["daniel","daniel","daniel","luis","luis","luis","luis"], keyTime = ["10:00","10:40","11:00","09:00","11:00","13:00","15:00"]
Output: ["daniel"]
Explanation: "daniel" used the keycard 3 times in a one-hour period ("10:00","10:40", "11:00").

Example 2:

Input: keyName = ["alice","alice","alice","bob","bob","bob","bob"], keyTime = ["12:01","12:00","18:00","21:00","21:20","21:30","23:00"]
Output: ["bob"]
Explanation: "bob" used the keycard 3 times in a one-hour period ("21:00","21:20", "21:30").

Example 3:

Input: keyName = ["john","john","john"], keyTime = ["23:58","23:59","00:01"]
Output: []

Example 4:

Input: keyName = ["leslie","leslie","leslie","clare","clare","clare","clare"], keyTime = ["13:00","13:20","14:00","18:00","18:51","19:30","19:49"]
Output: ["clare","leslie"]

Constraints:

1 <= keyName.length, keyTime.length <= 10⁵
keyName.length == keyTime.length
keyTime are in the format “HH:MM”.
[keyName[i], keyTime[i]] is unique.
1 <= keyName[i].length <= 10
keyName[i] contains only lowercase English letters.

Solution: Hashtable + sorting

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

C++

class Solution {

public:

vector<string> alertNames(vector<string>& keyName, vector<string>& keyTime) {

unordered_map<string, vector<int>> t; // {name -> time}

for (size_t i = 0; i < keyName.size(); ++i) {

const int h = stoi(keyTime[i].substr(0, 2));

const int m = stoi(keyTime[i].substr(3));

t[keyName[i]].push_back(h * 60 + m);

}

vector<string> ans;

for (auto& [name, times] : t) {

sort(begin(times), end(times));

for (size_t i = 2; i < times.size(); ++i)

if (times[i] - times[i - 2] <= 60) {

ans.push_back(name);

break;

}

sort(begin(ans), end(ans));

return ans;

}

};

花花酱 LeetCode 1590. Make Sum Divisible by P

By zxi on September 20, 2020

Given an array of positive integers nums, remove the smallest subarray (possibly empty) such that the sum of the remaining elements is divisible by p. It is not allowed to remove the whole array.

Return the length of the smallest subarray that you need to remove, or -1 if it’s impossible.

A subarray is defined as a contiguous block of elements in the array.

Example 1:

Input: nums = [3,1,4,2], p = 6
Output: 1
Explanation: The sum of the elements in nums is 10, which is not divisible by 6. We can remove the subarray [4], and the sum of the remaining elements is 6, which is divisible by 6.

Example 2:

Input: nums = [6,3,5,2], p = 9
Output: 2
Explanation: We cannot remove a single element to get a sum divisible by 9. The best way is to remove the subarray [5,2], leaving us with [6,3] with sum 9.

Example 3:

Input: nums = [1,2,3], p = 3
Output: 0
Explanation: Here the sum is 6. which is already divisible by 3. Thus we do not need to remove anything.

Example 4:

Input: nums = [1,2,3], p = 7
Output: -1
Explanation: There is no way to remove a subarray in order to get a sum divisible by 7.

Example 5:

Input: nums = [1000000000,1000000000,1000000000], p = 3
Output: 0

Constraints:

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

Solution: HashTable + Prefix Sum

Very similar to subarray target sum.

Basically, we are trying to find a shortest subarray that has sum % p equals to r = sum(arr) % p.

We use a hashtable to store the last index of the prefix sum % p and check whether (prefix_sum + p – r) % p exists or not.

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

C++

class Solution {

public:

int minSubarray(vector<int>& nums, int p) {

const int n = nums.size();

int r = accumulate(begin(nums), end(nums), 0LL) % p;

if (r == 0) return 0;

unordered_map<int, int> m{{0, -1}}; // {prefix_sum % p -> last_index}

int s = 0;

int ans = n;

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

s = (s + nums[i]) % p;

auto it = m.find((s + p - r) % p);

if (it != m.end())

ans = min(ans, i - it->second);

m[s] = i;

}

return ans == n ? -1 : ans;

}

};

Python3

class Solution:

def minSubarray(self, nums: List[int], p: int) -> int:

r = sum(nums) % p

if r == 0: return 0

m = {0: -1}

ans = len(nums)

s = 0

for i, x in enumerate(nums):

s = (s + x) % p

t = (s + p - r) % p

if t in m:

ans = min(ans, i - m[t])

m[s] = i

return -1 if ans == len(nums) else ans