Posts tagged as “sliding window”

花花酱 LeetCode 1838. Frequency of the Most Frequent Element

By zxi on April 25, 2021

The frequency of an element is the number of times it occurs in an array.

You are given an integer array nums and an integer k. In one operation, you can choose an index of nums and increment the element at that index by 1.

Return the maximum possible frequency of an element after performing at most k operations.

Example 1:

Input: nums = [1,2,4], k = 5
Output: 3
Explanation: Increment the first element three times and the second element two times to make nums = [4,4,4].
4 has a frequency of 3.

Example 2:

Input: nums = [1,4,8,13], k = 5
Output: 2
Explanation: There are multiple optimal solutions:
- Increment the first element three times to make nums = [4,4,8,13]. 4 has a frequency of 2.
- Increment the second element four times to make nums = [1,8,8,13]. 8 has a frequency of 2.
- Increment the third element five times to make nums = [1,4,13,13]. 13 has a frequency of 2.

Example 3:

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

Constraints:

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

Solution: Sliding Window

Sort the elements, maintain a window such that it takes at most k ops to make the all the elements equal to nums[i].

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

C++

class Solution {

public:

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

sort(begin(nums), end(nums));

int l = 0;

long sum = 0;

int ans = 0;

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

sum += nums[r];

while (l < r &&

sum + k < static_cast<long>(nums[r]) * (r - l + 1))

sum -= nums[l++];

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

}

return ans;

}

};

花花酱 LeetCode 1703. Minimum Adjacent Swaps for K Consecutive Ones

By zxi on December 26, 2020

You are given an integer array, nums, and an integer k. nums comprises of only 0‘s and 1‘s. In one move, you can choose two adjacent indices and swap their values.

Return the minimum number of moves required so that nums has k consecutive 1‘s.

Example 1:

Input: nums = [1,0,0,1,0,1], k = 2
Output: 1
Explanation: In 1 move, nums could be [1,0,0,0,1,1] and have 2 consecutive 1's.

Example 2:

Input: nums = [1,0,0,0,0,0,1,1], k = 3
Output: 5
Explanation: In 5 moves, the leftmost 1 can be shifted right until nums = [0,0,0,0,0,1,1,1].

Example 3:

Input: nums = [1,1,0,1], k = 2
Output: 0
Explanation: nums already has 2 consecutive 1's.

Constraints:

1 <= nums.length <= 10⁵
nums[i] is 0 or 1.
1 <= k <= sum(nums)

Solution: Prefix Sum + Sliding Window

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

We only care positions of 1s, we can move one element from position x to y (assuming x + 1 ~ y are all zeros) in y – x steps. e.g. [0 0 1 0 0 0 1] => [0 0 0 0 0 1 1], move first 1 at position 2 to position 5, cost is 5 – 2 = 3.

Given a size k window of indices of ones, the optimal solution it to use the median number as center. We can compute the cost to form consecutive numbers:

e.g. [1 4 7 9 10] => [5 6 7 8 9] cost = (5 – 1) + (6 – 4) + (9 – 8) + (10 – 9) = 8

However, naive solution takes O(n*k) => TLE.

We can use prefix sum to compute the cost of a window in O(1) to reduce time complexity to O(n)

First, in order to use sliding window, we change the target of every number in the window to the median number.
e.g. [1 4 7 9 10] => [7 7 7 7 7] cost = (7 – 1) + (7 – 4) + (7 – 7) + (9 – 7) + (10 – 7) = (9 + 10) – (1 + 4) = right – left.
[5 6 7 8 9] => [7 7 7 7 7] takes extra 2 + 1 + 1 + 2 = 6 steps = (k / 2) * ((k + 1) / 2), these extra steps should be deducted from the final answer.

C++

class Solution {

public:

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

vector<long> s(1);

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

if (nums[i])

s.push_back(s.back() + i);

const int n = s.size();

long ans = 1e10;

const int m1 = k / 2, m2 = (k + 1) / 2;

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

const long right = s[i + k] - s[i + m1];

const long left = s[i + m2] - s[i];

ans = min(ans, right - left);

}

return ans - m1 * m2;

}

};

Python3

class Solution:

def minMoves(self, nums: List[int], k: int) -> int:

ans = 1e10

s = [0]

for i, v in enumerate(nums):

if v: s.append(s[-1] + i)

n = len(s)

m1 = k // 2

