|
Given an array arr[] of size N. The task is to split the array into minimum number of strictly decreasing subsequences. Calculate the minimum number of subsequences we can get by splitting.
Examples:
Input: N = 4, arr[] = {3, 5, 1, 2}
Output: 2
Explanation: We can split the array into two subsequences: {3,1} and {5,2}
Both are strictly decreasing subsequence.
Input: N = 3, arr[] = {3,3,3}
Output: 3
Explanation: We can split the array into three subsequences: {3},{3} and {3}
Approach: To solve the problem, follow the below idea:
If we observe carefully, we can see that the Minimum number of decreasing subsequences is equal to the length of longest increasing subsequence where each element from the longest increasing subsequence belongs to a single decreasing subsequence, so it can be found in N*Log(N).
Below is the implementation of the above approach:
C++
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
int minDecreasingSub(int N, vector<int> arr) {
vector<int> seq;
seq.push_back(arr[0]);
for (auto i = 1; i < N; i++) {
int ind = upper_bound(seq.begin(), seq.end(), arr[i]) - seq.begin();
if (ind == seq.size())
seq.push_back(arr[i]);
else
seq[ind] = arr[i];
}
return seq.size();
}
};
int main() {
vector<int> arr = {5, 2, 7, 8, 6};
int N = arr.size();
Solution solution;
int result = solution.minDecreasingSub(N, arr);
cout << "Length of the minimum decreasing subsequence: " << result << endl;
return 0;
}
|
Java
import java.util.ArrayList;
import java.util.Collections;
class Solution {
public int minDecreasingSub(int N, ArrayList<Integer> arr) {
ArrayList<Integer> seq = new ArrayList<>();
seq.add(arr.get(0));
for (int i = 1; i < N; i++) {
int ind = Collections.binarySearch(seq, arr.get(i));
ind = (ind < 0) ? -ind - 1 : ind;
if (ind == seq.size())
seq.add(arr.get(i));
else
seq.set(ind, arr.get(i));
}
return seq.size();
}
public static void main(String[] args) {
ArrayList<Integer> arr = new ArrayList<>();
arr.add(5);
arr.add(2);
arr.add(7);
arr.add(8);
arr.add(6);
int N = arr.size();
Solution solution = new Solution();
int result = solution.minDecreasingSub(N, arr);
System.out.println("Length of the minimum decreasing subsequence: " + result);
}
}
|
Python
class Solution:
def min_decreasing_sub(self, N, arr):
seq = [arr[0]]
for i in range(1, N):
ind = self.binary_search(seq, arr[i])
if ind == len(seq):
seq.append(arr[i])
else:
seq[ind] = arr[i]
return len(seq)
def binary_search(self, seq, target):
low, high = 0, len(seq)
while low < high:
mid = (low + high) // 2
if seq[mid] < target:
low = mid + 1
else:
high = mid
return low
arr = [5, 2, 7, 8, 6]
N = len(arr)
solution = Solution()
result = solution.min_decreasing_sub(N, arr)
print("Length of the minimum decreasing subsequence:", result)
|
C#
using System;
class Solution {
public int MinDecreasingSub(int N, int[] arr)
{
int[] seq = new int[] { arr[0] };
for (int i = 1; i < N; i++) {
int ind = BinarySearch(seq, arr[i]);
if (ind == seq.Length) {
Array.Resize(ref seq, seq.Length + 1);
seq[ind] = arr[i];
}
else {
seq[ind] = arr[i];
}
}
return seq.Length;
}
private int BinarySearch(int[] seq, int target)
{
int low = 0, high = seq.Length;
while (low < high) {
int mid = (low + high) / 2;
if (seq[mid] < target) {
low = mid + 1;
}
else {
high = mid;
}
}
return low;
}
}
class Program {
static void Main()
{
int[] arr = { 5, 2, 7, 8, 6 };
int N = arr.Length;
Solution solution = new Solution();
int result = solution.MinDecreasingSub(N, arr);
Console.WriteLine(
"Length of the minimum decreasing subsequence: "
+ result);
}
}
|
Javascript
class Solution {
minDecreasingSub(N, arr) {
let seq = [];
seq.push(arr[0]);
for (let i = 1; i < N; i++) {
let ind = this.upperBound(seq, arr[i]);
if (ind === seq.length)
seq.push(arr[i]);
else
seq[ind] = arr[i];
}
return seq.length;
}
upperBound(seq, target) {
let left = 0;
let right = seq.length;
while (left < right) {
let mid = Math.floor((left + right) / 2);
if (seq[mid] <= target) {
left = mid + 1;
} else {
right = mid;
}
}
return left;
}
}
let arr = [5, 2, 7, 8, 6];
let N = arr.length;
let solution = new Solution();
let result = solution.minDecreasingSub(N, arr);
console.log("Length of the minimum decreasing subsequence: " + result);
|
Output
Length of the minimum decreasing subsequence: 3
Time Complexity: O(N log N), where N is the length of array arr[].
Auxiliary Space: O(N)
|
