We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Divide Array in Sets of K Consecutive Numbers

Number: 1422

Difficulty: Medium

Paid? No

Companies: Google, TikTok

Problem Description

Given an array of integers and a positive integer k, determine if it is possible to divide the array into groups of k consecutive numbers.

Key Insights

  • The total number of elements must be divisible by k.
  • Use a frequency map (hash table) to count the occurrences of each number.
  • Sort the unique numbers to process them in ascending order.
  • Use a greedy approach: for the smallest available number, try to build a sequence of k consecutive numbers.
  • For each number in the sequence, ensure that there are enough occurrences; if not, the division is impossible.

Space and Time Complexity

Time Complexity: O(n log n) due to sorting of the unique numbers. Space Complexity: O(n) for storing the frequency count.

Solution

The solution uses a frequency dictionary to count the occurrences of each number. After confirming that the array’s length is divisible by k, we iterate through the sorted keys of the frequency dictionary. For each number, if its count is positive, we attempt to form a consecutive sequence of length k, starting from that number. We decrease the frequency for each number in the sequence by the count of the starting number. If at any point the next needed number does not have a sufficient count, we return false. Otherwise, after processing all numbers, we return true.

Code Solutions

import collections

def is_possible_divide(nums, k):
    # Check if total number of elements is divisible by k
    if len(nums) % k != 0:
        return False

    # Count the frequency of each number in the array
    num_count = collections.Counter(nums)
    
    # Iterate over the numbers in sorted order
    for num in sorted(num_count):
        count = num_count[num]
        if count > 0:
            # Try to form a group starting from current number
            for i in range(num, num + k):
                if num_count[i] < count:
                    return False
                num_count[i] -= count
    return True

# Example usage:
print(is_possible_divide([1,2,3,3,4,4,5,6], 4))  # Expected output: True
print(is_possible_divide([1,2,3,4], 3))          # Expected output: False
← Back to All Questions