Posts tagged as “sliding window”

花花酱 LeetCode 1343. Number of Sub-arrays of Size K and Average Greater than or Equal to Threshold

By zxi on February 13, 2020

Given an array of integers arr and two integers k and threshold.

Return the number of sub-arrays of size k and average greater than or equal to threshold.

Example 1:

Input: arr = [2,2,2,2,5,5,5,8], k = 3, threshold = 4
Output: 3
Explanation: Sub-arrays [2,5,5],[5,5,5] and [5,5,8] have averages 4, 5 and 6 respectively. All other sub-arrays of size 3 have averages less than 4 (the threshold).

Example 2:

Input: arr = [1,1,1,1,1], k = 1, threshold = 0
Output: 5

Example 3:

Input: arr = [11,13,17,23,29,31,7,5,2,3], k = 3, threshold = 5
Output: 6
Explanation: The first 6 sub-arrays of size 3 have averages greater than 5. Note that averages are not integers.

Example 4:

Input: arr = [7,7,7,7,7,7,7], k = 7, threshold = 7
Output: 1

Example 5:

Input: arr = [4,4,4,4], k = 4, threshold = 1
Output: 1

Constraints:

1 <= arr.length <= 10^5
1 <= arr[i] <= 10^4
1 <= k <= arr.length
0 <= threshold <= 10^4

Solution: Sliding Window

Window size = k
Maintain the sum of the window
Check sum >= threshold * k

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

C++

// Author: Huahua

class Solution {

public:

int numOfSubarrays(vector<int>& arr, int k, int threshold) {

int ans = 0;

int sum = 0;

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

sum += arr[i];

if (i + 1 >= k) {

if (threshold * k <= sum) ++ans;

sum -= arr[i + 1 - k];

}

return ans;

}

};

花花酱 LeetCode 1208. Get Equal Substrings Within Budget

By zxi on September 29, 2019

You are given two strings s and t of the same length. You want to change s to t. Changing the i-th character of s to i-th character of t costs |s[i] - t[i]| that is, the absolute difference between the ASCII values of the characters.

You are also given an integer maxCost.

Return the maximum length of a substring of s that can be changed to be the same as the corresponding substring of twith a cost less than or equal to maxCost.

If there is no substring from s that can be changed to its corresponding substring from t, return 0.

Example 1:

Input: s = "abcd", t = "bcdf", cost = 3
Output: 3
Explanation: "abc" of s can change to "bcd". That costs 3, so the maximum length is 3.

Example 2:

Input: s = "abcd", t = "cdef", cost = 3
Output: 1
Explanation: Each charactor in s costs 2 to change to charactor in t, so the maximum length is 1.

Example 3:

Input: s = "abcd", t = "acde", cost = 0
Output: 1
Explanation: You can't make any change, so the maximum length is 1.

Constraints:

1 <= s.length, t.length <= 10^5
0 <= maxCost <= 10^6
s and t only contain lower case English letters.

Solution 1: Binary Search

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

C++

// Author: Huahua

class Solution {

public:

int equalSubstring(string s, string t, int maxCost) {

const int n = s.length();

vector<int> c(n + 1);

auto cit = begin(c) + 1;

int ans = 0;

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

*cit = c[i] + abs(s[i] - t[i]);

int len = cit - lower_bound(begin(c), cit, *cit - maxCost);

ans = max(ans, len);

}

return ans;

}

};

Solution 2: Sliding Window

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

C++

// Author: Huahua

class Solution {

public:

int equalSubstring(string s, string t, int maxCost) {

const int n = s.length();

int ans = 0;

for (int i = 0, j = 0, cost = 0; i < n && j < n; ++i) {

while (j < n) {

int c = abs(s[j] - t[j]);

if (cost + c > maxCost) break;

cost += c;

++j;

}

ans = max(ans, j - i);

cost -= abs(s[i] - t[i]);

}

return ans;

}

};

花花酱 LeetCode 1176. Diet Plan Performance

By zxi on August 31, 2019

A dieter consumes calories[i] calories on the i-th day. For every consecutive sequence of k days, they look at T, the total calories consumed during that sequence of k days:

If T < lower, they performed poorly on their diet and lose 1 point;
If T > upper, they performed well on their diet and gain 1 point;
Otherwise, they performed normally and there is no change in points.

