Posts published in “Hashtable”

花花酱 LeetCode 2399. Check Distances Between Same Letters

By zxi on September 17, 2022

You are given a 0-indexed string s consisting of only lowercase English letters, where each letter in s appears exactly twice. You are also given a 0-indexed integer array distance of length 26.

Each letter in the alphabet is numbered from 0 to 25 (i.e. 'a' -> 0, 'b' -> 1, 'c' -> 2, … , 'z' -> 25).

In a well-spaced string, the number of letters between the two occurrences of the i^th letter is distance[i]. If the i^th letter does not appear in s, then distance[i] can be ignored.

Return true if s is a well-spaced string, otherwise return false.

Example 1:

Input: s = "abaccb", distance = [1,3,0,5,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
Output: true
Explanation:
- 'a' appears at indices 0 and 2 so it satisfies distance[0] = 1.
- 'b' appears at indices 1 and 5 so it satisfies distance[1] = 3.
- 'c' appears at indices 3 and 4 so it satisfies distance[2] = 0.
Note that distance[3] = 5, but since 'd' does not appear in s, it can be ignored.
Return true because s is a well-spaced string.

Example 2:

Input: s = "aa", distance = [1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
Output: false
Explanation:
- 'a' appears at indices 0 and 1 so there are zero letters between them.
Because distance[0] = 1, s is not a well-spaced string.

Constraints:

2 <= s.length <= 52
s consists only of lowercase English letters.
Each letter appears in s exactly twice.
distance.length == 26
0 <= distance[i] <= 50

Solution: Hashtable

Use a hastable to store the index of first occurrence of each letter.

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

C++

// Author: Huahua

class Solution {

public:

bool checkDistances(string s, vector<int>& distance) {

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

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

int c = s[i] - 'a';

if (m[c] >= 0 && i - m[c] - 1 != distance[c]) return false;

m[c] = i;

}

return true;

}

};

花花酱 LeetCode 2404. Most Frequent Even Element

By zxi on September 11, 2022

Given an integer array nums, return the most frequent even element.

If there is a tie, return the smallest one. If there is no such element, return -1.

Example 1:

Input: nums = [0,1,2,2,4,4,1]
Output: 2
Explanation:
The even elements are 0, 2, and 4. Of these, 2 and 4 appear the most.
We return the smallest one, which is 2.

Example 2:

Input: nums = [4,4,4,9,2,4]
Output: 4
Explanation: 4 is the even element appears the most.

Example 3:

Input: nums = [29,47,21,41,13,37,25,7]
Output: -1
Explanation: There is no even element.

Constraints:

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

Solution: Hashtable

Use a hashtable to store the frequency of even numbers.

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

C++

// Author: Huahua

class Solution {

public:

int mostFrequentEven(vector<int>& nums) {

unordered_map<int, int> m;

int ans = -1;

int best = 0;

for (int x : nums) {

if (x & 1) continue;

int cur = ++m[x];

if (cur > best) {

best = cur;

ans = x;

} else if (cur == best && x < ans) {

ans = x;

}

return ans;

}

};

花花酱 LeetCode 2260. Minimum Consecutive Cards to Pick Up

By zxi on May 3, 2022

You are given an integer array cards where cards[i] represents the value of the i^th card. A pair of cards are matching if the cards have the same value.

Return the minimum number of consecutive cards you have to pick up to have a pair of matching cards among the picked cards. If it is impossible to have matching cards, return -1.

Example 1:

Input: cards = [3,4,2,3,4,7]
Output: 4
Explanation: We can pick up the cards [3,4,2,3] which contain a matching pair of cards with value 3. Note that picking up the cards [4,2,3,4] is also optimal.

Example 2:

Input: cards = [1,0,5,3]
Output: -1
Explanation: There is no way to pick up a set of consecutive cards that contain a pair of matching cards.

Constraints:

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

Solution: Hashtable

Record the last position of each number,
ans = min{card_i – last[card_i]}

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

C++

// Author: Huahua

class Solution {

public:

int minimumCardPickup(vector<int>& cards) {

const int n = cards.size();

unordered_map<int, int> m;

int ans = INT_MAX;

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

if (m.count(cards[i]))

ans = min(ans, i - m[cards[i]] + 1);

m[cards[i]] = i;

}

return ans == INT_MAX ? -1 : ans;

}

};

花花酱 LeetCode 2248. Intersection of Multiple Arrays

By zxi on April 27, 2022

Given a 2D integer array nums where nums[i] is a non-empty array of distinct positive integers, return the list of integers that are present in each array ofnums sorted in ascending order.

Example 1:

Input: nums = [[3,1,2,4,5],[1,2,3,4],[3,4,5,6]]
Output: [3,4]
Explanation: 
The only integers present in each of nums[0] = [3,1,2,4,5], nums[1] = [1,2,3,4], and nums[2] = [3,4,5,6] are 3 and 4, so we return [3,4].

Example 2:

Input: nums = [[1,2,3],[4,5,6]]
Output: []
Explanation: 
There does not exist any integer present both in nums[0] and nums[1], so we return an empty list [].

Constraints:

1 <= nums.length <= 1000
1 <= sum(nums[i].length) <= 1000
1 <= nums[i][j] <= 1000
All the values of nums[i] are unique.

Solution: Hashtable

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

C++

// Author: Huahua

class Solution {

public:

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

vector<int> m(1001);

for (const auto& arr : nums)

for (const int x : arr)

++m[x];

vector<int> ans;

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

if (m[i] == nums.size())

ans.push_back(i);

return ans;

}

};

