Given an array arr[] containing n integers. The problem is to count number of increasing subsequences in the array of size k.
Examples:
Input : arr[] = {2, 6, 4, 5, 7},
k = 3
Output : 5
The subsequences of size '3' are:
{2, 6, 7}, {2, 4, 5}, {2, 4, 7},
{2, 5, 7} and {4, 5, 7}.
Input : arr[] = {12, 8, 11, 13, 10, 15, 14, 16, 20},
k = 4
Output : 39
Approach: The idea is to use Dynamic Programming by define 2D matrix, say dp[][]. dp[i][j] stores the count of increasing subsequences of size i ending with element arr[j]. So dp[i][j] can be defined as:
dp[i][j] = 1, where i = 1 and 1 <= j <= n
dp[i][j] = sum(dp[i-1][j]), where 1 < i <= k, i <= j <= n and arr[m] < arr[j] for (i-1) <= m < j.
Below is the implementation of above approach:
C++
// C++ implementation to count number of// increasing subsequences of size k#include <bits/stdc++.h>using namespace std;// function to count number of increasing// subsequences of size kint numOfIncSubseqOfSizeK(int arr[], int n, int k){ int dp[k][n], sum = 0; memset(dp, 0, sizeof(dp)); // count of increasing subsequences of size 1 // ending at each arr[i] for (int i = 0; i < n; i++) dp[0][i] = 1; // building up the matrix dp[][] // Here 'l' signifies the size of // increasing subsequence of size (l+1). for (int l = 1; l < k; l++) { // for each increasing subsequence of size 'l' // ending with element arr[i] for (int i = l; i < n; i++) { // count of increasing subsequences of size 'l' // ending with element arr[i] dp[l][i] = 0; for (int j = l - 1; j < i; j++) { if (arr[j] < arr[i]) dp[l][i] += dp[l - 1][j]; } } } // sum up the count of increasing subsequences of // size 'k' ending at each element arr[i] for (int i = k - 1; i < n; i++) sum += dp[k - 1][i]; // required number of increasing // subsequences of size k return sum;}// Driver program to test aboveint main(){ int arr[] = { 12, 8, 11, 13, 10, 15, 14, 16, 20 }; int n = sizeof(arr) / sizeof(arr[0]); int k = 4; cout << "Number of Increasing Subsequences of size " << k << " = " << numOfIncSubseqOfSizeK(arr, n, k); return 0;} |
Java
//Java implementation to count number of// increasing subsequences of size kclass GFG {// function to count number of increasing// subsequences of size k static int numOfIncSubseqOfSizeK(int arr[], int n, int k) { int dp[][] = new int[k][n], sum = 0; // count of increasing subsequences of size 1 // ending at each arr[i] for (int i = 0; i < n; i++) { dp[0][i] = 1; } // building up the matrix dp[][] // Here 'l' signifies the size of // increasing subsequence of size (l+1). for (int l = 1; l < k; l++) { // for each increasing subsequence of size 'l' // ending with element arr[i] for (int i = l; i < n; i++) { // count of increasing subsequences of size 'l' // ending with element arr[i] dp[l][i] = 0; for (int j = l - 1; j < i; j++) { if (arr[j] < arr[i]) { dp[l][i] += dp[l - 1][j]; } } } } // sum up the count of increasing subsequences of // size 'k' ending at each element arr[i] for (int i = k - 1; i < n; i++) { sum += dp[k - 1][i]; } // required number of increasing // subsequences of size k return sum; }// Driver program to test above public static void main(String[] args) { int arr[] = {12, 8, 11, 13, 10, 15, 14, 16, 20}; int n = arr.length; int k = 4; System.out.print("Number of Increasing Subsequences of size " + k + " = " + numOfIncSubseqOfSizeK(arr, n, k)); }}// This code is contributed by 29AjayKumar |
Python3
# Python3 implementation to count number # of increasing subsequences of size kimport math as mt# function to count number of increasing# subsequences of size kdef numOfIncSubseqOfSizeK(arr, n, k): dp = [[0 for i in range(n)] for i in range(k)] # count of increasing subsequences # of size 1 ending at each arr[i] for i in range(n): dp[0][i] = 1 # building up the matrix dp[][] # Here 'l' signifies the size of # increasing subsequence of size (l+1). for l in range(1, k): # for each increasing subsequence of # size 'l' ending with element arr[i] for i in range(l, n): # count of increasing subsequences of # size 'l' ending with element arr[i] dp[l][i] = 0 for j in range(l - 1, i): if (arr[j] < arr[i]): dp[l][i] += dp[l - 1][j] # Sum up the count of increasing subsequences # of size 'k' ending at each element arr[i] Sum = 0 for i in range(k - 1, n): Sum += dp[k - 1][i] # required number of increasing # subsequences of size k return Sum# Driver Codearr = [12, 8, 11, 13, 10, 15, 14, 16, 20 ]n = len(arr)k = 4print("Number of Increasing Subsequences of size", k, "=", numOfIncSubseqOfSizeK(arr, n, k))# This code is contributed by# Mohit kumar 29 |
C#
// C# implementation to count number of// increasing subsequences of size k using System; public class GFG { // function to count number of increasing// subsequences of size k static int numOfIncSubseqOfSizeK(int []arr, int n, int k) { int [,]dp = new int[k,n]; int sum = 0; // count of increasing subsequences of size 1 // ending at each arr[i] for (int i = 0; i < n; i++) { dp[0,i] = 1; } // building up the matrix dp[,] // Here 'l' signifies the size of // increasing subsequence of size (l+1). for (int l = 1; l < k; l++) { // for each increasing subsequence of size 'l' // ending with element arr[i] for (int i = l; i < n; i++) { // count of increasing subsequences of size 'l' // ending with element arr[i] dp[l,i] = 0; for (int j = l - 1; j < i; j++) { if (arr[j] < arr[i]) { dp[l,i] += dp[l - 1,j]; } } } } // sum up the count of increasing subsequences of // size 'k' ending at each element arr[i] for (int i = k - 1; i < n; i++) { sum += dp[k - 1,i]; } // required number of increasing // subsequences of size k return sum; } // Driver program to test above public static void Main() { int []arr = {12, 8, 11, 13, 10, 15, 14, 16, 20}; int n = arr.Length; int k = 4; Console.Write("Number of Increasing Subsequences of size " + k + " = " + numOfIncSubseqOfSizeK(arr, n, k)); }}// This code is contributed by 29AjayKumar |
PHP
<?php// PHP implementation to count // number of increasing // subsequences of size k// function to count number// of increasing subsequences// of size kfunction numOfIncSubseqOfSizeK($arr, $n, $k){ $dp = array(array()); $sum = 0; $dp = array_fill(0, $n + 1, false); // count of increasing // subsequences of size 1 // ending at each arr[i] for ($i = 0; $i < $n; $i++) $dp[0][$i] = 1; // building up the matrix // dp[][]. Here 'l' signifies // the size of increasing // subsequence of size (l+1). for ($l = 1; $l < $k; $l++) { // for each increasing // subsequence of size 'l' // ending with element arr[i] for ($i = $l; $i < $n; $i++) { // count of increasing // subsequences of size 'l' // ending with element arr[i] $dp[$l][$i] = 0; for ($j = $l - 1; $j < $i; $j++) { if ($arr[$j] < $arr[$i]) $dp[$l][$i] += $dp[$l - 1][$j]; } } } // sum up the count of increasing // subsequences of size 'k' ending // at each element arr[i] for ($i = $k - 1; $i < $n; $i++) $sum += $dp[$k - 1][$i]; // required number of increasing // subsequences of size k return $sum;}// Driver Code$arr = array(12, 8, 11, 13, 10, 15, 14, 16, 20);$n = sizeof($arr);$k = 4;echo "Number of Increasing ". "Subsequences of size ", $k , " = " , numOfIncSubseqOfSizeK($arr, $n, $k);// This code is contributed // by akt_mit?> |
Javascript
<script>// JavaScript implementation to count number of// increasing subsequences of size k// function to count number of increasing// subsequences of size k function numOfIncSubseqOfSizeK(arr, n, k) { let dp = new Array(k), sum = 0; // Loop to create 2D array using 1D array for (let i = 0; i < dp.length; i++) { dp[i] = new Array(2); } // count of increasing subsequences of size 1 // ending at each arr[i] for (let i = 0; i < n; i++) { dp[0][i] = 1; } // building up the matrix dp[][] // Here 'l' signifies the size of // increasing subsequence of size (l+1). for (let l = 1; l < k; l++) { // for each increasing subsequence of size 'l' // ending with element arr[i] for (let i = l; i < n; i++) { // count of increasing subsequences of size 'l' // ending with element arr[i] dp[l][i] = 0; for (let j = l - 1; j < i; j++) { if (arr[j] < arr[i]) { dp[l][i] += dp[l - 1][j]; } } } } // sum up the count of increasing subsequences of // size 'k' ending at each element arr[i] for (let i = k - 1; i < n; i++) { sum += dp[k - 1][i]; } // required number of increasing // subsequences of size k return sum; }// Driver code let arr = [12, 8, 11, 13, 10, 15, 14, 16, 20]; let n = arr.length; let k = 4; document.write("Number of Increasing Subsequences of size " + k + " = " + numOfIncSubseqOfSizeK(arr, n, k)); </script> |
Output
Number of Increasing Subsequences of size 4 = 39
Time Complexity: O(kn2).
Auxiliary Space: O(kn).
Segment Tree Approach
For every element arr[i], we need to search for all arr[i]-1 as these are the elements that can be appended to arr[i] to make increasing subsequence. This is very much similar to COUNT LONGEST INCREASING SUBSEQUENCES. We use a vector of size K for each node in segment Tree signifying the length of LIS of size K ending at node.
Stepping down the array to smaller numbers with same ordering will reduce the space complexity as well.
If arr[i] has vector K={1,3,2}, signifies there is one K=1 length LIS ending at arr[i]
three K=2 length LIS ending at arr[i]
two K=3 length LIS ending at arr[i]
If arr[j] is greater than arr[i], then arr[j] can appended after arr[i]. So the vector of arr[j] becomes {1,1,3}.
The K=1 remains the same since every element itself is a single length(K=1) subsequence.
We will take subsequences of length K=1 from arr[i] in the K=2 of arr[j] Since all the K=1 increasing subsequences of arr[i] becomes K=2 length increasing subsequences when arr[j] is added to arr[i].
Similarly all the K=2 length subsequences of arr[i] becomes K=3 length subsequences for arr[j] as arr[j] gets appended to K=2 subsequences of arr[i]. We are not adding here, because we are calculating ways, not length.
Simply saying vec_j[K]=vec_i[K-1], where K>1
Below is the implementation of above approach:
C++
#include <bits/stdc++.h>using namespace std;vector<vector<long long>>tree; /* vector<long long> represents the number of ways LIS of size K ending at node can be formed */int RANKER(vector<int>& arr) { int n = arr.size(); vector<int> temp = arr; sort(temp.begin(), temp.end()); unordered_map<int, int> mpp; int mx = 0; for (int i = 0; i < n; i++) { if (mpp.find(temp[i]) == mpp.end()) { mpp[temp[i]] = mx; mx++; } } for (int i = 0; i < n; i++) { arr[i] = mpp[arr[i]]; } return mx;}vector<long long> summation(vector<long long>& left, vector<long long>& right, int k) { // ADD WAYS, REMEMBER NO NEED TO TAKE MAX, WE ARE FINDING WAYS, NOT LENGTH. // So each K will contribute to final answer vector<long long> res(k + 1, 0); for (int i = 1; i <= k; i++) { res[i] = left[i] + right[i]; } return res;}vector<long long> query(int start, int end, int parent, int qstart, int qend, int k) { if (end < qstart || qend < start) { return vector<long long>(k + 1, 0); } if (qstart <= start && qend >= end) { return tree[parent]; } int mid = (start + end) / 2; vector<long long> left = query(start, mid, 2 * parent + 1, qstart, qend, k); vector<long long> right = query(mid + 1, end, 2 * parent + 2, qstart, qend, k); return summation(left, right, k);}void update(int start, int end, int parent, int index, vector<long long>& updateThis, int k) { if (index < start || index > end) { return; } if (start == end) { tree[parent] = summation(updateThis, tree[parent], k); return; } int mid = (start + end) / 2; if (index > mid) { update(mid + 1, end, 2 * parent + 2, index, updateThis, k); } else { update(start, mid, 2 * parent + 1, index, updateThis, k); } vector<long long> left = tree[2 * parent + 1]; vector<long long> right = tree[2 * parent + 2]; tree[parent] = summation(left, right, k); return;}int numOfIncSubseqOfSizeK(vector<int>& arr, int K) { int n = arr.size(); int mx = RANKER(arr); tree.resize(4 * mx + 1, vector<long long>(K + 1, 0)); for (int i = 0; i < n; i++) { vector<long long> Kj(K + 1, 0); // K length ways Kj[1] = 1; // K=1 is element itself if (arr[i] > 0) { // arr[0] cannot be queried, since its the lowest /* Querying the longest LIS K array where arr[i] can append to*/ vector<long long> Ki = query(0, mx, 0, 0, arr[i] - 1, K); for (int k = 2; k <= K; k++) { // As explained before Kj[k] = Ki[k - 1]; } } update(0, mx, 0, arr[i], Kj, K); // update Kj array for arr[i] } return tree[0][K]; // answer is at kth index of root's K array}int main() { vector<int> arr = { 12, 8, 11, 13, 10, 15, 14, 16, 20 }; int k = 4; cout << "Number of Increasing Subsequences of size " << k << " = " << numOfIncSubseqOfSizeK(arr, k); return 0;}// Code by RainX (ABHIJIT ROY, NIT AGARTALA) |
Python3
from typing import List, Dicttree = []def RANKER(arr: List[int]) -> int: n = len(arr) temp = arr.copy() temp.sort() mpp = {} mx = 0 for i in range(n): if temp[i] not in mpp: mpp[temp[i]] = mx mx += 1 for i in range(n): arr[i] = mpp[arr[i]] return mxdef summation(left: List[int], right: List[int], k: int) -> List[int]: # ADD WAYS, REMEMBER NO NEED TO TAKE MAX, WE ARE FINDING WAYS, NOT LENGTH. # So each K will contribute to final answer res = [0] * (k + 1) for i in range(1, k+1): res[i] = left[i] + right[i] return resdef query(start: int, end: int, parent: int, qstart: int, qend: int, k: int) -> List[int]: if end < qstart or qend < start: return [0] * (k + 1) if qstart <= start and qend >= end: return tree[parent] mid = (start + end) // 2 left = query(start, mid, 2 * parent + 1, qstart, qend, k) right = query(mid + 1, end, 2 * parent + 2, qstart, qend, k) return summation(left, right, k)def update(start: int, end: int, parent: int, index: int, updateThis: List[int], k: int) -> None: if index < start or index > end: return if start == end: tree[parent] = summation(updateThis, tree[parent], k) return mid = (start + end) // 2 if index > mid: update(mid + 1, end, 2 * parent + 2, index, updateThis, k) else: update(start, mid, 2 * parent + 1, index, updateThis, k) left = tree[2 * parent + 1] right = tree[2 * parent + 2] tree[parent] = summation(left, right, k) returndef numOfIncSubseqOfSizeK(arr: List[int], K: int) -> int: n = len(arr) mx = RANKER(arr) global tree tree = [[0] * (K + 1) for _ in range(4 * mx + 1)] for i in range(n): # K length ways Kj = [0] * (K + 1) # K=1 is element itself Kj[1] = 1 # arr[0] cannot be queried, since its the lowest if arr[i] > 0: # Querying the longest LIS K array where arr[i] can append to Ki = query(0, mx, 0, 0, arr[i] - 1, K) # As explained before for k in range(2, K+1): Kj[k] = Ki[k - 1] # update Kj array for arr[i] update(0, mx, 0, arr[i], Kj, K) # answer is at kth index of root's K array return tree[0][K]if __name__ == '__main__': arr = [12, 8, 11, 13, 10, 15, 14, 16, 20] k = 4 print("Number of Increasing Subsequences of size", k, "=", numOfIncSubseqOfSizeK(arr, k))# This code is contributed by shivhack999 |
Javascript
let tree = []; /* array of arrays, where each inner array represents the number of ways LIS of size K ending at node can be formed */function RANKER(arr) { let n = arr.length; let temp = [...arr]; temp.sort((a, b) => a - b); let mpp = new Map(); let mx = 0; for (let i = 0; i < n; i++) { if (!mpp.has(temp[i])) { mpp.set(temp[i], mx); mx++; } } for (let i = 0; i < n; i++) { arr[i] = mpp.get(arr[i]); } return mx;}function summation(left, right, k) { // ADD WAYS, REMEMBER NO NEED TO TAKE MAX, WE ARE FINDING WAYS, NOT LENGTH. // So each K will contribute to final answer let res = new Array(k + 1).fill(0); for (let i = 1; i <= k; i++) { res[i] = left[i] + right[i]; } return res;}function query(start, end, parent, qstart, qend, k) { if (end < qstart || qend < start) { return new Array(k + 1).fill(0); } if (qstart <= start && qend >= end) { return tree[parent]; } let mid = Math.floor((start + end) / 2); let left = query(start, mid, 2 * parent + 1, qstart, qend, k); let right = query(mid + 1, end, 2 * parent + 2, qstart, qend, k); return summation(left, right, k);}function update(start, end, parent, index, updateThis, k) { if (index < start || index > end) { return; } if (start === end) { tree[parent] = summation(updateThis, tree[parent], k); return; } let mid = Math.floor((start + end) / 2); if (index > mid) { update(mid + 1, end, 2 * parent + 2, index, updateThis, k); } else { update(start, mid, 2 * parent + 1, index, updateThis, k); } let left = tree[2 * parent + 1]; let right = tree[2 * parent + 2]; tree[parent] = summation(left, right, k); return;}function numOfIncSubseqOfSizeK(arr, K) { const n = arr.length; const mx = RANKER(arr); tree = new Array(4 * mx + 1).fill().map(() => new Array(K + 1).fill(0)); for (let i = 0; i < n; i++) { const Kj = new Array(K + 1).fill(0); Kj[1] = 1; if (arr[i] > 0) { const Ki = query(0, mx, 0, 0, arr[i] - 1, K); for (let k = 2; k <= K; k++) { Kj[k] = Ki[k - 1]; } } update(0, mx, 0, arr[i], Kj, K); } return tree[0][K];}const arr = [12, 8, 11, 13, 10, 15, 14, 16, 20];const k = 4;console.log(`Number of Increasing Subsequences of size ${k} = ${numOfIncSubseqOfSizeK(arr, k)}`); |
Output
Number of Increasing Subsequences of size 4 = 39
Time Complexity: O(n*K*logn). For each index, we need to do query(logn) and update in K array(k)
Auxiliary Space: O(kn).
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!
