Horje
Split Array into Consecutive Subsequences of Size K or more.

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, 5

Input: 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_queue
class 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 Code
int 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_queue
class 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 Code
vec = [1, 2, 3, 3, 4, 5]
k = 3
 
if 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.


 


Reffered: https://www.geeksforgeeks.org

DSA

Related
Maximum Square Side length with M 1x1 and N 2x2 tiles Maximum Square Side length with M 1x1 and N 2x2 tiles
Number of K-Spikes in Stock Price Array Number of K-Spikes in Stock Price Array
Exploring Range Trees Exploring Range Trees
Count the participants defeating maximum individuals in a competition Count the participants defeating maximum individuals in a competition
GCD (Greatest Common Divisor) Practice Problems for Competitive Programming GCD (Greatest Common Divisor) Practice Problems for Competitive Programming

Type:
 Geek
Category:
 Coding
Sub Category:
 Tutorial
Uploaded by:
 Admin
Views:
 10



 

Horje