Posts tagged as “range query”

花花酱 LeetCode 2407. Longest Increasing Subsequence II

By zxi on September 11, 2022

You are given an integer array nums and an integer k.

Find the longest subsequence of nums that meets the following requirements:

The subsequence is strictly increasing and
The difference between adjacent elements in the subsequence is at most k.

Return the length of the longest subsequence that meets the requirements.

A subsequence is an array that can be derived from another array by deleting some or no elements without changing the order of the remaining elements.

Example 1:

Input: nums = [4,2,1,4,3,4,5,8,15], k = 3
Output: 5
Explanation:
The longest subsequence that meets the requirements is [1,3,4,5,8].
The subsequence has a length of 5, so we return 5.
Note that the subsequence [1,3,4,5,8,15] does not meet the requirements because 15 - 8 = 7 is larger than 3.

Example 2:

Input: nums = [7,4,5,1,8,12,4,7], k = 5
Output: 4
Explanation:
The longest subsequence that meets the requirements is [4,5,8,12].
The subsequence has a length of 4, so we return 4.

Example 3:

Input: nums = [1,5], k = 1
Output: 1
Explanation:
The longest subsequence that meets the requirements is [1].
The subsequence has a length of 1, so we return 1.

Constraints:

1 <= nums.length <= 10⁵
1 <= nums[i], k <= 10⁵

Solution: DP + Segment Tree | Max range query

Let dp[i] := length of LIS end with number i.
dp[i] = 1 + max(dp[i-k:i])

Naive dp takes O(n*k) time which will cause TLE.

We can use segment tree to speed up the max range query to log(m), where m is the max value of the array.

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

C++

// Author: Huahua

class Solution {

public:

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

const int n = *max_element(begin(nums), end(nums));

vector<int> dp(2 * (n + 1));

auto query = [&](int l, int r) -> int {

int ans = 0;

for (l += n, r += n; l < r; l >>= 1, r >>= 1) {

if (l & 1) ans = max(ans, dp[l++]);

if (r & 1) ans = max(ans, dp[--r]);

}

return ans;

};

auto update = [&](int i, int val) -> void {

dp[i += n] = val;

while (i > 1) {

i >>= 1;

dp[i] = max(dp[i * 2], dp[i * 2 + 1]);

}

};

int ans = 0;

for (int x : nums) {

int cur = 1 + query(max(1, x - k), x);

update(x, cur);

ans = max(ans, cur);

}

return ans;

}

};

花花酱 LeetCode 2106. Maximum Fruits Harvested After at Most K Steps

By zxi on December 12, 2021

Problem

Solution 1: Range sum query

Assuming we can collect fruits in range [l, r], we need a fast query to compute the sum of those fruits.

Given startPos and k, we have four options:
1. move i steps to the left
2. move i steps to the left and k – i steps to the right.
3. move i steps to the right
4. move i steps to the right and k – i steps to the left.

We enumerate i steps and calculate maximum range [l, r] covered by each option, and collect all the fruit in that range.

Time complexity: O(m + k)
Space complexity: O(m)
where m = max(max(pos), startPos)

C++

// Author: Huahua

