Posts tagged as “hashtable”

花花酱 LeetCode 2661. First Completely Painted Row or Column

By zxi on April 30, 2023

You are given a 0-indexed integer array arr, and an m x n integer matrix mat. arr and mat both contain all the integers in the range [1, m * n].

Go through each index i in arr starting from index 0 and paint the cell in mat containing the integer arr[i].

Return the smallest index i at which either a row or a column will be completely painted in mat.

Example 1:

Input: arr = [1,3,4,2], mat = [[1,4],[2,3]]
Output: 2
Explanation: The moves are shown in order, and both the first row and second column of the matrix become fully painted at arr[2].

Example 2:

Input: arr = [2,8,7,4,1,3,5,6,9], mat = [[3,2,5],[1,4,6],[8,7,9]]
Output: 3
Explanation: The second column becomes fully painted at arr[3].

Constraints:

m == mat.length
n = mat[i].length
arr.length == m * n
1 <= m, n <= 10⁵
1 <= m * n <= 10⁵
1 <= arr[i], mat[r][c] <= m * n
All the integers of arr are unique.
All the integers of mat are unique.

Solution: Map + Counter

Use a map to store the position of each integer.

Use row counters and column counters to track how many elements have been painted.

Time complexity: O(m*n + m + n)
Space complexity: O(m*n + m + n)

C++

// Author: Huahua

class Solution {

public:

int firstCompleteIndex(vector<int>& arr, vector<vector<int>>& mat) {

const int m = mat.size();

const int n = mat[0].size();

vector<int> rows(m);

vector<int> cols(n);

vector<pair<int, int>> pos(m * n + 1);

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

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

pos[mat[i][j]] = {i, j};

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

auto [r, c] = pos[arr[i]];

if (++rows[r] == n) return i;

if (++cols[c] == m) return i;

}

return -1;

}

};

花花酱 LeetCode 2588. Count the Number of Beautiful Subarrays

By zxi on March 11, 2023

You are given a 0-indexed integer array nums. In one operation, you can:

Choose two different indices i and j such that 0 <= i, j < nums.length.
Choose a non-negative integer k such that the k^th bit (0-indexed) in the binary representation of nums[i] and nums[j] is 1.
Subtract 2^k from nums[i] and nums[j].

A subarray is beautiful if it is possible to make all of its elements equal to 0 after applying the above operation any number of times.

Return the number of beautiful subarrays in the array nums.

A subarray is a contiguous non-empty sequence of elements within an array.

Example 1:

Input: nums = [4,3,1,2,4]
Output: 2
Explanation: There are 2 beautiful subarrays in nums: [4,3,1,2,4] and [4,3,1,2,4].
- We can make all elements in the subarray [3,1,2] equal to 0 in the following way:
  - Choose [3, 1, 2] and k = 1. Subtract 2¹ from both numbers. The subarray becomes [1, 1, 0].
  - Choose [1, 1, 0] and k = 0. Subtract 2⁰ from both numbers. The subarray becomes [0, 0, 0].
- We can make all elements in the subarray [4,3,1,2,4] equal to 0 in the following way:
  - Choose [4, 3, 1, 2, 4] and k = 2. Subtract 2² from both numbers. The subarray becomes [0, 3, 1, 2, 0].
  - Choose [0, 3, 1, 2, 0] and k = 0. Subtract 2⁰ from both numbers. The subarray becomes [0, 2, 0, 2, 0].
  - Choose [0, 2, 0, 2, 0] and k = 1. Subtract 2¹ from both numbers. The subarray becomes [0, 0, 0, 0, 0].

Example 2:

Input: nums = [1,10,4]
Output: 0
Explanation: There are no beautiful subarrays in nums.

Constraints:

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

Solution: Hashtable + Prefix XOR

The problem is asking to find # of subarrays whose element wise xor is 0. We can use a hashtable to store the frequency of each prefix xor value, which reduces this problem to # of Subarray sum equal to k.

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

C++

// Author: Huahua

class Solution {

public:

long long beautifulSubarrays(vector<int>& nums) {

long long ans = 0;

unordered_map<int, int> m{{0, 1}};

int x = 0;

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

x ^= nums[i];

ans += m[x];

m[x] += 1;

}

return ans;

}

};

