Huahua’s Tech Road

花花酱 LeetCode 2111. Minimum Operations to Make the Array K-Increasing

By zxi on December 22, 2021

You are given a 0-indexed array arr consisting of n positive integers, and a positive integer k.

The array arr is called K-increasing if arr[i-k] <= arr[i] holds for every index i, where k <= i <= n-1.

For example, arr = [4, 1, 5, 2, 6, 2] is K-increasing for k = 2 because:
- arr[0] <= arr[2] (4 <= 5)
- arr[1] <= arr[3] (1 <= 2)
- arr[2] <= arr[4] (5 <= 6)
- arr[3] <= arr[5] (2 <= 2)
However, the same arr is not K-increasing for k = 1 (because arr[0] > arr[1]) or k = 3 (because arr[0] > arr[3]).

In one operation, you can choose an index i and change arr[i] into any positive integer.

Return the minimum number of operations required to make the array K-increasing for the given k.

Example 1:

Input: arr = [5,4,3,2,1], k = 1
Output: 4
Explanation:
For k = 1, the resultant array has to be non-decreasing.
Some of the K-increasing arrays that can be formed are [5,6,7,8,9], [1,1,1,1,1], [2,2,3,4,4]. All of them require 4 operations.
It is suboptimal to change the array to, for example, [6,7,8,9,10] because it would take 5 operations.
It can be shown that we cannot make the array K-increasing in less than 4 operations.

Example 2:

Input: arr = [4,1,5,2,6,2], k = 2
Output: 0
Explanation:
This is the same example as the one in the problem description.
Here, for every index i where 2 <= i <= 5, arr[i-2] <=arr[i].
Since the given array is already K-increasing, we do not need to perform any operations.

Example 3:

Input: arr = [4,1,5,2,6,2], k = 3
Output: 2
Explanation:
Indices 3 and 5 are the only ones not satisfying arr[i-3] <= arr[i] for 3 <= i <= 5.
One of the ways we can make the array K-increasing is by changing arr[3] to 4 and arr[5] to 5.
The array will now be [4,1,5,4,6,5].
Note that there can be other ways to make the array K-increasing, but none of them require less than 2 operations.

Constraints:

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

Solution: Longest increasing subsequence

if k = 1, we need to modify the following arrays
1. [a[0], a[1], a[2], …]
if k = 2, we need to modify the following arrays
1. [a[0], a[2], a[4], …]
2. [a[1], a[3], a[5], …]
if k = 3, we need to modify the following arrays
1. [a[0], a[3], a[6], …]
2. [a[1], a[4], a[7], …]
3. [a[2], a[5], a[8], …]
…

These arrays are independent of each other, we just need to find LIS of it, # ops = len(arr) – LIS(arr).
Ans = sum(len(arr_i) – LIS(arr_i)) 1 <= i <= k

Reference: 花花酱 LeetCode 300. Longest Increasing Subsequence

Time complexity: O(k * (n/k)* log(n/k)) = O(n * log(n/k))
Space complexity: O(n/k)

C++

// Author: Huahua

class Solution {

public:

int kIncreasing(vector<int>& arr, int k) {

auto LIS = [](const vector<int>& nums) {

vector<int> lis;

for (int x : nums)

if (lis.empty() || lis.back() <= x)

lis.push_back(x);

else

*upper_bound(begin(lis), end(lis), x) = x;

return lis.size();

};

const int n = arr.size();

int ans = 0;

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

vector<int> cur;

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

cur.push_back(arr[j]);

ans += cur.size() - LIS(cur);

}

return ans;

}

};

Python3

# Author: Huahua

class Solution:

def kIncreasing(self, arr: List[int], k: int) -> int:

def LIS(arr: List[int]) -> int:

lis = []

for x in arr:

if not lis or lis[-1] <= x:

lis.append(x)

else:

lis[bisect_right(lis, x)] = x

return len(lis)

return sum(len(arr[i::k]) - LIS(arr[i::k]) for i in range(k))

花花酱 LeetCode 2110. Number of Smooth Descent Periods of a Stock

By zxi on December 20, 2021

You are given an integer array prices representing the daily price history of a stock, where prices[i] is the stock price on the i^th day.

A smooth descent period of a stock consists of one or more contiguous days such that the price on each day is lower than the price on the preceding day by exactly 1. The first day of the period is exempted from this rule.

Return the number of smooth descent periods.

Example 1:

Input: prices = [3,2,1,4]
Output: 7
Explanation: There are 7 smooth descent periods:
[3], [2], [1], [4], [3,2], [2,1], and [3,2,1]
Note that a period with one day is a smooth descent period by the definition.

Example 2:

Input: prices = [8,6,7,7]
Output: 4
Explanation: There are 4 smooth descent periods: [8], [6], [7], and [7]
Note that [8,6] is not a smooth descent period as 8 - 6 ≠ 1.