class Solution {

public:

int maxTotalFruits(vector<vector<int>>& fruits, int startPos, int k) {

const int m = max(startPos, (*max_element(begin(fruits), end(fruits)))[0]);

vector<int> sums(m + 2);

for (int i = 0, j = 0; i <= m; ++i) {

sums[i + 1] += sums[i];

while (j < fruits.size() && fruits[j][0] == i)

sums[i + 1] += fruits[j++][1];

}

int ans = 0;

for (int s = 0; s <= k; ++s) {

if (startPos - s >= 0) {

int l = startPos - s;

int r = min(max(startPos, l + (k - s)), m);

ans = max(ans, sums[r + 1] - sums[l]);

}

if (startPos + s <= m) {

int r = startPos + s;

int l = max(0, min(startPos, r - (k - s)));

ans = max(ans, sums[r + 1] - sums[l]);

}

return ans;

}

};

Solution 2: Sliding Window

Maintain a window [l, r] such that the steps to cover [l, r] from startPos is less or equal to k.

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

C++

// Author: Huahua

class Solution {

public:

int maxTotalFruits(vector<vector<int>>& fruits, int startPos, int k) {

auto steps = [&](int l, int r) {

if (r <= startPos)

return startPos - l;

else if (l >= startPos)

return r - startPos;

else

return min(startPos + r - 2 * l, 2 * r - startPos - l);

};

int ans = 0;

for (int r = 0, l = 0, cur = 0; r < fruits.size(); ++r) {

cur += fruits[r][1];

while (l <= r && steps(fruits[l][0], fruits[r][0]) > k)

cur -= fruits[l++][1];

ans = max(ans, cur);

}

return ans;

}

};

花花酱 LeetCode 2055. Plates Between Candles

By zxi on November 3, 2021

There is a long table with a line of plates and candles arranged on top of it. You are given a 0-indexed string s consisting of characters '*' and '|' only, where a '*' represents a plate and a '|' represents a candle.

You are also given a 0-indexed 2D integer array queries where queries[i] = [left_i, right_i] denotes the substring s[left_i...right_i] (inclusive). For each query, you need to find the number of plates between candles that are in the substring. A plate is considered between candles if there is at least one candle to its left and at least one candle to its right in the substring.

For example, s = "||**||**|*", and a query [3, 8] denotes the substring "*||**|". The number of plates between candles in this substring is 2, as each of the two plates has at least one candle in the substring to its left and right.

Return an integer array answer where answer[i] is the answer to the i^th query.

Example 1:

Input: s = "**|**|***|", queries = [[2,5],[5,9]]
Output: [2,3]
Explanation:
- queries[0] has two plates between candles.
- queries[1] has three plates between candles.

Example 2:

Input: s = "***|**|*****|**||**|*", queries = [[1,17],[4,5],[14,17],[5,11],[15,16]]
Output: [9,0,0,0,0]
Explanation:
- queries[0] has nine plates between candles.
- The other queries have zero plates between candles.

Constraints:

3 <= s.length <= 10⁵
s consists of '*' and '|' characters.
1 <= queries.length <= 10⁵
queries[i].length == 2
0 <= left_i <= right_i < s.length

Solution: Binary Search

Store the indices of all candles into an array idx.

For each query q:
1. Find the left most candle whose index is greater or equal to left as l.
2. Find the left most candle whose index is greater than right, choose the previous candle as r.

[idx[l], idx[r]] is the range that are elements between two candles , there are (idx[r] – idx[l] + 1) elements in total and there are (r – l + 1) candles in the range. So the number of plates is (idx[r] – idx[l] + 1) – (r – l + 1) or (idx[r] – idx[l]) – (r – l)

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

C++

// Author: huahua

class Solution {

public:

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

vector<int> idx;

for (size_t i = 0; i < s.size(); ++i)

if (s[i] == '|') idx.push_back(i);

vector<int> ans;

for (const auto& q : queries) {

const int l = lower_bound(begin(idx), end(idx), q[0]) - begin(idx);

const int r = upper_bound(begin(idx), end(idx), q[1]) - begin(idx) - 1;

ans.push_back(l >= r ? 0 : (idx[r] - idx[l]) - (r - l));

}

return ans;

}

};

花花酱 LeetCode 1906. Minimum Absolute Difference Queries

By zxi on August 15, 2021

The minimum absolute difference of an array a is defined as the minimum value of |a[i] - a[j]|, where 0 <= i < j < a.length and a[i] != a[j]. If all elements of a are the same, the minimum absolute difference is -1.

For example, the minimum absolute difference of the array [5,2,3,7,2] is |2 - 3| = 1. Note that it is not 0 because a[i] and a[j] must be different.

