Posts published in “Array”

花花酱 LeetCode 1909. Remove One Element to Make the Array Strictly Increasing

By zxi on December 24, 2021

Given a 0-indexed integer array nums, return true if it can be made strictly increasing after removing exactly one element, or false otherwise. If the array is already strictly increasing, return true.

The array nums is strictly increasing if nums[i - 1] < nums[i] for each index (1 <= i < nums.length).

Example 1:

Input: nums = [1,2,10,5,7]
Output: true
Explanation: By removing 10 at index 2 from nums, it becomes [1,2,5,7].
[1,2,5,7] is strictly increasing, so return true.

Example 2:

Input: nums = [2,3,1,2]
Output: false
Explanation:
[3,1,2] is the result of removing the element at index 0.
[2,1,2] is the result of removing the element at index 1.
[2,3,2] is the result of removing the element at index 2.
[2,3,1] is the result of removing the element at index 3.
No resulting array is strictly increasing, so return false.

Example 3:

Input: nums = [1,1,1]
Output: false
Explanation: The result of removing any element is [1,1].
[1,1] is not strictly increasing, so return false.

Constraints:

2 <= nums.length <= 1000
1 <= nums[i] <= 1000

Solution 1: Brute Force

Enumerate the element to remove and check.

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

C++

// Author: Huahua

class Solution {

public:

bool canBeIncreasing(vector<int>& nums) {

const int n = nums.size();

auto check = [&](int k) {

vector<int> arr(nums);

arr.erase(begin(arr) + k);

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

if (arr[i] <= arr[i - 1]) return false;

return true;

};

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

if (check(i)) return true;

return false;

}

};

C++/O(1) Space

// Author: Huahua

class Solution {

public:

bool canBeIncreasing(vector<int>& nums) {

const int n = nums.size();

auto check = [&](int k) {

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

int j = (i - 1 == k) ? (i - 2) : (i - 1);

if (i != k && j >= 0 && nums[i] <= nums[j])

return false;

}

return true;

};

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

if (check(i)) return true;

return false;

}

};

花花酱 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 2104. Sum of Subarray Ranges

By zxi on December 12, 2021

Problem

Solution 0: Brute force [TLE]

Enumerate all subarrays, for each one, find min and max.

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

Solution 1: Prefix min/max

We can use prefix technique to extend the array while keep tracking the min/max of the subarray.

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

C++

// Author: Huahua

class Solution {

public:

long long subArrayRanges(vector<int>& nums) {

const int n = nums.size();

long long ans = 0;

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

int lo = nums[i];

int hi = nums[i];

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

lo = min(lo, nums[j]);

hi = max(hi, nums[j]);

ans += (hi - lo);

}

return ans;

}

};

Solution 2: Monotonic stack

This problem can be reduced to 花花酱 LeetCode 907. Sum of Subarray Minimums

Just need to run twice one for sum of mins and another for sum of maxs.

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

C++

// Author: Huahua

class Solution {

public:

long long subArrayRanges(vector<int>& nums) {

const int n = nums.size();

auto sumOf = [&](function<bool(int, int)> op) {

long long ans = 0;

stack<int> s;

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

while (!s.empty() and (i == n or op(nums[s.top()], nums[i]))) {

long long k = s.top(); s.pop();

long long j = s.empty() ? -1 : s.top();

ans += nums[k] * (i - k) * (k - j);

}

s.push(i);

}

return ans;

};

return sumOf(less<int>()) - sumOf(greater<int>());

}

};

花花酱 LeetCode 2100. Find Good Days to Rob the Bank

By zxi on December 12, 2021

You and a gang of thieves are planning on robbing a bank. You are given a 0-indexed integer array security, where security[i] is the number of guards on duty on the i^th day. The days are numbered starting from 0. You are also given an integer time.

The i^th day is a good day to rob the bank if:

There are at least time days before and after the i^th day,
The number of guards at the bank for the time days before i are non-increasing, and
The number of guards at the bank for the time days after i are non-decreasing.

More formally, this means day i is a good day to rob the bank if and only if security[i - time] >= security[i - time + 1] >= ... >= security[i] <= ... <= security[i + time - 1] <= security[i + time].

