Posts tagged as “sliding window”

花花酱 LeetCode 219. Contains Duplicate II

By zxi on December 5, 2021

Given an integer array nums and an integer k, return true if there are two distinct indices i and j in the array such that nums[i] == nums[j] and abs(i - j) <= k.

Example 1:

Input: nums = [1,2,3,1], k = 3
Output: true

Example 2:

Input: nums = [1,0,1,1], k = 1
Output: true

Example 3:

Input: nums = [1,2,3,1,2,3], k = 2
Output: false

Constraints:

1 <= nums.length <= 10⁵
-10⁹ <= nums[i] <= 10⁹
0 <= k <= 10⁵

Solution: Sliding Window + Hashtable

Hashtable to store the last index of a number.

Remove the number if it’s k steps behind the current position.

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

C++

// Author: Huahua

class Solution {

public:

bool containsNearbyDuplicate(vector<int>& nums, int k) {

unordered_map<int, int> m; // num -> last index

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

if (i > k && m[nums[i - k - 1]] < i - k + 1)

m.erase(nums[i - k - 1]);

if (m.count(nums[i])) return true;

m[nums[i]] = i;

}

return false;

}

};

花花酱 LeetCode 2090. K Radius Subarray Averages

By zxi on November 28, 2021

You are given a 0-indexed array nums of n integers, and an integer k.

The k-radius average for a subarray of nums centered at some index i with the radius k is the average of all elements in nums between the indices i - k and i + k (inclusive). If there are less than k elements before or after the index i, then the k-radius average is -1.

Build and return an array avgs of length n where avgs[i] is the k-radius average for the subarray centered at index i.

The average of x elements is the sum of the x elements divided by x, using integer division. The integer division truncates toward zero, which means losing its fractional part.

For example, the average of four elements 2, 3, 1, and 5 is (2 + 3 + 1 + 5) / 4 = 11 / 4 = 2.75, which truncates to 2.

Example 1:

Input: nums = [7,4,3,9,1,8,5,2,6], k = 3
Output: [-1,-1,-1,5,4,4,-1,-1,-1]
Explanation:
- avg[0], avg[1], and avg[2] are -1 because there are less than k elements before each index.
- The sum of the subarray centered at index 3 with radius 3 is: 7 + 4 + 3 + 9 + 1 + 8 + 5 = 37.
  Using integer division, avg[3] = 37 / 7 = 5.
- For the subarray centered at index 4, avg[4] = (4 + 3 + 9 + 1 + 8 + 5 + 2) / 7 = 4.
- For the subarray centered at index 5, avg[5] = (3 + 9 + 1 + 8 + 5 + 2 + 6) / 7 = 4.
- avg[6], avg[7], and avg[8] are -1 because there are less than k elements after each index.

Example 2:

Input: nums = [100000], k = 0
Output: [100000]
Explanation:
- The sum of the subarray centered at index 0 with radius 0 is: 100000.
  avg[0] = 100000 / 1 = 100000.

Example 3:

Input: nums = [8], k = 100000
Output: [-1]
Explanation: 
- avg[0] is -1 because there are less than k elements before and after index 0.

Constraints:

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

Solution: Sliding Window

We compute i – k’s average at position i.

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

C++

// Author: Huahua

class Solution {

public:

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

const int n = nums.size();

long long sum = 0;

vector<int> ans(n, -1);

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

sum += nums[i];

if (i >= 2 * k) {

ans[i - k] = sum / (2 * k + 1);

sum -= nums[i - 2 * k];

}

return ans;

}

};

花花酱 LeetCode 2009. Minimum Number of Operations to Make Array Continuous

By zxi on November 26, 2021

You are given an integer array nums. In one operation, you can replace any element in nums with any integer.

nums is considered continuous if both of the following conditions are fulfilled:

All elements in nums are unique.
The difference between the maximum element and the minimum element in nums equals nums.length - 1.

For example, nums = [4, 2, 5, 3] is continuous, but nums = [1, 2, 3, 5, 6] is not continuous.

Return the minimum number of operations to make numscontinuous.

Example 1:

Input: nums = [4,2,5,3]
Output: 0
Explanation: nums is already continuous.

Example 2:

Input: nums = [1,2,3,5,6]
Output: 1
Explanation: One possible solution is to change the last element to 4.
The resulting array is [1,2,3,5,4], which is continuous.

Example 3:

Input: nums = [1,10,100,1000]
Output: 3
Explanation: One possible solution is to:
- Change the second element to 2.
- Change the third element to 3.
- Change the fourth element to 4.
The resulting array is [1,2,3,4], which is continuous.

Constraints:

1 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁹

Solution: Sliding Window

Remove duplicates and sort the numbers.
Try using nums[i] as the min number of the final array.
window [i, j), max – min < n, then change the rest of array to fit into or append after the window, which takes n – (j – i) steps.
e.g. input = [10, 3, 1, 4, 5, 6, 6, 6, 11, 15] => sorted + unique => [1, 3, 4, 5, 6, 10, 11, 15]
n = 10, window = [3, 4, 5, 6, 10, 11], max = 11, min = 3, max – min = 8 < 10
Final array = [3, 4, 5, 6, 1->7, 6₂->8, 6₃->9, 10, 11, 15->12]
Time complexity: O(n)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int minOperations(vector<int>& A) {

const int n = A.size();

sort(begin(A), end(A));

A.erase(unique(begin(A), end(A)), end(A));

int ans = INT_MAX;

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

while (j < m && A[j] < A[i] + n) ++j;

ans = min(ans, n - (j - i));

}

