Greedy: Given an array and a value k, check if we can have k consecutive numbers

Problem Statement:

Given an array and a value k, check if we can have k consecutive numbers

Example:

Input: arr = [1, 2, 3, 4, 5, 6, 7, 8] k = 4

Output: True

Explanation: [1, 2, 3, 4] [5, 6, 7, 8]

Solution Explanation:

We will use sorting along with frequency array to solve the problem.

First we sort the array, then we will use frequency array to count the number of frequency of each element.

Then we iterate through the array and form the group by checking if the numbers are consecutive and return the result.

Time Complexity: O(nlogn)
Space Complexity: O(n)

Code Solution

#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
#include <algorithm>
using namespace std;

bool solution(vector<int>& nums, int k) 
{
    
    int n = nums.size();
    
    //if the size of the array is not divisible by k, then return false.
    if(n % k)
        return false;
        
    sort(nums.begin(), nums.end());
        
    unordered_map<int, int> freq;
    
    for(int i = 0; i < n; i++)
    {
        freq[nums[i]]++;
    }
        
    for(int i = 0; i < n; i++)
    {   
    	// if the occurance of the 
    	// element is already included
        if(freq[nums[i]] == 0)
            continue;
                
        freq[nums[i]]--;
                
        for(int j = 1; j < k; j++)
        {            
            if(freq[nums[i] + j] == 0)
                return false;
                       
            freq[nums[i] + j]--;
        }
    }
    
    return true;
}

int main()
{
    vector<int> arr = { 1, 2, 3, 4, 5, 6, 7, 8};
    int K = 4;
    cout << (solution(arr, K) ? "Yes" : "No");

    return 0;
}

Output

Yes