Posts published in “Hashtable”

花花酱 LeetCode 2122. Recover the Original Array

By zxi on December 26, 2021

Alice had a 0-indexed array arr consisting of n positive integers. She chose an arbitrary positive integer k and created two new 0-indexed integer arrays lower and higher in the following manner:

lower[i] = arr[i] - k, for every index i where 0 <= i < n
higher[i] = arr[i] + k, for every index i where 0 <= i < n

Unfortunately, Alice lost all three arrays. However, she remembers the integers that were present in the arrays lower and higher, but not the array each integer belonged to. Help Alice and recover the original array.

Given an array nums consisting of 2n integers, where exactly n of the integers were present in lower and the remaining in higher, return the original array arr. In case the answer is not unique, return any valid array.

Note: The test cases are generated such that there exists at least one valid array arr.

Example 1:

Input: nums = [2,10,6,4,8,12]
Output: [3,7,11]
Explanation:
If arr = [3,7,11] and k = 1, we get lower = [2,6,10] and higher = [4,8,12].
Combining lower and higher gives us [2,6,10,4,8,12], which is a permutation of nums.
Another valid possibility is that arr = [5,7,9] and k = 3. In that case, lower = [2,4,6] and higher = [8,10,12].

Example 2:

Input: nums = [1,1,3,3]
Output: [2,2]
Explanation:
If arr = [2,2] and k = 1, we get lower = [1,1] and higher = [3,3].
Combining lower and higher gives us [1,1,3,3], which is equal to nums.
Note that arr cannot be [1,3] because in that case, the only possible way to obtain [1,1,3,3] is with k = 0.
This is invalid since k must be positive.

Example 3:

Input: nums = [5,435]
Output: [220]
Explanation:
The only possible combination is arr = [220] and k = 215. Using them, we get lower = [5] and higher = [435].

Constraints:

2 * n == nums.length
1 <= n <= 1000
1 <= nums[i] <= 10⁹
The test cases are generated such that there exists at least one valid array arr.

Solution: Try all possible k

Sort the array, we know that the smallest number nums[0] is org[0] – k, org[0] + k (nums[0] + 2k) must exist in nums. We try all possible ks. k = (nums[i] – nums[0]) / 2.

Then we iterate the sorted nums array as low, and see whether we can find low + 2k as high using a dynamic hashtable.

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

C++

// Author: Huahua

class Solution {

public:

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

const int n = nums.size();

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

unordered_map<int, int> m;

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

auto check = [&](int k) -> vector<int> {

vector<int> ans;

unordered_map<int, int> cur(m);

for (int x : nums) {

if (cur[x] == 0) continue;

--cur[x];

if (--cur[x + 2 * k] < 0) return {};

ans.push_back(x + k);

}

return ans;

};

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

if (nums[i] == nums[0] || (nums[i] - nums[0]) & 1) continue;

const int k = (nums[i] - nums[0]) / 2;

vector<int> ans = check(k);

if (!ans.empty()) return ans;

}

return {};

}

};

花花酱 LeetCode 2121. Intervals Between Identical Elements

By zxi on December 26, 2021

You are given a 0-indexed array of n integers arr.

The interval between two elements in arr is defined as the absolute difference between their indices. More formally, the interval between arr[i] and arr[j] is |i - j|.

Return an array intervals of length n where intervals[i] is the sum of intervals between arr[i] and each element in arr with the same value as arr[i].

Note: |x| is the absolute value of x.

Example 1:

Input: arr = [2,1,3,1,2,3,3]
Output: [4,2,7,2,4,4,5]
Explanation:
- Index 0: Another 2 is found at index 4. |0 - 4| = 4
- Index 1: Another 1 is found at index 3. |1 - 3| = 2
- Index 2: Two more 3s are found at indices 5 and 6. |2 - 5| + |2 - 6| = 7
- Index 3: Another 1 is found at index 1. |3 - 1| = 2
- Index 4: Another 2 is found at index 0. |4 - 0| = 4
- Index 5: Two more 3s are found at indices 2 and 6. |5 - 2| + |5 - 6| = 4
- Index 6: Two more 3s are found at indices 2 and 5. |6 - 2| + |6 - 5| = 5