Return a list of all days (0-indexed) that are good days to rob the bank. The order that the days are returned in does not matter.

Example 1:

Input: security = [5,3,3,3,5,6,2], time = 2
Output: [2,3]
Explanation:
On day 2, we have security[0] >= security[1] >= security[2] <= security[3] <= security[4].
On day 3, we have security[1] >= security[2] >= security[3] <= security[4] <= security[5].
No other days satisfy this condition, so days 2 and 3 are the only good days to rob the bank.

Example 2:

Input: security = [1,1,1,1,1], time = 0
Output: [0,1,2,3,4]
Explanation:
Since time equals 0, every day is a good day to rob the bank, so return every day.

Example 3:

Input: security = [1,2,3,4,5,6], time = 2
Output: []
Explanation:
No day has 2 days before it that have a non-increasing number of guards.
Thus, no day is a good day to rob the bank, so return an empty list.

Example 4:

Input: security = [1], time = 5
Output: []
Explanation:
No day has 5 days before and after it.
Thus, no day is a good day to rob the bank, so return an empty list.

Constraints:

1 <= security.length <= 10⁵
0 <= security[i], time <= 10⁵

Solution: Pre-Processing

Pre-compute the non-increasing days at days[i] and the non-decreasing days at days[i] using prefix and suffix arrays.

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

C++

// Author: Huahua

class Solution {

public:

vector<int> goodDaysToRobBank(vector<int>& security, int time) {

const int n = security.size();

vector<int> before(n);

vector<int> after(n);

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

before[i] = security[i - 1] >= security[i] ? before[i - 1] + 1 : 0;

for (int i = n - 2; i >= 0; --i)

after[i] = security[i + 1] >= security[i] ? after[i + 1] + 1 : 0;

vector<int> ans;

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

if (before[i] >= time && after[i] >= time)

ans.push_back(i);

return ans;

}

};

花花酱 LeetCode 2099. Find Subsequence of Length K With the Largest Sum

By zxi on December 12, 2021

You are given an integer array nums and an integer k. You want to find a subsequence of nums of length k that has the largest sum.

Return any such subsequence as an integer array of length k.

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 = [2,1,3,3], k = 2
Output: [3,3]
Explanation:
The subsequence has the largest sum of 3 + 3 = 6.

Example 2:

Input: nums = [-1,-2,3,4], k = 3
Output: [-1,3,4]
Explanation: 
The subsequence has the largest sum of -1 + 3 + 4 = 6.

Example 3:

Input: nums = [3,4,3,3], k = 2
Output: [3,4]
Explanation:
The subsequence has the largest sum of 3 + 4 = 7. 
Another possible subsequence is [4, 3].

Constraints:

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

Solution 1: Full sorting + Hashtable

Make a copy of the original array, sort it in whole and put k largest elements in a hashtable.

Scan the original array and append the number to the answer array if it’s in the hashtable.

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

C++

// Author: Huahua

class Solution {

public:

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

vector<int> ans;

vector<int> s(nums);

sort(rbegin(s), rend(s));

unordered_map<int, int> m;

for (int i = 0; i < k; ++i) ++m[s[i]];

for (int x : nums)

if (--m[x] >= 0)

ans.push_back(x);

return ans;

}

};

Solution 2: k-th element

Use quick select / partial sort to find the k-th largest element of the array. Any number greater than that must be in the sequence. The tricky part is: what about the pivot itself? We couldn’t include ’em all blindly. Need to figure out how many copies of the pivot is there in the k largest and only include as many as of that in the final answer.

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

C++

// Author: Huahua

class Solution {

public:

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

vector<int> ans;

vector<int> s(nums);

nth_element(begin(s), begin(s) + k - 1, end(s), greater<int>());

const int pivot = s[k - 1];

// How many pivots in the largest k elements.

int left = count(begin(s), begin(s) + k, pivot);

for (size_t i = 0; i != nums.size(); ++i)

if (nums[i] > pivot || (nums[i] == pivot && --left >= 0))

ans.push_back(nums[i]);

return ans;

}

};