Return the total number of points the dieter has after all calories.length days.

Note that: The total points could be negative.

Example 1:

Input: calories = [1,2,3,4,5], k = 1, lower = 3, upper = 3
Output: 0
Explaination: calories[0], calories[1] < lower and calories[3], calories[4] > upper, total points = 0.

Example 2:

Input: calories = [3,2], k = 2, lower = 0, upper = 1
Output: 1
Explaination: calories[0] + calories[1] > upper, total points = 1.

Example 3:

Input: calories = [6,5,0,0], k = 2, lower = 1, upper = 5
Output: 0
Explaination: calories[0] + calories[1] > upper, calories[2] + calories[3] < lower, total points = 0.

Constraints:

1 <= k <= calories.length <= 10^5
0 <= calories[i] <= 20000
0 <= lower <= upper

Solution: Sliding Window

Maintain the sum of a sliding window length of k.

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

C++

// Author: Huahua

class Solution {

public:

int dietPlanPerformance(vector<int>& calories, int k, int lower, int upper) {

int ans = 0;

int t = accumulate(begin(calories), begin(calories) + k - 1, 0);

for (int i = k - 1; i < calories.size(); ++i) {

if (i >= k) t -= calories[i - k];

t += calories[i];

if (t > upper) ++ans;

if (t < lower) --ans;

}

return ans;

}

};

花花酱 LeetCode 1052. Grumpy Bookstore Owner

By zxi on May 27, 2019

Today, the bookstore owner has a store open for customers.length minutes. Every minute, some number of customers (customers[i]) enter the store, and all those customers leave after the end of that minute.

On some minutes, the bookstore owner is grumpy. If the bookstore owner is grumpy on the i-th minute, grumpy[i] = 1, otherwise grumpy[i] = 0. When the bookstore owner is grumpy, the customers of that minute are not satisfied, otherwise they are satisfied.

The bookstore owner knows a secret technique to keep themselves not grumpy for X minutes straight, but can only use it once.

Return the maximum number of customers that can be satisfied throughout the day.

Example 1:

Input: customers = [1,0,1,2,1,1,7,5], grumpy = [0,1,0,1,0,1,0,1], X = 3
Output: 16
Explanation: The bookstore owner keeps themselves not grumpy for the last 3 minutes. 
The maximum number of customers that can be satisfied = 1 + 1 + 1 + 1 + 7 + 5 = 16.

Note:

1 <= X <= customers.length == grumpy.length <= 20000
0 <= customers[i] <= 1000
0 <= grumpy[i] <= 1

Solution: Sliding Window

Sum the costumers of non grumpy minutes, recording the max sum of the sliding window of size X.

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

C++

// Author: Huahua

class Solution {

public:

int maxSatisfied(vector<int>& customers, vector<int>& grumpy, int X) {

int base = 0;

int window = 0;

int best_window = 0;

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

(grumpy[i] ? window : base) += customers[i];

if (i >= X && grumpy[i - X])

window -= customers[i - X];

best_window = max(best_window, window);

}

return base + best_window;

}

};

花花酱 LeetCode 209. Minimum Size Subarray Sum

By zxi on April 13, 2019

Given an array of n positive integers and a positive integer s, find the minimal length of a contiguoussubarray of which the sum ≥ s. If there isn’t one, return 0 instead.

Example:

Input: s = 7, nums = [2,3,1,2,4,3]
Output: 2
Explanation: the subarray [4,3] has the minimal length under the problem constraint.

Follow up:If you have figured out the O(n) solution, try coding another solution of which the time complexity is O(n log n).

Solution 1: Two Pointers (Sliding Window)

Maintain a sliding window [l, r) such that sum(nums[l:r)) >= s, then move l to l + 1, and move r accordingly to make the window valid.

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

C++

class Solution {

public:

int minSubArrayLen(int s, vector<int>& nums) {

int l = 0;

int r = 0;

int t = 0;

int ans = INT_MAX;

while (l < nums.size()) {

while (t < s && r < nums.size()) t += nums[r++];

if (t < s) break;

ans = min(ans, r - l);

t -= nums[l++];

}

return ans == INT_MAX ? 0 : ans;

}

};