Example 2:

Input: arr = [10,5,10,10]
Output: [5,0,3,4]
Explanation:
- Index 0: Two more 10s are found at indices 2 and 3. |0 - 2| + |0 - 3| = 5
- Index 1: There is only one 5 in the array, so its sum of intervals to identical elements is 0.
- Index 2: Two more 10s are found at indices 0 and 3. |2 - 0| + |2 - 3| = 3
- Index 3: Two more 10s are found at indices 0 and 2. |3 - 0| + |3 - 2| = 4

Constraints:

n == arr.length
1 <= n <= 10⁵
1 <= arr[i] <= 10⁵

Solution: Math / Hashtable + Prefix Sum

For each arr[i], suppose it occurs in the array of total c times, among which k of them are in front of it and c – k – 1 of them are after it. Then the total sum intervals:
(i – j₁) + (i – j₂) + … + (i – j_k) + (j_k+1-i) + (j_k+2-i) + … + (j_c-i)
<=> k * i – sum(j₁~j_k) + sum(j_k+1~j_c) – (c – k – 1) * i

Use a hashtable to store the indies of each unique number in the array and compute the prefix sum for fast range sum query.

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

C++

// Author: Huahua

class Solution {

public:

vector<long long> getDistances(vector<int>& arr) {

const int n = arr.size();

unordered_map<int, vector<long long>> m;

vector<int> pos(n);

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

m[arr[i]].push_back(i);

pos[i] = m[arr[i]].size() - 1;

}

for (auto& [k, idx] : m)

partial_sum(begin(idx), end(idx), begin(idx));

vector<long long> ans(n);

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

const auto& sums = m[arr[i]];

const long long k = pos[i];

const long long c = sums.size();

if (k > 0) ans[i] += k * i - sums[k - 1];

if (k + 1 < c) ans[i] += (sums[c - 1] - sums[k]) - (c - k - 1) * i;

}

return ans;

}

};

花花酱 LeetCode 1915. Number of Wonderful Substrings

By zxi on December 25, 2021

A wonderful string is a string where at most one letter appears an odd number of times.

For example, "ccjjc" and "abab" are wonderful, but "ab" is not.

Given a string word that consists of the first ten lowercase English letters ('a' through 'j'), return the number of wonderful non-empty substrings in word. If the same substring appears multiple times in word, then count each occurrence separately.

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

Example 1:

Input: word = "aba"
Output: 4
Explanation: The four wonderful substrings are underlined below:
- "aba" -> "a"
- "aba" -> "b"
- "aba" -> "a"
- "aba" -> "aba"

Example 2:

Input: word = "aabb"
Output: 9
Explanation: The nine wonderful substrings are underlined below:
- "aabb" -> "a"
- "aabb" -> "aa"
- "aabb" -> "aab"
- "aabb" -> "aabb"
- "aabb" -> "a"
- "aabb" -> "abb"
- "aabb" -> "b"
- "aabb" -> "bb"
- "aabb" -> "b"

Example 3:

Input: word = "he"
Output: 2
Explanation: The two wonderful substrings are underlined below:
- "he" -> "h"
- "he" -> "e"

Constraints:

1 <= word.length <= 10⁵
word consists of lowercase English letters from 'a' to 'j'.

Solution: Prefix Bitmask + Hashtable

Similar to 花花酱 LeetCode 1371. Find the Longest Substring Containing Vowels in Even Counts, we use a bitmask to represent the occurrence (odd or even) of each letter and use a hashtable to store the frequency of each bitmask seen so far.

1. “0000000000” means all letters occur even times.
2. “0000000101” means all letters occur even times expect letter ‘a’ and ‘c’ that occur odd times.