You are given an integer array nums and the array queries where queries[i] = [l_i, r_i]. For each query i, compute the minimum absolute difference of the subarray nums[l_i...r_i] containing the elements of nums between the 0-based indices l_i and r_i (inclusive).

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

A subarray is a contiguous sequence of elements in an array.

The value of |x| is defined as:

x if x >= 0.
-x if x < 0.

Example 1:

Input: nums = [1,3,4,8], queries = [[0,1],[1,2],[2,3],[0,3]]
Output: [2,1,4,1]
Explanation: The queries are processed as follows:
- queries[0] = [0,1]: The subarray is [1,3] and the minimum absolute difference is |1-3| = 2.
- queries[1] = [1,2]: The subarray is [3,4] and the minimum absolute difference is |3-4| = 1.
- queries[2] = [2,3]: The subarray is [4,8] and the minimum absolute difference is |4-8| = 4.
- queries[3] = [0,3]: The subarray is [1,3,4,8] and the minimum absolute difference is |3-4| = 1.

Example 2:

Input: nums = [4,5,2,2,7,10], queries = [[2,3],[0,2],[0,5],[3,5]]
Output: [-1,1,1,3]
Explanation: The queries are processed as follows:
- queries[0] = [2,3]: The subarray is [2,2] and the minimum absolute difference is -1 because all the
  elements are the same.
- queries[1] = [0,2]: The subarray is [4,5,2] and the minimum absolute difference is |4-5| = 1.
- queries[2] = [0,5]: The subarray is [4,5,2,2,7,10] and the minimum absolute difference is |4-5| = 1.
- queries[3] = [3,5]: The subarray is [2,7,10] and the minimum absolute difference is |7-10| = 3.

Constraints:

2 <= nums.length <= 10⁵
1 <= nums[i] <= 100
1 <= queries.length <= 2 * 10⁴
0 <= l_i < r_i < nums.length

Solution: Binary Search

Since the value range of num is quiet small [1~100], we can store the indices for each value.
[2, 1, 2, 2, 3] => {1: [1], 2: [0, 2, 3]: 3: [4]}.

For each query, we try all possible value b. Check whether b is the query range using binary search, we also keep tracking the previous available value a, ans will be min{b – a}.

Time complexity: O(n + q * 100 * log(n))
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

vector<int> minDifference(vector<int>& nums, vector<vector<int>>& queries) {

constexpr int kMax = 100;

const int n = nums.size();

vector<vector<int>> idx(kMax + 1);

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

idx[nums[i]].push_back(i);

vector<int> ans;

for (const auto& q: queries) {

int diff = INT_MAX;

for (int a = 0, b = 1; b <= kMax; ++b) {

auto it = lower_bound(begin(idx[b]), end(idx[b]), q[0]);

if (it == end(idx[b]) || *it > q[1]) continue;

if (a) diff = min(diff, b - a);

a = b;

}

ans.push_back(diff == INT_MAX ? -1 : diff);

}

return ans;

}

};

花花酱 LeetCode 1292. Maximum Side Length of a Square with Sum Less than or Equal to Threshold

By zxi on December 17, 2019

Given a m x n matrix mat and an integer threshold. Return the maximum side-length of a square with a sum less than or equal to threshold or return 0 if there is no such square.

Example 1:

Input: mat = [[1,1,3,2,4,3,2],[1,1,3,2,4,3,2],[1,1,3,2,4,3,2]], threshold = 4
Output: 2
Explanation: The maximum side length of square with sum less than 4 is 2 as shown.

Example 2:

Input: mat = [[2,2,2,2,2],[2,2,2,2,2],[2,2,2,2,2],[2,2,2,2,2],[2,2,2,2,2]], threshold = 1
Output: 0

Example 3:

Input: mat = [[1,1,1,1],[1,0,0,0],[1,0,0,0],[1,0,0,0]], threshold = 6
Output: 3

