Checking for Consecutive K-Length Subsequence using Hashing
Keep two maps to keep track of the count of each number that hasn’t been used in a sequence other to keep track of the count of sequences that are currently “open” or started but not completed. Now, every element has two options, first: either include this current element into the already existing consecutive increasing sequence which is of length at least k, second: it can start its new consecutive increasing sequence of at least k length. At any point of time, if we are not able to do so, then we return false. Finally, we return true.
- Keep two maps, to keep track of unused elements (notUsed) and open sequences (opening).
- Store the frequency of input elements in the notUsed map.
- Loop through the input array:
- Check if the current number can be used:
- If there’s an open sequence starting with the current element, close it and open a new one with the next number.
- If there’s no open sequence starting with the current number, start a new sequence of length k from the current element, decrementing counts for subsequent numbers and checking if there are enough remaining occurrences.
- If at any point, it’s not possible to create a valid sequence, return false.
- Check if the current number can be used:
- If all numbers have been successfully used to form sequences, return true.
Below is the implementation of the above approach:
C++
// C++ code for the above approach: #include <bits/stdc++.h> using namespace std; // Function to check if it is possible to // arrange given numbers in k-length sequences bool isPossible(vector< int >& arr, int k) { int n = arr.size(); unordered_map< int , int > notUsed, opening; // Count the occurrences of each number // in the input array for ( int i = 0; i < n; i++) notUsed[arr[i]]++; // Iterate through the input array for ( int i = 0; i < n; i++) { if (notUsed[arr[i]]) { if (opening[arr[i]]) { // If there's an open sequence // starting with arr[i], close // it and open a new one notUsed[arr[i]]--; opening[arr[i]]--; opening[arr[i] + 1]++; } else { // Start a new sequence of length // k starting with arr[i] for ( int j = 1; j <= k - 1; j++) { notUsed[arr[i] + j]--; // If there aren't enough // remaining elements to // complete the sequence, // return false if (notUsed[arr[i] + j] < 0) return false ; } opening[arr[i] + k]++; } } } return true ; } // Drivers code int main() { vector< int > arr = { 1, 2, 3, 3, 4, 4, 5, 5 }; int k = 3; // Print "true" if it's possible to arrange // the numbers, otherwise print "false" cout << (isPossible(arr, k) ? "true" : "false" ); return 0; } |
Java
// Java Implementation import java.util.HashMap; import java.util.Map; public class Main { public static void main(String[] args) { int [] arr = { 1 , 2 , 3 , 3 , 4 , 4 , 5 , 5 }; int k = 3 ; // Print "true" if it's possible to arrange // the numbers, otherwise print "false" System.out.println(isPossible(arr, k) ? "true" : "false" ); } // Function to check if it is possible to // arrange given numbers in k-length sequences public static boolean isPossible( int [] arr, int k) { int n = arr.length; Map<Integer, Integer> notUsed = new HashMap<>(); Map<Integer, Integer> opening = new HashMap<>(); // Count the occurrences of each number // in the input array for ( int i = 0 ; i < n; i++) { notUsed.put(arr[i], notUsed.getOrDefault(arr[i], 0 ) + 1 ); } // Iterate through the input array for ( int i = 0 ; i < n; i++) { if (notUsed.get(arr[i]) > 0 ) { if (opening.getOrDefault(arr[i], 0 ) > 0 ) { // If there's an open sequence // starting with arr[i], close // it and open a new one notUsed.put(arr[i], notUsed.get(arr[i]) - 1 ); opening.put(arr[i], opening.get(arr[i]) - 1 ); opening.put(arr[i] + 1 , opening.getOrDefault(arr[i] + 1 , 0 ) + 1 ); } else { // Start a new sequence of length // k starting with arr[i] for ( int j = 1 ; j <= k - 1 ; j++) { notUsed.put(arr[i] + j, notUsed.getOrDefault(arr[i] + j, 0 ) - 1 ); // If there aren't enough // remaining elements to // complete the sequence, // return false if (notUsed.get(arr[i] + j) < 0 ) return false ; } opening.put(arr[i] + k, opening.getOrDefault(arr[i] + k, 0 ) + 1 ); } } } return true ; } } // Thsi code is contributed by Sakshi |
Python3
def is_possible(arr, k): n = len (arr) not_used = {} opening = {} # Count the occurrences of each number # in the input array for i in range (n): not_used[arr[i]] = not_used.get(arr[i], 0 ) + 1 # Iterate through the input array for i in range (n): if arr[i] in not_used and not_used[arr[i]] > 0 : if opening.get(arr[i], 0 ) > 0 : # If there's an open sequence # starting with arr[i], close # it and open a new one not_used[arr[i]] - = 1 opening[arr[i]] - = 1 opening[arr[i] + 1 ] = opening.get(arr[i] + 1 , 0 ) + 1 else : # Start a new sequence of length # k starting with arr[i] for j in range ( 1 , k): next_num = arr[i] + j if next_num in not_used and not_used[next_num] > 0 : not_used[next_num] - = 1 else : return False opening[arr[i] + k] = opening.get(arr[i] + k, 0 ) + 1 return True # Driver code arr = [ 1 , 2 , 3 , 3 , 4 , 4 , 5 , 5 ] k = 3 # Print "true" if it's possible to arrange # the numbers, otherwise print "false" print ( "true" if is_possible(arr, k) else "false" ) |
C#
using System; using System.Collections.Generic; class Program { // Function to check if it is possible to // arrange given numbers in k-length sequences static bool IsPossible(List< int > arr, int k) { int n = arr.Count; Dictionary< int , int > notUsed = new Dictionary< int , int >(); Dictionary< int , int > opening = new Dictionary< int , int >(); // Count the occurrences of each number // in the input array for ( int i = 0; i < n; i++) { if (notUsed.ContainsKey(arr[i])) notUsed[arr[i]]++; else notUsed[arr[i]] = 1; } // Iterate through the input array for ( int i = 0; i < n; i++) { if (notUsed[arr[i]] > 0) { if (opening.ContainsKey(arr[i]) && opening[arr[i]] > 0) { // If there's an open sequence // starting with arr[i], close // it and open a new one notUsed[arr[i]]--; opening[arr[i]]--; if (opening.ContainsKey(arr[i] + 1)) opening[arr[i] + 1]++; else opening[arr[i] + 1] = 1; } else { // Start a new sequence of length // k starting with arr[i] for ( int j = 1; j <= k - 1; j++) { notUsed[arr[i] + j]--; // If there aren't enough // remaining elements to // complete the sequence, // return false if (notUsed[arr[i] + j] < 0) return false ; } if (opening.ContainsKey(arr[i] + k)) opening[arr[i] + k]++; else opening[arr[i] + k] = 1; } } } return true ; } // Driver code static void Main( string [] args) { List< int > arr = new List< int > { 1, 2, 3, 3, 4, 4, 5, 5 }; int k = 3; // Print "true" if it's possible to arrange // the numbers, otherwise print "false" Console.WriteLine(IsPossible(arr, k) ? "true" : "false" ); } } |
Javascript
// Function to check if it is possible to // arrange given numbers in k-length sequences function isPossible(arr, k) { let notUsed = {}; let opening = {}; // Count the occurrences of each number // in the input array arr.forEach((num) => { notUsed[num] = (notUsed[num] || 0) + 1; }); // Iterate through the input array for (let i = 0; i < arr.length; i++) { if (notUsed[arr[i]]) { if (opening[arr[i]]) { // If there's an open sequence // starting with arr[i], close // it and open a new one notUsed[arr[i]]--; opening[arr[i]]--; opening[arr[i] + 1] = (opening[arr[i] + 1] || 0) + 1; } else { // Start a new sequence of length // k starting with arr[i] for (let j = 1; j <= k - 1; j++) { notUsed[arr[i] + j]--; // If there aren't enough // remaining elements to // complete the sequence, // return false if (notUsed[arr[i] + j] < 0) { return false ; } } opening[arr[i] + k] = (opening[arr[i] + k] || 0) + 1; } } } return true ; } // Driver code let arr = [1, 2, 3, 3, 4, 4, 5, 5]; let k = 3; // Print "true" if it's possible to arrange // the numbers, otherwise print "false" console.log(isPossible(arr, k) ? "true" : "false" ); |
true
Time Complexity: O(N), where N is the length of given input array arr[].
Auxiliary Space: O(N)
Checking for Consecutive K-Length Subsequence
Given an array arr[] of size N, the elements are non-decreasing order, the task is to determine if it’s possible to form one or more subsequences such that elements in each subsequence are a consecutive increasing sequence of K length at least.
Examples:
Input: arr = {1, 2, 3, 3, 4, 4, 5, 5}, K = 3
Output: true
Explanation: arr can be divided into the following subsequences: {1, 2, 3, 4, 5}, {3, 4, 5}Input: arr = {1,2,3,4,4,5}, K = 4
Output: false
Explanation: It is not possible to divide arr[] into consecutive increasing subsequences of length K or more.