return ans;

}

};

花花酱 LeetCode 2062. Count Vowel Substrings of a String

By zxi on November 7, 2021

A substring is a contiguous (non-empty) sequence of characters within a string.

A vowel substring is a substring that only consists of vowels ('a', 'e', 'i', 'o', and 'u') and has all five vowels present in it.

Given a string word, return the number of vowel substrings in word.

Example 1:

Input: word = "aeiouu"
Output: 2
Explanation: The vowel substrings of word are as follows (underlined):
- "aeiouu"
- "aeiouu"

Example 2:

Input: word = "unicornarihan"
Output: 0
Explanation: Not all 5 vowels are present, so there are no vowel substrings.

Example 3:

Input: word = "cuaieuouac"
Output: 7
Explanation: The vowel substrings of word are as follows (underlined):
- "cuaieuouac"
- "cuaieuouac"
- "cuaieuouac"
- "cuaieuouac"
- "cuaieuouac"
- "cuaieuouac"
- "cuaieuouac"

Example 4:

Input: word = "bbaeixoubb"
Output: 0
Explanation: The only substrings that contain all five vowels also contain consonants, so there are no vowel substrings.

Constraints:

1 <= word.length <= 100
word consists of lowercase English letters only.

Solution 1: Brute Force

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

C++

// Author: Huahua

class Solution {

public:

int countVowelSubstrings(string_view word) {

const int n = word.size();

auto check = [&](string_view s) {

set<int> seen;

string vowels {"aeiou"};

for (char c : s) {

if (vowels.find(c) == string::npos) return false;

seen.insert(c);

}

return seen.size() == 5;

};

int ans = 0;

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

for (int l = 5; i + l <= n; ++l)

if (check(word.substr(i, l))) ++ans;

return ans;

}

};

Solution 2: Sliding Window / Three Pointers

Maintain a window [i, j] that contain all 5 vowels, find k s.t. [k + 1, i] no longer container 5 vowels.
# of valid substrings end with j will be (k – i).

##aeiouaeioo##
..i....k...j..
i = 3, k = 8, j = 12

Valid substrings are:
aeiouaeioo .eiouaeioo ..iouaeioo ...ouaeioo ....uaeioo
8 – 3 = 5

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

C++

// Author: Huahua

class Solution {

public:

int countVowelSubstrings(string_view word) {

constexpr string_view vowels{"aeiou"};

int ans = 0;

unordered_map<char, int> m;

for (char c : vowels) m[c] = 0;

for (size_t i = 0, j = 0, k = 0, v = 0; j < word.size(); ++j) {

if (m.count(word[j])) {

v += (++m[word[j]] == 1);

while (v == 5)

v -= (--m[word[k++]] == 0);

ans += k - i;

} else {

for (char c : vowels) m[c] = 0;

v = 0;

i = k = j + 1;

}

return ans;

}

};

花花酱 LeetCode 1888. Minimum Number of Flips to Make the Binary String Alternating

By zxi on August 9, 2021

You are given a binary string s. You are allowed to perform two types of operations on the string in any sequence:

Type-1: Remove the character at the start of the string s and append it to the end of the string.
Type-2: Pick any character in s and flip its value, i.e., if its value is '0' it becomes '1' and vice-versa.

Return the minimum number of type-2 operations you need to perform such that s becomes alternating.

The string is called alternating if no two adjacent characters are equal.

For example, the strings "010" and "1010" are alternating, while the string "0100" is not.

Example 1:

Input: s = "111000"
Output: 2
Explanation: Use the first operation two times to make s = "100011".
Then, use the second operation on the third and sixth elements to make s = "101010".

Example 2:

Input: s = "010"
Output: 0
Explanation: The string is already alternating.

Example 3:

Input: s = "1110"
Output: 1
Explanation: Use the second operation on the second element to make s = "1010".

Constraints:

1 <= s.length <= 10⁵
s[i] is either '0' or '1'.

Solution: Sliding Window

Trying all possible rotations will take O(n²) that leads to TLE, we have to do better.

concatenate the s to itself, then using a sliding window length of n to check how many count needed to make the string in the window alternating which will cover all possible rotations. We can update the count in O(1) when moving to the next window.

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

C++

 // Author: Huahua class Solution { public: int minFlips(string s) { const int n = s.length(); int ans = INT_MAX; for (int i = 0, c0 = 0, c1 = 1, a0 = 0, a1 = 0; i < 2 * n; ++i, c0 ^= 1, c1 ^= 1) { if (s[i % n] - '0' != c0) ++a0; if (s[i % n] - '0' != c1) ++a1; if (i < n - 1) continue; if (i >= n) { if (s[i - n] - '0' != c0 ^ (n & 1)) --a0; if (s[i - n] - '0' != c1 ^ (n & 1)) --a1; } ans = min({ans, a0, a1}); } return ans; } };