m2 = (k + 1) // 2

for i in range(n - k):

right = s[i + k] - s[i + m1]

left = s[i + m2] - s[i]

ans = min(ans, right - left)

return ans - m1 * m2

花花酱 LeetCode 1695. Maximum Erasure Value

By zxi on December 20, 2020

You are given an array of positive integers nums and want to erase a subarray containing unique elements. The score you get by erasing the subarray is equal to the sum of its elements.

Return the maximum score you can get by erasing exactly one subarray.

An array b is called to be a subarray of a if it forms a contiguous subsequence of a, that is, if it is equal to a[l],a[l+1],...,a[r] for some (l,r).

Example 1:

Input: nums = [4,2,4,5,6]
Output: 17
Explanation: The optimal subarray here is [2,4,5,6].

Example 2:

Input: nums = [5,2,1,2,5,2,1,2,5]
Output: 8
Explanation: The optimal subarray here is [5,2,1] or [1,2,5].

Constraints:

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

Solution: Sliding window + Hashset

Maintain a window that has no duplicate elements.

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

C++

// Author: Huahua

class Solution {

public:

int maximumUniqueSubarray(vector<int>& nums) {

const int n = nums.size();

unordered_set<int> t;

int ans = 0;

for (int l = 0, r = 0, s = 0; r < n; ++r) {

while (t.count(nums[r]) && l < r) {

s -= nums[l];

t.erase(nums[l++]);

}

t.insert(nums[r]);

ans = max(ans, s += nums[r]);

}

return ans;

}

};

花花酱 LeetCode 1687. Delivering Boxes from Storage to Ports

By zxi on December 13, 2020

You have the task of delivering some boxes from storage to their ports using only one ship. However, this ship has a limit on the number of boxes and the total weight that it can carry.

You are given an array boxes, where boxes[i] = [ports_i, weight_i], and three integers portsCount, maxBoxes, and maxWeight.

ports_i is the port where you need to deliver the i^th box and weights_i is the weight of the i^th box.
portsCount is the number of ports.
maxBoxes and maxWeight are the respective box and weight limits of the ship.

The boxes need to be delivered in the order they are given. The ship will follow these steps:

The ship will take some number of boxes from the boxes queue, not violating the maxBoxes and maxWeight constraints.
For each loaded box in order, the ship will make a trip to the port the box needs to be delivered to and deliver it. If the ship is already at the correct port, no trip is needed, and the box can immediately be delivered.
The ship then makes a return trip to storage to take more boxes from the queue.

The ship must end at storage after all the boxes have been delivered.

Return the minimum number of trips the ship needs to make to deliver all boxes to their respective ports.

Example 1:

Input: boxes = [[1,1],[2,1],[1,1]], portsCount = 2, maxBoxes = 3, maxWeight = 3
Output: 4
Explanation: The optimal strategy is as follows: 
- The ship takes all the boxes in the queue, goes to port 1, then port 2, then port 1 again, then returns to storage. 4 trips.
So the total number of trips is 4.
Note that the first and third boxes cannot be delivered together because the boxes need to be delivered in order (i.e. the second box needs to be delivered at port 2 before the third box).

Example 2:

Input: boxes = [[1,2],[3,3],[3,1],[3,1],[2,4]], portsCount = 3, maxBoxes = 3, maxWeight = 6
Output: 6
Explanation: The optimal strategy is as follows: 
- The ship takes the first box, goes to port 1, then returns to storage. 2 trips.
- The ship takes the second, third and fourth boxes, goes to port 3, then returns to storage. 2 trips.
- The ship takes the fifth box, goes to port 3, then returns to storage. 2 trips.
So the total number of trips is 2 + 2 + 2 = 6.

Example 3:

Input: boxes = [[1,4],[1,2],[2,1],[2,1],[3,2],[3,4]], portsCount = 3, maxBoxes = 6, maxWeight = 7
Output: 6
Explanation: The optimal strategy is as follows:
- The ship takes the first and second boxes, goes to port 1, then returns to storage. 2 trips.
- The ship takes the third and fourth boxes, goes to port 2, then returns to storage. 2 trips.
- The ship takes the fifth and sixth boxes, goes to port 3, then returns to storage. 2 trips.
So the total number of trips is 2 + 2 + 2 = 6.

Example 4:

