Posts tagged as “LIS”

花花酱 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 1713. Minimum Operations to Make a Subsequence

By zxi on January 3, 2021

You are given an array target that consists of distinct integers and another integer array arr that can have duplicates.

In one operation, you can insert any integer at any position in arr. For example, if arr = [1,4,1,2], you can add 3 in the middle and make it [1,4,3,1,2]. Note that you can insert the integer at the very beginning or end of the array.

Return the minimum number of operations needed to make target a subsequence of arr.

A subsequence of an array is a new array generated from the original array by deleting some elements (possibly none) without changing the remaining elements’ relative order. For example, [2,7,4] is a subsequence of [4,2,3,7,2,1,4] (the underlined elements), while [2,4,2] is not.

Example 1:

Input: target = [5,1,3], arr = [9,4,2,3,4]
Output: 2
Explanation: You can add 5 and 1 in such a way that makes arr = [5,9,4,1,2,3,4], then target will be a subsequence of arr.

Example 2:

Input: target = [6,4,8,1,3,2], arr = [4,7,6,2,3,8,6,1]
Output: 3

Constraints:

1 <= target.length, arr.length <= 10⁵
1 <= target[i], arr[i] <= 10⁹
target contains no duplicates.

Solution: Reduce to LIS

The original problem is a LCS (Longest common subsequence) problem that can be solved in O(n*m) time.
Since the elements in the target array is unique, we can convert the numbers into indices that helps to reduce the problem to LIS (Longest increasing subsequence) that can be solved in O(mlogn) time.

e.g.
target: [6,4,8,1,3,2] => [0, 1, 2, 3, 4, 5]
array: [4,7,6,2,3,8,6,1] => [1,-1, 0, 5, 4, 2, 0, 3] => [1, 0, 5, 4, 2, 3]
and the LIS is [0, 2, 3] => [6, 8, 1], we need to insert the rest of the numbers.
Ans = len(target) – len(LIS)

Time complexity: O(nlogm)
Space complexity: O(m)

C++

// Author: Huahua

class Solution {

public:

int minOperations(vector<int>& A, vector<int>& B) {

unordered_map<int, int> m;

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

m[A[i]] = i;

vector<int> dp;

for (int x : B) {

auto mit = m.find(x);

if (mit == end(m)) continue;

const int idx = mit->second;

if (dp.empty() || idx > dp.back())

dp.push_back(idx);

else

*lower_bound(begin(dp), end(dp), idx) = idx;

}

return A.size() - dp.size();

}

};

Python3

# Author: Huahua

class Solution:

def minOperations(self, A: List[int], B: List[int]) -> int:

m = {x: i for i, x in enumerate(A)}

dp = []

for x in B:

if x not in m: continue

if not dp or m[x] > dp[-1]: dp.append(m[x])

else: dp[bisect_left(dp, m[x])] = m[x]

return len(A) - len(dp)

花花酱 LeetCode 1671. Minimum Number of Removals to Make Mountain Array

By zxi on November 28, 2020

You may recall that an array arr is a mountain array if and only if:

arr.length >= 3
There exists some index i (0-indexed) with 0 < i < arr.length - 1 such that:
- arr[0] < arr[1] < ... < arr[i - 1] < arr[i]
- arr[i] > arr[i + 1] > ... > arr[arr.length - 1]

Given an integer array nums, return the minimum number of elements to remove to make numsa mountain array.

Example 1:

Input: nums = [1,3,1]
Output: 0
Explanation: The array itself is a mountain array so we do not need to remove any elements.

Example 2:

Input: nums = [2,1,1,5,6,2,3,1]
Output: 3
Explanation: One solution is to remove the elements at indices 0, 1, and 5, making the array nums = [1,5,6,3,1].

Example 3:

Input: nums = [4,3,2,1,1,2,3,1]
Output: 4

Example 4:

Input: nums = [1,2,3,4,4,3,2,1]
Output: 1

Constraints:

3 <= nums.length <= 1000
1 <= nums[i] <= 10⁹
It is guaranteed that you can make a mountain array out of nums.

Solution: DP / LIS

LIS[i] := longest increasing subsequence ends with nums[i]
LDS[i] := longest decreasing subsequence starts with nums[i]
Let nums[i] be the peak, the length of the mountain array is LIS[i] + LDS[i] – 1
Note: LIS[i] and LDS[i] must be > 1 to form a valid mountain array.
ans = min(n – (LIS[i] + LDS[i] – 1)) 0 <= i < n

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

C++

// Author: Huahua

class Solution {

public:

int minimumMountainRemovals(vector<int>& nums) {

const int n = nums.size();

vector<int> LIS(n, 1); // LIS[i] := Longest increasing subseq ends with nums[i]

vector<int> LDS(n, 1); // LDS[i] := Longest decreasing subseq starts with nums[i]

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

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

if (nums[i] > nums[j]) LIS[i] = max(LIS[i], LIS[j] + 1);

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

for (int j = n - 1; j > i; --j)

if (nums[i] > nums[j]) LDS[i] = max(LDS[i], LDS[j] + 1);

int ans = INT_MAX;

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

if (LIS[i] < 2 || LDS[i] < 2) continue;

ans = min(ans, n - (LIS[i] + LDS[i] - 1));

}

return ans;

}

};

