Posts tagged as “precompute”

花花酱 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 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 2420. Find All Good Indices

By zxi on September 26, 2022

You are given a 0-indexed integer array nums of size n and a positive integer k.

We call an index i in the range k <= i < n - k good if the following conditions are satisfied:

The k elements that are just before the index i are in non-increasing order.
The k elements that are just after the index i are in non-decreasing order.

Return an array of all good indices sorted in increasing order.

Example 1:

Input: nums = [2,1,1,1,3,4,1], k = 2
Output: [2,3]
Explanation: There are two good indices in the array:
- Index 2. The subarray [2,1] is in non-increasing order, and the subarray [1,3] is in non-decreasing order.
- Index 3. The subarray [1,1] is in non-increasing order, and the subarray [3,4] is in non-decreasing order.
Note that the index 4 is not good because [4,1] is not non-decreasing.

Example 2:

Input: nums = [2,1,1,2], k = 2
Output: []
Explanation: There are no good indices in this array.

Constraints:

n == nums.length
3 <= n <= 10⁵
1 <= nums[i] <= 10⁶
1 <= k <= n / 2

Solution: Prefix Sum

Let before[i] = length of longest non-increasing subarray ends of nums[i].
Let after[i] = length of longest non-decreasing subarray ends of nums[i].

An index is good if nums[i – 1] >= k and nums[i + k] >= k

Time complexity: O(n + (n – 2*k))
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

vector<int> goodIndices(vector<int>& nums, int k) {

const int n = nums.size();

vector<int> before(n, 1);

vector<int> after(n, 1);

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

if (nums[i] <= nums[i - 1])

before[i] = before[i - 1] + 1;

if (nums[i] >= nums[i - 1])

after[i] = after[i - 1] + 1;

}

vector<int> ans;

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

if (before[i - 1] >= k && after[i + k] >= k)

ans.push_back(i);

}

return ans;

}

};

花花酱 LeetCode 2155. All Divisions With the Highest Score of a Binary Array

By zxi on February 4, 2022

You are given a 0-indexed binary array nums of length n. nums can be divided at index i (where 0 <= i <= n) into two arrays (possibly empty) nums_left and nums_right:

nums_left has all the elements of nums between index 0 and i - 1 (inclusive), while nums_right has all the elements of nums between index i and n - 1 (inclusive).
If i == 0, nums_left is empty, while nums_right has all the elements of nums.
If i == n, nums_left has all the elements of nums, while nums_right is empty.

The division score of an index i is the sum of the number of 0‘s in nums_left and the number of 1‘s in nums_right.

Return all distinct indices that have the highest possible division score. You may return the answer in any order.

Example 1:

Input: nums = [0,0,1,0]
Output: [2,4]
Explanation: Division at index
- 0: nums_left is []. nums_right is [0,0,1,0]. The score is 0 + 1 = 1.
- 1: nums_left is [0]. nums_right is [0,1,0]. The score is 1 + 1 = 2.
- 2: nums_left is [0,0]. nums_right is [1,0]. The score is 2 + 1 = 3.
- 3: nums_left is [0,0,1]. nums_right is [0]. The score is 2 + 0 = 2.
- 4: nums_left is [0,0,1,0]. nums_right is []. The score is 3 + 0 = 3.
Indices 2 and 4 both have the highest possible division score 3.
Note the answer [4,2] would also be accepted.

Example 2:

Input: nums = [0,0,0]
Output: [3]
Explanation: Division at index
- 0: nums_left is []. nums_right is [0,0,0]. The score is 0 + 0 = 0.
- 1: nums_left is [0]. nums_right is [0,0]. The score is 1 + 0 = 1.
- 2: nums_left is [0,0]. nums_right is [0]. The score is 2 + 0 = 2.
- 3: nums_left is [0,0,0]. nums_right is []. The score is 3 + 0 = 3.
Only index 3 has the highest possible division score 3.

Example 3:

Input: nums = [1,1]
Output: [0]
Explanation: Division at index
- 0: nums_left is []. nums_right is [1,1]. The score is 0 + 2 = 2.
- 1: nums_left is [1]. nums_right is [1]. The score is 0 + 1 = 1.
- 2: nums_left is [1,1]. nums_right is []. The score is 0 + 0 = 0.
Only index 0 has the highest possible division score 2.

Constraints:

n == nums.length
1 <= n <= 10⁵
nums[i] is either 0 or 1.

Solution: Precompute + Prefix Sum

Count how many ones in the array, track the prefix sum to compute score for each index in O(1).

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

C++

// Author: Huahua

class Solution {

public:

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

const int n = nums.size();

const int t = accumulate(begin(nums), end(nums), 0);

vector<int> ans;

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

const int s = (i - p) + (t - p);

if (s > b) {

b = s; ans.clear();

}

if (s == b) ans.push_back(i);

if (i != n) p += nums[i];

}

return ans;

}

};