We scan the word from left to right and update the bitmask: bitmask ^= (1 << (c-‘a’)).
However, the bitmask only represents the state of the prefix, i.e. word[0:i], then how can we count substrings? The answer is hashtable. If the same bitmask occurs c times before, which means there are c indices that word[0~j1], word[0~j2], …, word[0~jc] have the same state as word[0~i] that means for word[j1+1~i], word[j2+1~i], …, word[jc+1~i], all letters occurred even times.
For the “at most one odd” case, we toggle each bit of the bitmask and check how many times it occurred before.

ans += freq[mask] + sum(freq[mask ^ (1 << i)] for i in range(k))

Time complexity: O(n*k)
Space complexity: O(2^k)
where k = j – a + 1 = 10

C++

// Author: Huahua

class Solution {

public:

long long wonderfulSubstrings(string word) {

constexpr int l = 'j' - 'a' + 1;

vector<int> count(1 << l);

count[0] = 1;

int mask = 0;

long long ans = 0;

for (char c : word) {

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

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

ans += count[mask ^ (1 << i)]; // one odd.

ans += count[mask]++; // all even.

}

return ans;

}

};

花花酱 LeetCode 835. Image Overlap

By zxi on December 23, 2021

You are given two images, img1 and img2, represented as binary, square matrices of size n x n. A binary matrix has only 0s and 1s as values.

We translate one image however we choose by sliding all the 1 bits left, right, up, and/or down any number of units. We then place it on top of the other image. We can then calculate the overlap by counting the number of positions that have a 1 in both images.

Note also that a translation does not include any kind of rotation. Any 1 bits that are translated outside of the matrix borders are erased.

Return the largest possible overlap.

Example 1:

Input: img1 = [[1,1,0],[0,1,0],[0,1,0]], img2 = [[0,0,0],[0,1,1],[0,0,1]]
Output: 3
Explanation: We translate img1 to right by 1 unit and down by 1 unit.

The number of positions that have a 1 in both images is 3 (shown in red).

Example 2:

Input: img1 = [[1]], img2 = [[1]]
Output: 1

Example 3:

Input: img1 = [[0]], img2 = [[0]]
Output: 0

Constraints:

n == img1.length == img1[i].length
n == img2.length == img2[i].length
1 <= n <= 30
img1[i][j] is either 0 or 1.
img2[i][j] is either 0 or 1.

Solution: Hashtable of offsets

Enumerate all pairs of 1 cells (x1, y1) (x2, y2), the key / offset will be ((x1-x2), (y1-y2)), i.e how should we shift the image to have those two cells overlapped. Use a counter to find the most common/best offset.

Time complexity: O(n⁴) Note: this is the same as brute force / simulation method if the matrix is dense.
Space complexity: O(n²)

C++

// Author: Huahua

class Solution {

public:

int largestOverlap(vector<vector<int>>& img1, vector<vector<int>>& img2) {

const int n = img1.size();

unordered_map<int, int> m;

for (int y1 = 0; y1 < n; ++y1)

for (int x1 = 0; x1 < n; ++x1)

if (img1[y1][x1])

for (int y2 = 0; y2 < n; ++y2)

for (int x2 = 0; x2 < n; ++x2)

if (img2[y2][x2])

++m[(x1 - x2) * 100 + (y1 - y2)];

int ans = 0;

for (const auto [key, count] : m)

ans = max(ans, count);

return ans;

}

};

花花酱 LeetCode 2103. Rings and Rods

By zxi on December 12, 2021

Problem

Solution: Hashset

Use 10 hashsets to track the status of each rod, check whether it contains three unique elements (R,G,B).

Time complexity: O(n)
Space complexity: O(10*3)

C++

// Author: Huahua

class Solution {

public:

int countPoints(string rings) {

constexpr int kRods = 10;

vector<unordered_set<char>> s(kRods);

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

s[rings[i + 1] - '0'].insert(rings[i]);

int ans = 0;

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

if (s[i].size() == 3)

++ans;

return ans;

}

};