Input: boxes = [[2,4],[2,5],[3,1],[3,2],[3,7],[3,1],[4,4],[1,3],[5,2]], portsCount = 5, maxBoxes = 5, maxWeight = 7
Output: 14
Explanation: The optimal strategy is as follows:
- The ship takes the first box, goes to port 2, then storage. 2 trips.
- The ship takes the second box, goes to port 2, then storage. 2 trips.
- The ship takes the third and fourth boxes, goes to port 3, then storage. 2 trips.
- The ship takes the fifth box, goes to port 3, then storage. 2 trips.
- The ship takes the sixth and seventh boxes, goes to port 3, then port 4, then storage. 3 trips. 
- The ship takes the eighth and ninth boxes, goes to port 1, then port 5, then storage. 3 trips.
So the total number of trips is 2 + 2 + 2 + 2 + 3 + 3 = 14.

Constraints:

1 <= boxes.length <= 10⁵
1 <= portsCount, maxBoxes, maxWeight <= 10⁵
1 <= ports_i <= portsCount
1 <= weights_i <= maxWeight

Solution: Sliding Window

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

C++

// Author: Huahua

class Solution {

public:

int boxDelivering(vector<vector<int>>& boxes, int portsCount, int maxBoxes, int maxWeight) {

const int n = boxes.size();

vector<int> dp(n + 1); // dp[i] := min trips to deliver boxes[0:i]

for (int i = 0, j = 0, b = 0, w = 0, t = 1; j < n; ++j) {

// Different ports.

if (j == 0 || boxes[j][0] != boxes[j - 1][0]) ++t;

// Load the box.

w += boxes[j][1];

while (w > maxWeight // Too heavy.

|| (j - i + 1) > maxBoxes // Too many boxes.

|| (i < j && dp[i + 1] == dp[i])) { // Same cost more boxes.

w -= boxes[i++][1]; // 'Unload' the box.

if (boxes[i][0] != boxes[i - 1][0]) --t; // Different ports.

}

// Takes t trips to deliver boxes[i~j].

dp[j + 1] = dp[i] + t;

}

return dp[n];

}

};

花花酱 LeetCode 1658. Minimum Operations to Reduce X to Zero

By zxi on November 14, 2020

You are given an integer array nums and an integer x. In one operation, you can either remove the leftmost or the rightmost element from the array nums and subtract its value from x. Note that this modifies the array for future operations.

Return the minimum number of operations to reduce x to exactly 0 if it’s possible, otherwise, return -1.

Example 1:

Input: nums = [1,1,4,2,3], x = 5
Output: 2
Explanation: The optimal solution is to remove the last two elements to reduce x to zero.

Example 2:

Input: nums = [5,6,7,8,9], x = 4
Output: -1

Example 3:

Input: nums = [3,2,20,1,1,3], x = 10
Output: 5
Explanation: The optimal solution is to remove the last three elements and the first two elements (5 operations in total) to reduce x to zero.

Constraints:

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

Solution1: Prefix Sum + Hashtable

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

C++

// Author: Huahua

class Solution {

public:

int minOperations(vector<int>& nums, int x) {

const int n = nums.size();

vector<int> l(n), r(n);

unordered_map<int, int> ml, mr;

ml[0] = mr[0] = -1;

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

l[i] = nums[i] + (i > 0 ? l[i - 1] : 0);

r[i] = nums[n - i - 1] + (i > 0 ? r[i - 1]: 0);

ml[l[i]] = mr[r[i]] = i;

}

int ans = INT_MAX;

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

int s1 = x - l[i];

auto it1 = mr.find(s1);

if (it1 != mr.end()) ans = min(ans, i + 1 + it1->second + 1);

int s2 = x - r[i];

auto it2 = ml.find(s2);

if (it2 != ml.end()) ans = min(ans, i + 1 + it2->second + 1);

}

return ans > n ? -1 : ans;

}

};

Solution2: Sliding Window

Find the longest sliding window whose sum of elements equals sum(nums) – x
ans = n – window_size

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

C++

// Author: Huahua

class Solution {

public:

int minOperations(vector<int>& nums, int x) {

const int n = nums.size();

int target = accumulate(begin(nums), end(nums), 0) - x;

int ans = INT_MAX;

for (int s = 0, l = 0, r = 0; r < n; ++r) {

s += nums[r];

while (s > target && l <= r) s -= nums[l++];

if (s == target) ans = min(ans, n - (r - l + 1));

}

return ans > n ? -1 : ans;

}

};