Example 3:

Input: prices = [1]
Output: 1
Explanation: There is 1 smooth descent period: [1]

Constraints:

1 <= prices.length <= 10⁵
1 <= prices[i] <= 10⁵

Solution: DP

Same as longest decreasing subarray.

dp[i] := length of longest smoothing subarray ends with nums[i].

dp[i] = dp[i – 1] + 1 if nums[i] + 1 = nums[i – 1] else 1

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

C++

// Author: Huahua

class Solution {

public:

long long getDescentPeriods(vector<int>& prices) {

const int n = prices.size();

vector<long long> dp(n, 1);

long long ans = 1;

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

if (prices[i] - prices[i - 1] == -1)

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

ans += dp[i];

}

return ans;

}

};

花花酱 LeetCode 2109. Adding Spaces to a String

By zxi on December 20, 2021

You are given a 0-indexed string s and a 0-indexed integer array spaces that describes the indices in the original string where spaces will be added. Each space should be inserted before the character at the given index.

For example, given s = "EnjoyYourCoffee" and spaces = [5, 9], we place spaces before 'Y' and 'C', which are at indices 5 and 9 respectively. Thus, we obtain "Enjoy Your Coffee".

Return the modified string after the spaces have been added.

Example 1:

Input: s = "LeetcodeHelpsMeLearn", spaces = [8,13,15]
Output: "Leetcode Helps Me Learn"
Explanation: 
The indices 8, 13, and 15 correspond to the underlined characters in "LeetcodeHelpsMeLearn".
We then place spaces before those characters.

Example 2:

Input: s = "icodeinpython", spaces = [1,5,7,9]
Output: "i code in py thon"
Explanation:
The indices 1, 5, 7, and 9 correspond to the underlined characters in "icodeinpython".
We then place spaces before those characters.

Example 3:

Input: s = "spacing", spaces = [0,1,2,3,4,5,6]
Output: " s p a c i n g"
Explanation:
We are also able to place spaces before the first character of the string.

Constraints:

1 <= s.length <= 3 * 10⁵
s consists only of lowercase and uppercase English letters.
1 <= spaces.length <= 3 * 10⁵
0 <= spaces[i] <= s.length - 1
All the values of spaces are strictly increasing.

Solution: Scan orignal string / Two Pointers

Just scan the original string and insert a space if the current index matched the front space index.

Time complexity: O(n)
Space complexity: O(m+n) / O(1)

C++

// Author: Huahua

class Solution {

public:

string addSpaces(string s, vector<int>& spaces) {

const int m = spaces.size();

string ans;

for (int i = 0, j = 0; i < s.length(); ++i) {

if (j < m && i == spaces[j]) {

ans += " ";

++j;

}

ans += s[i];

}

return ans;

}

};

花花酱 LeetCode 2108. Find First Palindromic String in the Array

By zxi on December 20, 2021

Given an array of strings words, return the first palindromic string in the array. If there is no such string, return an empty string "".

A string is palindromic if it reads the same forward and backward.

Example 1:

Input: words = ["abc","car","ada","racecar","cool"]
Output: "ada"
Explanation: The first string that is palindromic is "ada".
Note that "racecar" is also palindromic, but it is not the first.

Example 2:

Input: words = ["notapalindrome","racecar"]
Output: "racecar"
Explanation: The first and only string that is palindromic is "racecar".

Example 3:

Input: words = ["def","ghi"]
Output: ""
Explanation: There are no palindromic strings, so the empty string is returned.

Constraints:

1 <= words.length <= 100
1 <= words[i].length <= 100
words[i] consists only of lowercase English letters.

Solution: Brute Force

Enumerate each word and check whether it’s a palindrome or not.

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

C++

// Author: Huahua

class Solution {

public:

string firstPalindrome(vector<string>& words) {

auto isPalindrome = [](string_view s) {

size_t l = s.size();

for (size_t i = 0; i < l / 2; ++i)

if (s[i] != s[l - i - 1]) return false;

return true;

};

for (const string& word : words)

if (isPalindrome(word)) return word;

return "";

}

};

花花酱 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;

}

};

Huahua's Tech Road

花花酱 LeetCode 2111. Minimum Operations to Make the Array K-Increasing

Solution: Longest increasing subsequence

C++

Python3

花花酱 LeetCode 2110. Number of Smooth Descent Periods of a Stock

Solution: DP

C++

花花酱 LeetCode 2109. Adding Spaces to a String

Solution: Scan orignal string / Two Pointers

C++

花花酱 LeetCode 2108. Find First Palindromic String in the Array

Solution: Brute Force

C++

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

Problem

Solution 1: Range sum query

C++

Solution 2: Sliding Window

C++