花花酱 LeetCode 2564. Substring XOR Queries

By zxi on February 12, 2023

You are given a binary string s, and a 2D integer array queries where queries[i] = [first_i, second_i].

For the i^th query, find the shortest substring of s whose decimal value, val, yields second_i when bitwise XORed with first_i. In other words, val ^ first_i == second_i.

The answer to the i^th query is the endpoints (0-indexed) of the substring [left_i, right_i] or [-1, -1] if no such substring exists. If there are multiple answers, choose the one with the minimum left_i.

Return an array ans where ans[i] = [left_i, right_i] is the answer to the i^th query.

A substring is a contiguous non-empty sequence of characters within a string.

Example 1:

Input: s = "101101", queries = [[0,5],[1,2]]
Output: [[0,2],[2,3]]
Explanation: For the first query the substring in range [0,2] is "101" which has a decimal value of 5, and 5 ^ 0 = 5, hence the answer to the first query is [0,2]. In the second query, the substring in range [2,3] is "11", and has a decimal value of 3, and 3 ^ 1 = 2. So, [2,3] is returned for the second query.

Example 2:

Input: s = "0101", queries = [[12,8]]
Output: [[-1,-1]]
Explanation: In this example there is no substring that answers the query, hence [-1,-1] is returned.

Example 3:

Input: s = "1", queries = [[4,5]]
Output: [[0,0]]
Explanation: For this example, the substring in range [0,0] has a decimal value of 1, and 1 ^ 4 = 5. So, the answer is [0,0].

Constraints:

1 <= s.length <= 10⁴
s[i] is either '0' or '1'.
1 <= queries.length <= 10⁵
0 <= first_i, second_i <= 10⁹

Solution: Pre-compute

We can pre-compute all possible substrings

Time complexity: O(n*32 + m)
Space complexity: O(n*32)

C++

// Author: Huahua

class Solution {

public:

vector<vector<int>> substringXorQueries(string s, vector<vector<int>>& queries) {

unordered_map<int, vector<int>> m;

const int l = s.length();

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

if (s[i] == '0') {

if (!m.count(0)) m[0] = {i, i};

continue;

}

for (int j = 0, cur = 0; j < 32 && i + j < l; ++j) {

cur = (cur << 1) | (s[i + j] - '0');

if (!m.count(cur))

m[cur] = {i, i + j};

}

vector<vector<int>> ans;

for (const auto& q : queries) {

int x = q[0] ^ q[1];

if (m.count(x))

ans.push_back(m[x]);

else

ans.push_back({-1, -1});

}

return ans;

}

};

花花酱 LeetCode 2475. Number of Unequal Triplets in Array

By zxi on November 21, 2022

You are given a 0-indexed array of positive integers nums. Find the number of triplets (i, j, k) that meet the following conditions:

0 <= i < j < k < nums.length
nums[i], nums[j], and nums[k] are pairwise distinct.
- In other words, nums[i] != nums[j], nums[i] != nums[k], and nums[j] != nums[k].

Return the number of triplets that meet the conditions.

Example 1:

Input: nums = [4,4,2,4,3]
Output: 3
Explanation: The following triplets meet the conditions:
- (0, 2, 4) because 4 != 2 != 3
- (1, 2, 4) because 4 != 2 != 3
- (2, 3, 4) because 2 != 4 != 3
Since there are 3 triplets, we return 3.
Note that (2, 0, 4) is not a valid triplet because 2 > 0.

Example 2:

Input: nums = [1,1,1,1,1]
Output: 0
Explanation: No triplets meet the conditions so we return 0.

Constraints:

3 <= nums.length <= 100
1 <= nums[i] <= 1000

Solution 1: Brute Force

Enumerate i, j, k.

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

C++

// Author: Huahua

class Solution {

public:

int unequalTriplets(vector<int>& nums) {

int ans = 0;

const int n = nums.size();

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

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

for (int k = j + 1; k < n; ++k)

if (nums[i] != nums[j] && nums[j] != nums[k] && nums[i] != nums[k])

++ans;

return ans;

}

};

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

}

};