Given an array arr[] of size N, the task is to print the minimum possible count of strictly increasing subsequences present in the array.
Note: It is possible to swap the pairs of array elements.
Examples:
Input: arr[] = {2, 1, 2, 1, 4, 3}
Output: 2
Explanation: Sorting the array modifies the array to arr[] = {1, 1, 2, 2, 3, 4}. Two possible increasing subsequences are {1, 2, 3} and {1, 2, 4}, which involves all the array elements.Input: arr[] = {3, 3, 3}
Output: 3
MultiSet-based Approach: Refer to the previous post to solve the problem using Multiset to find the longest decreasing subsequence in the array.
Time Complexity: O(N2)
Auxiliary Space: O(N)
Space-Optimized Approach: The optimal idea is based on the following observation:
Two elements with the same value can’t be included in a single subsequence, as they won’t form a strictly increasing subsequence.
Therefore, for every distinct array element, count its frequency, say y. Therefore, at least y subsequences are required.
Hence, the frequency of the most occurring array element is the required answer.
Follow the steps below to solve the problem:
- Initialize a variable, say count, to store the final count of strictly increasing subsequences.
- Traverse the array arr[] and perform the following observations:
- Initialize two variables, say X, to store the current array element, and freqX to store the frequency of the current array element.
- Find and store all the occurrences of the current element in freqX.
- If the frequency of the current element is greater than the previous count, then update the count.
- Print the value of count.
Below is the implementation of the above approach:
C++
// C++ program for// the above approach#include <bits/stdc++.h>using namespace std;// Function to find the number of strictly// increasing subsequences in an arrayint minimumIncreasingSubsequences( int arr[], int N){ // Sort the array sort(arr, arr + N); // Stores final count // of subsequences int count = 0; int i = 0; // Traverse the array while (i < N) { // Stores current element int x = arr[i]; // Stores frequency of // the current element int freqX = 0; // Count frequency of // the current element while (i < N && arr[i] == x) { freqX++; i++; } // If current element frequency // is greater than count count = max(count, freqX); } // Print the final count cout << count;}// Driver Codeint main(){ // Given array int arr[] = { 2, 1, 2, 1, 4, 3 }; // Size of the array int N = sizeof(arr) / sizeof(arr[0]); // Function call to find // the number of strictly // increasing subsequences minimumIncreasingSubsequences(arr, N);} |
Java
// Java program to implement // the above approach import java.util.*;class GFG{ // Function to find the number of strictly// increasing subsequences in an arraystatic void minimumIncreasingSubsequences( int arr[], int N){ // Sort the array Arrays.sort(arr); // Stores final count // of subsequences int count = 0; int i = 0; // Traverse the array while (i < N) { // Stores current element int x = arr[i]; // Stores frequency of // the current element int freqX = 0; // Count frequency of // the current element while (i < N && arr[i] == x) { freqX++; i++; } // If current element frequency // is greater than count count = Math.max(count, freqX); } // Print the final count System.out.print(count);}// Driver Codepublic static void main(String args[]){ // Given array int arr[] = { 2, 1, 2, 1, 4, 3 }; // Size of the array int N = arr.length; // Function call to find // the number of strictly // increasing subsequences minimumIncreasingSubsequences(arr, N);}}// This code is contributed by splevel62. |
Python3
# Python3 program to implement # the above approach # Function to find the number of strictly# increasing subsequences in an arraydef minimumIncreasingSubsequences(arr, N) : # Sort the array arr.sort() # Stores final count # of subsequences count = 0 i = 0 # Traverse the array while (i < N) : # Stores current element x = arr[i] # Stores frequency of # the current element freqX = 0 # Count frequency of # the current element while (i < N and arr[i] == x) : freqX += 1 i += 1 # If current element frequency # is greater than count count = max(count, freqX) # Print the final count print(count)# Given arrayarr = [ 2, 1, 2, 1, 4, 3 ]# Size of the arrayN = len(arr)# Function call to find# the number of strictly# increasing subsequencesminimumIncreasingSubsequences(arr, N)# This code is contributed by divyesh072019. |
C#
// C# program to implement // the above approach using System;public class GFG{ // Function to find the number of strictly// increasing subsequences in an arraystatic void minimumIncreasingSubsequences( int []arr, int N){ // Sort the array Array.Sort(arr); // Stores readonly count // of subsequences int count = 0; int i = 0; // Traverse the array while (i < N) { // Stores current element int x = arr[i]; // Stores frequency of // the current element int freqX = 0; // Count frequency of // the current element while (i < N && arr[i] == x) { freqX++; i++; } // If current element frequency // is greater than count count = Math.Max(count, freqX); } // Print the readonly count Console.Write(count);}// Driver Codepublic static void Main(String []args){ // Given array int []arr = { 2, 1, 2, 1, 4, 3 }; // Size of the array int N = arr.Length; // Function call to find // the number of strictly // increasing subsequences minimumIncreasingSubsequences(arr, N);}}// This code is contributed by 29AjayKumar |
Javascript
<script> // Javascript program to implement the above approach // Function to find the number of strictly // increasing subsequences in an array function minimumIncreasingSubsequences(arr, N) { // Sort the array arr.sort(function(a, b){return a - b}); // Stores readonly count // of subsequences let count = 0; let i = 0; // Traverse the array while (i < N) { // Stores current element let x = arr[i]; // Stores frequency of // the current element let freqX = 0; // Count frequency of // the current element while (i < N && arr[i] == x) { freqX++; i++; } // If current element frequency // is greater than count count = Math.max(count, freqX); } // Print the readonly count document.write(count); } // Given array let arr = [ 2, 1, 2, 1, 4, 3 ]; // Size of the array let N = arr.length; // Function call to find // the number of strictly // increasing subsequences minimumIncreasingSubsequences(arr, N); // This code is contributed by suresh07.</script> |
Output:
2
Time Complexity: O(NlogN)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
