Posts tagged as “array”

花花酱 LeetCode 1920. Build Array from Permutation

By zxi on December 25, 2021

Given a zero-based permutation nums (0-indexed), build an array ans of the same length where ans[i] = nums[nums[i]] for each 0 <= i < nums.length and return it.

A zero-based permutation nums is an array of distinct integers from 0 to nums.length - 1 (inclusive).

Example 1:

Input: nums = [0,2,1,5,3,4]
Output: [0,1,2,4,5,3]
Explanation: The array ans is built as follows: 
ans = [nums[nums[0]], nums[nums[1]], nums[nums[2]], nums[nums[3]], nums[nums[4]], nums[nums[5]]]
    = [nums[0], nums[2], nums[1], nums[5], nums[3], nums[4]]
    = [0,1,2,4,5,3]

Example 2:

Input: nums = [5,0,1,2,3,4]
Output: [4,5,0,1,2,3]
Explanation: The array ans is built as follows:
ans = [nums[nums[0]], nums[nums[1]], nums[nums[2]], nums[nums[3]], nums[nums[4]], nums[nums[5]]]
    = [nums[5], nums[0], nums[1], nums[2], nums[3], nums[4]]
    = [4,5,0,1,2,3]

Constraints:

1 <= nums.length <= 1000
0 <= nums[i] < nums.length
The elements in nums are distinct.

Follow-up: Can you solve it without using an extra space (i.e., O(1) memory)?

Solution 1: Straight forward

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

C++

// Author: Huahua

class Solution {

public:

vector<int> buildArray(vector<int>& nums) {

vector<int> ans(nums);

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

ans[i] = nums[nums[i]];

return ans;

}

};

Solution 2: Follow up: Inplace Encoding

Since nums[i] <= 1000, we can use low 16 bit to store the original value and high 16 bit for new value.

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

C++

// Author: Huahua

class Solution {

public:

vector<int> buildArray(vector<int>& nums) {

const int n = nums.size();

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

nums[i] |= (nums[nums[i]] & 0xffff) << 16;

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

nums[i] >>= 16;

return nums;

}

};

花花酱 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 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 2105. Watering Plants II

By zxi on December 12, 2021

Problem

Solution: Simulation w/ Two Pointers

Simulate the watering process.

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

C++

// Author: Huahua

class Solution {

public:

int minimumRefill(vector<int>& plants, int capacityA, int capacityB) {

const int n = plants.size();

int ans = 0;

for (int l = 0, r = n - 1, A = capacityA, B = capacityB; l <= r; ++l, --r) {

if (l == r)

return ans += max(A, B) < plants[l];

if ((A -= plants[l]) < 0)

A = capacityA - plants[l], ++ans;

if ((B -= plants[r]) < 0)

B = capacityB - plants[r], ++ans;

}

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>());

}

};