花花酱 LeetCode 2225. Find Players With Zero or One Losses

By zxi on April 2, 2022

You are given an integer array matches where matches[i] = [winner_i, loser_i] indicates that the player winner_i defeated player loser_i in a match.

Return a list answer of size 2 where:

answer[0] is a list of all players that have not lost any matches.
answer[1] is a list of all players that have lost exactly one match.

The values in the two lists should be returned in increasing order.

Note:

You should only consider the players that have played at least one match.
The testcases will be generated such that no two matches will have the same outcome.

Example 1:

Input: matches = [[1,3],[2,3],[3,6],[5,6],[5,7],[4,5],[4,8],[4,9],[10,4],[10,9]]
Output: [[1,2,10],[4,5,7,8]]
Explanation:
Players 1, 2, and 10 have not lost any matches.
Players 4, 5, 7, and 8 each have lost one match.
Players 3, 6, and 9 each have lost two matches.
Thus, answer[0] = [1,2,10] and answer[1] = [4,5,7,8].

Example 2:

Input: matches = [[2,3],[1,3],[5,4],[6,4]]
Output: [[1,2,5,6],[]]
Explanation:
Players 1, 2, 5, and 6 have not lost any matches.
Players 3 and 4 each have lost two matches.
Thus, answer[0] = [1,2,5,6] and answer[1] = [].

Constraints:

1 <= matches.length <= 10⁵
matches[i].length == 2
1 <= winner_i, loser_i <= 10⁵
winner_i != loser_i
All matches[i] are unique.

Solution: Hashtable

Use a hashtable to store the number of matches each player has lost. Note, also create an entry for those winners who never lose.

Time complexity: O(m), m = # of matches
Space complexity: O(n), n = # of players

C++

// Author: Huahua

class Solution {

public:

vector<vector<int>> findWinners(vector<vector<int>>& matches) {

unordered_map<int, int> m;

for (const auto& match : matches) {

m[match[0]]; // create an entry for the winner.

++m[match[1]];

}

vector<vector<int>> ans(2);

for (const auto& [player, loses] : m)

if (loses <= 1) ans[loses].push_back(player);

sort(begin(ans[0]), end(ans[0]));

sort(begin(ans[1]), end(ans[1]));

return ans;

}

};