Posts tagged as “hashtable”

花花酱 LeetCode 2441. Largest Positive Integer That Exists With Its Negative

By zxi on October 15, 2022

Given an integer array nums that does not contain any zeros, find the largest positive integer k such that -k also exists in the array.

Return the positive integer k. If there is no such integer, return -1.

Example 1:

Input: nums = [-1,2,-3,3]
Output: 3
Explanation: 3 is the only valid k we can find in the array.

Example 2:

Input: nums = [-1,10,6,7,-7,1]
Output: 7
Explanation: Both 1 and 7 have their corresponding negative values in the array. 7 has a larger value.

Example 3:

Input: nums = [-10,8,6,7,-2,-3]
Output: -1
Explanation: There is no a single valid k, we return -1.

Constraints:

1 <= nums.length <= 1000
-1000 <= nums[i] <= 1000
nums[i] != 0

Solution 1: Hashtable

We can do in one pass by checking whether -x in the hashtable and update ans with abs(x) if so.

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

C++

// Author: Huahua

class Solution {

public:

int findMaxK(vector<int>& nums) {

unordered_set<int> s;

int ans = -1;

for (int x : nums) {

if (abs(x) > ans && s.count(-x))

ans = abs(x);

s.insert(x);

}

return ans;

}

};

Solution 2: Sorting

Sort the array by abs(x) in descending order.

[-1,10,6,7,-7,1] becomes = [-1, 1, 6, -7, 7, 10]

Check whether arr[i] = -arr[i-1].

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

C++

// Author: Huahua

class Solution {

public:

int findMaxK(vector<int>& nums) {

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

return abs(a) == abs(b) ? a < b : abs(a) > abs(b);

});

for (int i = 1; i < nums.size(); ++i)

if (nums[i] == -nums[i - 1]) return nums[i];

return -1;

}

};

Solution 3: Two Pointers

Sort the array.

Let sum = nums[i] + nums[j], sum == 0, we find one pair, if sum < 0, ++i else –j.

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

C++

// Author: Huahua

class Solution {

public:

int findMaxK(vector<int>& nums) {

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

int ans = -1;

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

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

if (s == 0) {

ans = max(ans, nums[j]);

++i, --j;

} else if (s < 0) {

++i;

} else {

--j;

}

return ans;

}

};

花花酱 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 2405. Optimal Partition of String

By zxi on September 11, 2022

Given a string s, partition the string into one or more substrings such that the characters in each substring are unique. That is, no letter appears in a single substring more than once.

Return the minimum number of substrings in such a partition.

Note that each character should belong to exactly one substring in a partition.

Example 1:

Input: s = "abacaba"
Output: 4
Explanation:
Two possible partitions are ("a","ba","cab","a") and ("ab","a","ca","ba").
It can be shown that 4 is the minimum number of substrings needed.

Example 2:

Input: s = "ssssss"
Output: 6
Explanation:
The only valid partition is ("s","s","s","s","s","s").

Constraints:

1 <= s.length <= 10⁵
s consists of only English lowercase letters.

Solution: Greedy

Extend the cur string as long as possible unless a duplicate character occurs.

You can use hashtable / array or bitmask to mark whether a character has been seen so far.

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

C++

// Author: Huahua

class Solution {

public:

int partitionString(string s) {

unordered_set<char> m;

int ans = 0;

for (char c : s) {

if (m.insert(c).second) continue;

m.clear();

m.insert(c);

++ans;

}

return ans + 1;

}

};

C++

// Author: Huahua

class Solution {

public:

int partitionString(string s) {

vector<int> m(26);

int ans = 0;

for (char c : s) {

if (++m[c - 'a'] == 1) continue;

fill(begin(m), end(m), 0);

m[c - 'a'] = 1;

++ans;

}

return ans + 1;

}

};

C++

// Author: Huahua

class Solution {

public:

int partitionString(string s) {

int mask = 0;

int ans = 0;

for (char c : s) {

if (mask & (1 << (c - 'a'))) {

mask = 0;

++ans;

}

mask |= 1 << (c - 'a');

}

return ans + 1;

}

};

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

}

};