Given an integer array arr[] that is sorted in increasing order and an integer K. Check whether it is possible to split arr[] into one or more subsequences such that both of the following conditions are true:
- Each subsequence is a consecutive increasing sequence (i.e. each integer is exactly one more than the previous integer).
- All subsequences have a length of K or more.
Examples:
Input: arr = [1, 2, 3, 3, 4, 5], k = 3
Output: true
Explanation: arr can be split into the following subsequences:
[1, 2, 3, 3, 4, 5] –> 1, 2, 3
[1, 2, 3, 3, 4, 5] –> 3, 4, 5Input: arr = [1, 1, 1, 1, 1], k = 4
Output: false
Explanation: It is impossible to split arr into consecutive increasing subsequences of length 4 or more.Input: arr = [1, 2, 3, 4, 4, 5], k=5
Output: false
Explanation: It is impossible to split arr into consecutive increasing subsequences of length k or more.
Approach: To solve the problem follow the below idea:
The idea to solve the problem is we can use a Min-Heap to store the current number and the count of the assumed subarray.
- We use a Min Heap to keep track of the current number and its assumed subarray count.
- Start with an empty Heap, indicating we haven’t begun processing elements yet.
- For the first element, set it as the starting point of the assumed subarray with a size of 1, then insert it into the Heap.
- For each subsequent element:
- Compare it with the top element in the Heap (which has the smallest number with the fewest subarray elements).
- If they are equal, increment the subarray count.
- If they are consecutive, create a new pair with the current element and its count, then insert it into the Heap while removing the top element.
- If neither condition holds, check if the count of the top pair in the Heap is greater than or equal to k. If so, remove it; otherwise, return false.
- Continue this process until all elements are processed.
- After traversal, inspect any remaining elements in the Heap. If there are identical elements pushed sequentially, consider them as potential starting points of subarrays (with a count not exceeding 1). If such elements exist, return false.
- If all conditions are met without encountering a false condition, return true.
Below is the implementation of the above approach:
C++14
// C++ code for the above approach:#include <bits/stdc++.h>using namespace std;// Comparator Function for// our Priority_queueclass comparison {public: bool operator()(pair<int, int> a, pair<int, int> b) { if (a.first == b.first) { return a.second > b.second; } else { return a.first > b.first; } }};bool isPossible(vector<int>& nums, int k){ // Min heap for storing the // current number and the // current subset's // length count priority_queue<pair<int, int>, vector<pair<int, int> >, comparison> pq; int i = 0; while (i < nums.size()) { // if the Heap is empty // at starting if (pq.empty()) { pq.push({ nums[i], 1 }); i++; } else { // Continue adding and creating // subset if the next element // is same as previous if (nums[i] == pq.top().first) { pq.push({ nums[i], 1 }); i++; } // If the next element is // consecutive to last element // that is nums[i]-pq.top.second==1 else if (nums[i] == pq.top().first + 1) { // temp stores the top // of the Min Heap. auto temp = pq.top(); // Remove the last element pq.pop(); pq.push({ nums[i], temp.second + 1 }); i++; } else { // Check if the length // of subset if less than // k or not if (pq.top().second < k) { return false; } // if the length is equal // to greater than k pop out // the last subset pair. pq.pop(); } } } // Check if the Heap contains // pairs which have been // formed by repeated elements // and have not been popped out. while (!pq.empty()) { if (pq.top().second < k) { return false; } pq.pop(); } // Else return true. return true;}// Driver Codeint main(){ vector<int> vec = { 1, 2, 3, 3, 4, 5 }; int k = 3; // Function call if (isPossible(vec, k)) { cout << "True" << endl; } else { cout << "False" << endl; } return 0;} |
Java
import java.util.*;class Solution { public static boolean isPossible(List<Integer> nums, int k) { // Create a priority queue to store pairs of values and their counts PriorityQueue<Pair<Integer, Integer>> pq = new PriorityQueue<>(new Comparator<Pair<Integer, Integer>>() { @Override public int compare(Pair<Integer, Integer> a, Pair<Integer, Integer> b) { // Compare pairs based on their keys (values) and then on their values (counts) if (a.getKey().equals(b.getKey())) { return a.getValue() - b.getValue(); } else { return a.getKey() - b.getKey(); } } }); int i = 0; while (i < nums.size()) { if (pq.isEmpty()) { // If the priority queue is empty, add a new pair with the current number and count of 1 pq.add(new Pair<>(nums.get(i), 1)); i++; } else { if (nums.get(i).equals(pq.peek().getKey())) { // If the current number is equal to the key of the top pair, add a new pair with the current number and count of 1 pq.add(new Pair<>(nums.get(i), 1)); i++; } else if (nums.get(i) == pq.peek().getKey() + 1) { // If the current number is one greater than the key of the top pair, update the top pair's count Pair<Integer, Integer> temp = pq.poll(); pq.add(new Pair<>(nums.get(i), temp.getValue() + 1)); i++; } else { if (pq.peek().getValue() < k) { // If the top pair's count is less than k, return false return false; } pq.poll(); } } } // Check if any remaining pairs in the priority queue have counts less than k while (!pq.isEmpty()) { if (pq.peek().getValue() < k) { return false; } pq.poll(); } // If all pairs have counts greater than or equal to k, return true return true; } public static void main(String[] args) { List<Integer> vec = Arrays.asList(1, 2, 3, 3, 4, 5); int k = 3; if (isPossible(vec, k)) { System.out.println("True"); } else { System.out.println("False"); } }}class Pair<K, V> { private final K key; private final V value; public Pair(K key, V value) { this.key = key; this.value = value; } public K getKey() { return key; } public V getValue() { return value; }}//This code is Contributed by chinmaya121221 |
Python3
import heapq# Comparator Function for# our Priority_queueclass Comparison: def __call__(self, a, b): if a[0] == b[0]: return a[1] > b[1] else: return a[0] > b[0]def is_possible(nums, k): # Min heap for storing the # current number and the # current subset's # length count pq = [] i = 0 while i < len(nums): # if the Heap is empty # at starting if not pq: heapq.heappush(pq, (nums[i], 1)) i += 1 else: # Continue adding and creating # subset if the next element # is same as previous if nums[i] == pq[0][0]: heapq.heappush(pq, (nums[i], 1)) i += 1 # If the next element is # consecutive to last element # that is nums[i]-pq.top.second==1 elif nums[i] == pq[0][0] + 1: # temp stores the top # of the Min Heap. # Remove the last element temp = heapq.heappop(pq) heapq.heappush(pq, (nums[i], temp[1] + 1)) i += 1 else: # Check if the length # of subset if less than # k or not if pq[0][1] < k: return False # if the length is equal # to greater than k pop out # the last subset pair. heapq.heappop(pq) # Check if the Heap contains # pairs which have been # formed by repeated elements # and have not been popped out. while pq: if pq[0][1] < k: return False heapq.heappop(pq) # Else return true. return True# Driver Codevec = [1, 2, 3, 3, 4, 5]k = 3if is_possible(vec, k): print("True")else: print("False") |
C#
using System;using System.Collections.Generic;public class GFG{ public static bool IsPossible(List<int> nums, int k) { // Create a priority queue to store pairs of values and their counts PriorityQueue<Pair<int, int>> pq = new PriorityQueue<Pair<int, int>>(new PairComparer()); int i = 0; while (i < nums.Count) { if (pq.Count == 0) { // If the priority queue is empty, add a new pair with the current number and count of 1 pq.Enqueue(new Pair<int, int>(nums[i], 1)); i++; } else { if (nums[i] == pq.Peek().Key) { // If the current number is equal to the key of the top pair, add a new pair with the current number and count of 1 pq.Enqueue(new Pair<int, int>(nums[i], 1)); i++; } else if (nums[i] == pq.Peek().Key + 1) { // If the current number is one greater than the key of the top pair, update the top pair's count Pair<int, int> temp = pq.Dequeue(); pq.Enqueue(new Pair<int, int>(nums[i], temp.Value + 1)); i++; } else { if (pq.Peek().Value < k) { // If the top pair's count is less than k, return false return false; } pq.Dequeue(); } } } // Check if any remaining pairs in the priority queue have counts less than k while (pq.Count > 0) { if (pq.Peek().Value < k) { return false; } pq.Dequeue(); } // If all pairs have counts greater than or equal to k, return true return true; } public static void Main(string[] args) { List<int> vec = new List<int> { 1, 2, 3, 3, 4, 5 }; int k = 3; if (IsPossible(vec, k)) { Console.WriteLine("True"); } else { Console.WriteLine("False"); } }}public class Pair<K, V>{ public K Key { get; } public V Value { get; } public Pair(K key, V value) { Key = key; Value = value; }}public class PairComparer : IComparer<Pair<int, int>>{ public int Compare(Pair<int, int> a, Pair<int, int> b) { // Compare pairs based on their keys (values) and then on their values (counts) if (a.Key == b.Key) { return a.Value - b.Value; } else { return a.Key - b.Key; } }}public class PriorityQueue<T>{ private List<T> data; private IComparer<T> comparer; public PriorityQueue(IComparer<T> comparer) { this.data = new List<T>(); this.comparer = comparer; } public int Count { get { return data.Count; } } public T Peek() { return data[0]; } public void Enqueue(T item) { data.Add(item); int childIndex = data.Count - 1; while (childIndex > 0) { int parentIndex = (childIndex - 1) / 2; if (comparer.Compare(data[childIndex], data[parentIndex]) >= 0) break; T tmp = data[childIndex]; data[childIndex] = data[parentIndex]; data[parentIndex] = tmp; childIndex = parentIndex; } } public T Dequeue() { int lastIndex = data.Count - 1; T frontItem = data[0]; data[0] = data[lastIndex]; data.RemoveAt(lastIndex); lastIndex--; int parentIndex = 0; while (true) { int leftChild = parentIndex * 2 + 1; if (leftChild > lastIndex) break; int rightChild = leftChild + 1; if (rightChild <= lastIndex && comparer.Compare(data[rightChild], data[leftChild]) < 0) leftChild = rightChild; if (comparer.Compare(data[parentIndex], data[leftChild]) <= 0) break; T tmp = data[parentIndex]; data[parentIndex] = data[leftChild]; data[leftChild] = tmp; parentIndex = leftChild; } return frontItem; }} |
Javascript
class PriorityQueue { constructor() { this.queue = []; } push(item) { this.queue.push(item); this.queue.sort((a, b) => { if (a[0] === b[0]) { return a[1] - b[1]; } else { return a[0] - b[0]; } }); } pop() { return this.queue.shift(); } top() { return this.queue[0]; } empty() { return this.queue.length === 0; }}function isPossible(nums, k) { const pq = new PriorityQueue(); let i = 0; while (i < nums.length) { if (pq.empty()) { pq.push([nums[i], 1]); i++; } else { if (nums[i] === pq.top()[0]) { pq.push([nums[i], 1]); i++; } else if (nums[i] === pq.top()[0] + 1) { const temp = pq.pop(); pq.push([nums[i], temp[1] + 1]); i++; } else { if (pq.top()[1] < k) { return false; } pq.pop(); } } } while (!pq.empty()) { if (pq.top()[1] < k) { return false; } pq.pop(); } return true;}const vec = [1, 2, 3, 3, 4, 5];const k = 3;if (isPossible(vec, k)) { console.log("True");} else { console.log("False");} |
Output
True
Time Complexity: O(N*log N), where N is the number of elements in the input array.
Auxiliary Space: O(N) used by Heap.
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!
Share your thoughts in the comments