Example 4:

Input: mat = [[18,70],[61,1],[25,85],[14,40],[11,96],[97,96],[63,45]], threshold = 40184
Output: 2

Constraints:

1 <= m, n <= 300
m == mat.length
n == mat[i].length
0 <= mat[i][j] <= 10000
0 <= threshold <= 10^5

Solution: DP + Brute Force

Precompute the sums of sub-matrixes whose left-top corner is at (0,0).

Try all possible left-top corner and sizes.

Time complexity: O(m*n*min(m,n))
Space complexity: O(m*n)

C++

// Author: Huahua, 148 ms

class Solution {

public:

int maxSideLength(vector<vector<int>>& mat, int threshold) {

const int m = mat.size();

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

vector<vector<int>> dp(m + 1, vector<int>(n + 1));

for (int y = 1; y <= m; ++y)

for (int x = 1; x <= n; ++x)

dp[y][x] = dp[y][x - 1] + dp[y - 1][x] - dp[y - 1][x - 1] + mat[y - 1][x - 1];

auto rangeSum = [&](int x1, int y1, int x2, int y2) {

return dp[y2][x2] - dp[y2][x1 - 1] - dp[y1 - 1][x2] + dp[y1 - 1][x1 - 1];

};

int ans = 0;

for (int y = 1; y <= m; ++y)

for (int x = 1; x <= n; ++x)

for (int k = 0; y + k <= m && x + k <= n; ++k) {

if (rangeSum(x, y, x + k, y + k) > threshold) break;

ans = max(ans, k + 1);

}

return ans;

}

};

Solution 2: Binary Search

Search for the smallest size k that is greater than the threshold, ans = k – 1.

C++

// Author: Huahua, 116 ms

class Solution {

public:

int maxSideLength(vector<vector<int>>& mat, int threshold) {

const int m = mat.size();

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

vector<vector<int>> dp(m + 1, vector<int>(n + 1));

for (int y = 1; y <= m; ++y)

for (int x = 1; x <= n; ++x)

dp[y][x] = dp[y][x - 1] + dp[y - 1][x] - dp[y - 1][x - 1] + mat[y - 1][x - 1];

auto rangeSum = [&](int x1, int y1, int x2, int y2) {

return dp[y2][x2] - dp[y2][x1 - 1] - dp[y1 - 1][x2] + dp[y1 - 1][x1 - 1];

};

int ans = 0;

for (int y = 1; y <= m; ++y)

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

int l = 0;

int r = min(m - y, n - x) + 1;

while (l < r) {

int m = l + (r - l) / 2;

// Find smllest l that > threshold, ans = (l + 1) - 1

if (rangeSum(x, y, x + m, y + m) > threshold)

r = m;

else

l = m + 1;

}

ans = max(ans, (l + 1) - 1);

}

return ans;

}

};

Solution 3: Bounded Search

Time complexity: O(m*n + min(m,n))

C++

// Author: Huahua, 148 ms

class Solution {

public:

int maxSideLength(vector<vector<int>>& mat, int threshold) {

const int m = mat.size();

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

vector<vector<int>> dp(m + 1, vector<int>(n + 1));

for (int y = 1; y <= m; ++y)

for (int x = 1; x <= n; ++x)

dp[y][x] = dp[y][x - 1] + dp[y - 1][x] - dp[y - 1][x - 1] + mat[y - 1][x - 1];

auto rangeSum = [&](int x1, int y1, int x2, int y2) {

return dp[y2][x2] - dp[y2][x1 - 1] - dp[y1 - 1][x2] + dp[y1 - 1][x1 - 1];

};

int ans = 0;

for (int y = 1; y <= m; ++y)

for (int x = 1; x <= n; ++x)

for (int k = ans; y + k <= m && x + k <= n; ++k) {

if (rangeSum(x, y, x + k, y + k) > threshold) break;

ans = max(ans, k + 1);

}

return ans;

}

};