Posts published in “Hashtable”

花花酱 LeetCode 2353. Design a Food Rating System

By zxi on March 29, 2025

Hashtable + TreeSet / OrderedSet

用了三个Hashtable…

菜名 -> 菜系
菜系 -> Treemap
菜名 -> 所在Treemap中的迭代器

每个菜系用一个TreeSet来保存从高到低的菜色排名，查询的时候只要拿出第一个就好了。

修改的时候，拿出迭代器，删除原来的评分，再把新的评分加入（别忘了更新迭代器）

时间复杂度：构造O(nlogn)，修改O(logn)，查询O(1)

空间复杂度：O(n)

class FoodRatings {

public:

FoodRatings(vector<string>& foods, vector<string>& cuisines, vector<int>& ratings) {

const int n = foods.size();

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

n_[foods[i]] = cuisines[i];

m_[foods[i]] = c_[cuisines[i]].emplace(-ratings[i], foods[i]).first;

}

void changeRating(string food, int newRating) {

const string& cuisine = n_[food];

c_[cuisine].erase(m_[food]);

m_[food] = c_[cuisine].emplace(-newRating, food).first;

}

string highestRated(string cuisine) {

return begin(c_[cuisine])->second;

}

private:

unordered_map<string, set<pair<int, string>>> c_; // cuisine -> {{-rating, name}}

unordered_map<string, string> n_; // food -> cuisine

unordered_map<string, set<pair<int, string>>::iterator> m_; // food -> set iterator

};

/**

* Your FoodRatings object will be instantiated and called as such:

* FoodRatings* obj = new FoodRatings(foods, cuisines, ratings);

* obj->changeRating(food,newRating);

* string param_2 = obj->highestRated(cuisine);

花花酱 LeetCode 3242. Design Neighbor Sum Service

By zxi on March 29, 2025

青铜 Brute Force：每次需要花费O(n*n)的时间去查找query所在的格子，求和是O(1)。总的时间复杂度达到O(n^4)，肯定会超时。

白银 Hashtable：由于所有元素的值的唯一的，我们可以使用hashtable（或者数组）来记录value所在的格子坐标，这样每次Query都是O(1)时间。
时间复杂度：初始化O(n^2)，query O(1)。
空间复杂度：O(n^2)

class NeighborSum {

public:

NeighborSum(vector<vector<int>>& grid):

n_(grid.size()), g_(&grid), xy_(n_ * n_) {

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

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

xy_[grid[i][j]] = {j, i};

}

int adjacentSum(int value) {

auto [x, y] = xy_[value];

return val(x, y - 1) + val(x, y + 1) + val(x + 1, y) + val(x - 1, y);

}

int diagonalSum(int value) {

auto [x, y] = xy_[value];

return val(x - 1, y - 1) + val(x - 1, y + 1) + val(x + 1, y - 1) + val(x + 1, y + 1);

}

private:

inline int val(int x, int y) const {

if (x < 0 || x >= n_ || y < 0 || y >= n_) return 0;

return (*g_)[y][x];

}

int n_;

vector<vector<int>>* g_;

vector<pair<int, int>> xy_;

};

黄金 Precompute：在初始化的时候顺便求合，开两个数组一个存上下左右的，一个存对角线的。query的时候直接返回答案就可以了。
时间复杂度和白银是一样的，但会快一些（省去了求合的过程）。

class NeighborSum {

public:

NeighborSum(vector<vector<int>>& grid) {

int n = grid.size();

adj_.resize(n * n);

dia_.resize(n * n);

auto v = [&](int x, int y) -> int {

if (x < 0 || x >= n || y < 0 || y >= n)

return 0;

return grid[y][x];

};

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

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

adj_[grid[y][x]] = v(x, y - 1) + v(x, y + 1) + v(x + 1, y) + v(x - 1, y);

dia_[grid[y][x]] = v(x - 1, y - 1) + v(x - 1, y + 1) + v(x + 1, y - 1) + v(x + 1, y + 1);

}

int adjacentSum(int value) {

return adj_[value];

}

int diagonalSum(int value) {

return dia_[value];

}

private:

vector<int> adj_;

vector<int> dia_;

};

花花酱 LeetCode 3005. Count Elements With Maximum Frequency

By zxi on January 15, 2024

You are given an array nums consisting of positive integers.

Return the total frequencies of elements in nums such that those elements all have the maximum frequency.

The frequency of an element is the number of occurrences of that element in the array.

Example 1:

Input: nums = [1,2,2,3,1,4]
Output: 4
Explanation: The elements 1 and 2 have a frequency of 2 which is the maximum frequency in the array.
So the number of elements in the array with maximum frequency is 4.

Example 2:

Input: nums = [1,2,3,4,5]
Output: 5
Explanation: All elements of the array have a frequency of 1 which is the maximum.
So the number of elements in the array with maximum frequency is 5.

Constraints:

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

Solution: Hashtable

Use a hashtable to store the frequency of each element, and compare it with a running maximum frequency. Reset answer if current frequency is greater than maximum frequency. Increment the answer if current frequency is equal to the maximum frequency.

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

C++

// Author: Huahua

class Solution {

public:

int maxFrequencyElements(vector<int>& nums) {

unordered_map<int, int> m;

int freq = 0;

int ans = 0;

for (int x : nums) {

if (++m[x] > freq)

freq = m[x], ans = 0;

if (m[x] == freq)

ans += m[x];

}

return ans;

}

};

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

}

};