花花酱 LeetCode 673. Number of Longest Increasing Subsequence

By zxi on September 15, 2017

https://leetcode.com/problems/number-of-longest-increasing-subsequence

Problem:

Given an unsorted array of integers, find the number of longest increasing subsequence.

Example 1:

Input: [1,3,5,4,7]

Output: 2

Explanation: The two longest increasing subsequence are [1, 3, 4, 7] and [1, 3, 5, 7].

Example 2:

Input: [2,2,2,2,2]

Output: 5

Explanation: The length of longest continuous increasing subsequence is 1, and there are 5 subsequences' length is 1, so output 5.

Note: Length of the given array will be not exceed 2000 and the answer is guaranteed to be fit in 32-bit signed int.

Idea:

Dynamic programming

Solution1:

// Author: Huahua

// Running time: 82 ms

class Solution {

public:

int findNumberOfLIS(vector<int>& nums) {

int n = nums.size();

if (n == 0) return 0;

c_ = vector<int>(n, 0);

l_ = vector<int>(n, 0);

// Find the length LIS.

int max_len = 0;

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

max_len = max(max_len, len(nums, i));

// Checking all endings.

int ans = 0;

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

if (len(nums, i) == max_len)

ans += count(nums, i);

return ans;

}

private:

vector<int> c_; // c[i]: number of LIS ends with nums[i] / NLIS'

vector<int> l_; // l[i]: lengeh of LIS ends with nums[i] / LIS'

// Number of LIS ends with nums[n]

int count(const vector<int>& nums, int n) {

if (n == 0) return 1;

if (c_[n] > 0) return c_[n];

int total_count = 0;

int l = len(nums, n);

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

if (nums[n] > nums[i] && len(nums, i) == l-1)

total_count += count(nums, i);

if (total_count == 0)

total_count = 1;

return c_[n] = total_count;

}

// Length of LIS ends with nums[n]

int len(const vector<int>& nums, int n) {

if (n == 0) return 1;

if (l_[n] > 0) return l_[n];

int max_len = 1;

// Check every subarray

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

if (nums[n] > nums[i])

max_len = max(max_len, len(nums, i) + 1);

return l_[n] = max_len;

}

};

Solution2:

// Author: Huahua

// Running time: 33 ms

class Solution {

public:

int findNumberOfLIS(vector<int>& nums) {

int n = nums.size();

if (n == 0) return 0;

vector<int> c(n, 1);

vector<int> l(n, 1);

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

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

if (nums[i] > nums[j]) {

if (l[j] + 1 > l[i]) {

l[i] = l[j] + 1;

c[i] = c[j];

} else if (l[j] + 1 == l[i]) {

c[i] += c[j];

}

int max_len = *max_element(l.begin(), l.end());

int ans = 0;

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

if (l[i] == max_len)

ans += c[i];

return ans;

}

};

Related Problems:

花花酱 LeetCode 300. Longest Increasing Subsequence

By zxi on September 10, 2017

Problem:

Given an unsorted array of integers, find the length of longest increasing subsequence.

For example,
Given [10, 9, 2, 5, 3, 7, 101, 18],
The longest increasing subsequence is [2, 3, 7, 101], therefore the length is 4. Note that there may be more than one LIS combination, it is only necessary for you to return the length.

Your algorithm should run in O(n²) complexity.

Follow up: Could you improve it to O(n log n) time complexity?

Idea:

Dynamic Programming

Time Complexity:

O(n^2)

Solution 1:

// Author: Huahua

// Running time: 29 ms

class Solution {

public:

int lengthOfLIS(vector<int>& nums) {

if (nums.empty()) return 0;

int n = nums.size();

auto f = vector<int>(n, 1);

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

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

if (nums[i] > nums[j])

f[i] = max(f[i], f[j] + 1);

return *max_element(f.begin(), f.end());

}

};

Solution 2: DP + Binary Search / Patience Sort

dp[i] := smallest tailing number of a increasing subsequence of length i + 1.

dp is an increasing array, we can use binary search to find the index to insert/update the array.

ans = len(dp)

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

C++

class Solution {

public:

int lengthOfLIS(vector<int>& nums) {

const int n = nums.size();

if (n == 0) return 0;

vector<int> dp;

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

auto it = lower_bound(begin(dp), end(dp), nums[i]);

if (it == end(dp))

dp.push_back(nums[i]);

else

*it = nums[i];

}

return dp.size();

}

};

Python3

class Solution:

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

d = []

for x in nums:

i = bisect_left(d, x)

if i == len(d):

d.append(x)

else:

d[i] = x

return len(d)

Related Problems: