Posts tagged as “hashtable”

花花酱 LeetCode 2829. Determine the Minimum Sum of a k-avoiding Array

By zxi on August 26, 2023

You are given two integers, n and k.

An array of distinct positive integers is called a k-avoiding array if there does not exist any pair of distinct elements that sum to k.

Return the minimum possible sum of a k-avoiding array of length n.

Example 1:

Input: n = 5, k = 4
Output: 18
Explanation: Consider the k-avoiding array [1,2,4,5,6], which has a sum of 18.
It can be proven that there is no k-avoiding array with a sum less than 18.

Example 2:

Input: n = 2, k = 6
Output: 3
Explanation: We can construct the array [1,2], which has a sum of 3.
It can be proven that there is no k-avoiding array with a sum less than 3.

Constraints:

1 <= n, k <= 50

Solution 1: Greedy + HashTable

Always choose the smallest possible number starting from 1.

Add all chosen numbers into a hashtable. For a new candidate i, check whether k – i is already in the hashtable.

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

C++

// Author: Huahua

class Solution {

public:

int minimumSum(int n, int k) {

int sum = 0;

unordered_set<int> s;

for (int i = 1; s.size() != n; ++i) {

if (s.count(k - i)) continue;

sum += i;

s.insert(i);

}

return sum;

}

};

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

}

};