Jobs

Interviews

Discussions

Divide Array in Sets of K Consecutive Numbers #13 Most Asked

Medium

Waymo

3 views

Topics:

ArraysGreedy Algorithms

Given an array of integers nums and a positive integer k, check whether it is possible to divide this array into sets of k consecutive numbers.

Return true if it is possible. Otherwise, return false.

Example 1:

Input: nums = [1,2,3,3,4,4,5,6], k = 4
Output: true
Explanation: Array can be divided into [1,2,3,4] and [3,4,5,6].

Example 2:

Input: nums = [3,2,1,2,3,4,3,4,5,9,10,11], k = 3
Output: true
Explanation: Array can be divided into [1,2,3] , [2,3,4] , [3,4,5] and [9,10,11].

Example 3:

Input: nums = [1,2,3,4], k = 3
Output: false
Explanation: Each array should be divided in subarrays of size 3.

Constraints:

1 <= k <= nums.length <= 10⁵
1 <= nums[i] <= 10⁹

Note: This question is the same as 846: https://leetcode.com/problems/hand-of-straights/

Try coding it in LeetCode

Divide Array in Sets of K Consecutive Numbers #13 Most Asked

Medium

Waymo

3 views

Topics:

ArraysGreedy Algorithms

Given an array of integers nums and a positive integer k, check whether it is possible to divide this array into sets of k consecutive numbers.

Return true if it is possible. Otherwise, return false.

Example 1:

Input: nums = [1,2,3,3,4,4,5,6], k = 4
Output: true
Explanation: Array can be divided into [1,2,3,4] and [3,4,5,6].

Example 2:

Input: nums = [3,2,1,2,3,4,3,4,5,9,10,11], k = 3
Output: true
Explanation: Array can be divided into [1,2,3] , [2,3,4] , [3,4,5] and [9,10,11].

Example 3:

Input: nums = [1,2,3,4], k = 3
Output: false
Explanation: Each array should be divided in subarrays of size 3.

Constraints:

1 <= k <= nums.length <= 10⁵
1 <= nums[i] <= 10⁹

Note: This question is the same as 846: https://leetcode.com/problems/hand-of-straights/

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the expected return value (e.g., boolean, null, exception) if the input array cannot be divided into sets of K consecutive numbers?
Can the input array contain negative numbers, zeros, or duplicates?
What are the possible ranges for the values in the array, and what is the maximum size of the array?
Is K guaranteed to be a positive integer, and is it always less than or equal to the length of the input array?
If there are multiple ways to divide the array into sets of K consecutive numbers, is any valid division acceptable, or is there a specific criteria for a 'correct' division?

Brute Force Solution

Approach

The brute force method to group numbers is to try every possible combination. We check each combination to see if it meets the requirements of the problem, namely creating sets of consecutive numbers of the specified size.

Here's how the algorithm would work step-by-step:

First, sort the numbers to make it easier to check for consecutive sequences.
Pick a starting number from the sorted list.
See if the next numbers after it are consecutive and that we have enough to form a full set of the required size.
If we can form a set, mark those numbers as used and continue trying to form other sets from the remaining numbers.
If we can't form a set, pick a different starting number and try again.
Repeat this process until either all numbers are grouped into valid sets, or we've exhausted all possibilities.
If at any point, we can't form any more sets with the remaining numbers, then it's not possible to divide the numbers according to the rules.

Code Implementation

def divide_array_in_sets_of_k_consecutive_numbers_brute_force(numbers, k_consecutive_length):
    numbers.sort()
    number_count = len(numbers)
    used = [False] * number_count

    def can_form_sets():
        nonlocal used
        
        for start_index in range(number_count):
            if not used[start_index]:
                # Find an unused number to start a potential set
                potential_set = [numbers[start_index]]
                used[start_index] = True
                
                for _ in range(k_consecutive_length - 1):
                    next_val = potential_set[-1] + 1
                    found = False
                    for next_index in range(number_count):
                        if not used[next_index] and numbers[next_index] == next_val:
                            potential_set.append(numbers[next_index])
                            used[next_index] = True
                            found = True
                            break
                            
                    if not found:
                        # Reset used flags since set couldn't be formed
                        for index, value in enumerate(numbers):
                            if value in potential_set:
                                used[index] = False
                        return False

        # All numbers were used to form valid sets
        return True

    if number_count % k_consecutive_length != 0:
        return False

    # Check if the array can be divided into sets of k consecutive numbers
    return can_form_sets()

Big(O) Analysis

Time Complexity

O(n!) – Sorting the array takes O(n log n) time. The brute force approach involves exploring combinations by picking a starting number and checking for consecutive numbers to form sets of size k. In the worst case, we might explore almost all permutations of the input array to find a valid grouping. The permutation generation and validation process leads to a time complexity approaching O(n!), since we may try nearly all possible arrangements to discover consecutive sets. Therefore the complexity is O(n!).

Space Complexity

O(N) – The algorithm sorts the input array of size N, which typically requires O(N) auxiliary space for sorting algorithms like merge sort used by many standard library sort functions. Additionally, the algorithm marks numbers as used which in the worst case could require an additional boolean array (or similar data structure) of size N to keep track of which numbers have been included in a set. Therefore the space complexity is dominated by the sorting and the marking of numbers, resulting in O(N) auxiliary space.

Optimal Solution

Approach

The core idea is to efficiently build groups of consecutive numbers. We'll use a clever counting trick to quickly determine if we can successfully form all the groups we need, without exhaustively checking every possible combination.

Here's how the algorithm would work step-by-step:

First, count how many times each number appears in the input.
Then, start with the smallest number that appears in the input. This number must be the start of a new group.
For this number, check if the next few consecutive numbers (based on the required group size) also exist. For example if we need groups of size 3, and the smallest number is 5, we need to see if 6 and 7 are also present.
If all the consecutive numbers exist, decrease their counts to reflect that they've been used in a group.
If any consecutive number is missing, or its count becomes zero, then it's impossible to form the groups, and you can stop and say no.
Repeat steps 2-5, always starting with the smallest remaining number, until all numbers have been used or you've determined it's impossible.

Code Implementation

def is_possible_divide_into_sets(numbers, group_size):
    number_counts = {}
    for number in numbers:
        number_counts[number] = number_counts.get(number, 0) + 1

    numbers_sorted = sorted(number_counts.keys())

    for number in numbers_sorted:
        if number_counts[number] > 0:
            # Start forming a group with the smallest number.

            start_count = number_counts[number]
            for i in range(group_size):
                next_number = number + i
                if next_number not in number_counts or number_counts[next_number] < start_count:
                    # If a consecutive number is missing or not enough.

                    return False
                number_counts[next_number] -= start_count

    return True

Big(O) Analysis

Time Complexity

O(n log n) – The initial step involves counting the frequency of each number using a data structure like a HashMap, which takes O(n) time. The dominant operation comes from repeatedly finding the smallest number and checking for the existence of k consecutive numbers. Finding the smallest number can be efficiently achieved using a sorted data structure like a TreeMap or a Heap, leading to a cost of O(log n) for each number. Since we iterate through each of the n numbers in the input array at most once and potentially remove the current smallest value we are processing, the overall complexity will be O(n log n).

Space Complexity

O(N) – The algorithm uses a data structure, specifically a frequency map or counter, to store the counts of each number in the input array. In the worst case, all the numbers in the input array are unique, leading to a frequency map with N entries, where N is the number of elements in the input array. Therefore, the auxiliary space required to store this frequency map grows linearly with the input size. Thus, the space complexity is O(N).

Edge Cases

Case	How to Handle
Empty input array	Return True if the array is empty, as it trivially satisfies the condition of being divisible into sets of size K.
Array size is not a multiple of K	Return False immediately since the array cannot be divided into sets of size K if its size is not divisible by K.
K is greater than the array size	Return False immediately since we cannot form sets of size K if K is greater than the array size.
Input array contains duplicate numbers	Use a frequency map (Counter) to correctly track the number of occurrences of each element and decrement appropriately as sets are formed.
Input array contains negative numbers	The solution should handle negative numbers correctly as the problem doesn't specify a non-negative constraint.
Input array contains numbers with large absolute values (potential integer overflow if summing)	The solution doesn't perform arithmetic sums so overflow is not a direct concern, but sort operation complexity could be impacted by large numbers.
No valid solution exists (e.g., cannot form consecutive sets)	The algorithm should correctly identify and return False when it's impossible to form consecutive sets of size K, such as when a required element is missing.
K = 1	Return True, because any array is divisible into sets of 1 consecutive number.

Empty input array

How to Handle:

Return True if the array is empty, as it trivially satisfies the condition of being divisible into sets of size K.

Array size is not a multiple of K

How to Handle:

Return False immediately since the array cannot be divided into sets of size K if its size is not divisible by K.

K is greater than the array size

How to Handle:

Return False immediately since we cannot form sets of size K if K is greater than the array size.

Input array contains duplicate numbers

How to Handle:

Use a frequency map (Counter) to correctly track the number of occurrences of each element and decrement appropriately as sets are formed.

Input array contains negative numbers

How to Handle:

The solution should handle negative numbers correctly as the problem doesn't specify a non-negative constraint.

Input array contains numbers with large absolute values (potential integer overflow if summing)

How to Handle:

The solution doesn't perform arithmetic sums so overflow is not a direct concern, but sort operation complexity could be impacted by large numbers.

No valid solution exists (e.g., cannot form consecutive sets)

How to Handle:

The algorithm should correctly identify and return False when it's impossible to form consecutive sets of size K, such as when a required element is missing.

K = 1

How to Handle:

Return True, because any array is divisible into sets of 1 consecutive number.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the expected return value (e.g., boolean, null, exception) if the input array cannot be divided into sets of K consecutive numbers?
Can the input array contain negative numbers, zeros, or duplicates?
What are the possible ranges for the values in the array, and what is the maximum size of the array?
Is K guaranteed to be a positive integer, and is it always less than or equal to the length of the input array?
If there are multiple ways to divide the array into sets of K consecutive numbers, is any valid division acceptable, or is there a specific criteria for a 'correct' division?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

First, sort the numbers to make it easier to check for consecutive sequences.
Pick a starting number from the sorted list.
See if the next numbers after it are consecutive and that we have enough to form a full set of the required size.
If we can form a set, mark those numbers as used and continue trying to form other sets from the remaining numbers.
If we can't form a set, pick a different starting number and try again.
Repeat this process until either all numbers are grouped into valid sets, or we've exhausted all possibilities.
If at any point, we can't form any more sets with the remaining numbers, then it's not possible to divide the numbers according to the rules.

Code Implementation

def divide_array_in_sets_of_k_consecutive_numbers_brute_force(numbers, k_consecutive_length):
    numbers.sort()
    number_count = len(numbers)
    used = [False] * number_count

    def can_form_sets():
        nonlocal used
        
        for start_index in range(number_count):
            if not used[start_index]:
                # Find an unused number to start a potential set
                potential_set = [numbers[start_index]]
                used[start_index] = True
                
                for _ in range(k_consecutive_length - 1):
                    next_val = potential_set[-1] + 1
                    found = False
                    for next_index in range(number_count):
                        if not used[next_index] and numbers[next_index] == next_val:
                            potential_set.append(numbers[next_index])
                            used[next_index] = True
                            found = True
                            break
                            
                    if not found:
                        # Reset used flags since set couldn't be formed
                        for index, value in enumerate(numbers):
                            if value in potential_set:
                                used[index] = False
                        return False

        # All numbers were used to form valid sets
        return True

    if number_count % k_consecutive_length != 0:
        return False

    # Check if the array can be divided into sets of k consecutive numbers
    return can_form_sets()

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

First, count how many times each number appears in the input.
Then, start with the smallest number that appears in the input. This number must be the start of a new group.
For this number, check if the next few consecutive numbers (based on the required group size) also exist. For example if we need groups of size 3, and the smallest number is 5, we need to see if 6 and 7 are also present.
If all the consecutive numbers exist, decrease their counts to reflect that they've been used in a group.
If any consecutive number is missing, or its count becomes zero, then it's impossible to form the groups, and you can stop and say no.
Repeat steps 2-5, always starting with the smallest remaining number, until all numbers have been used or you've determined it's impossible.

Code Implementation

def is_possible_divide_into_sets(numbers, group_size):
    number_counts = {}
    for number in numbers:
        number_counts[number] = number_counts.get(number, 0) + 1

    numbers_sorted = sorted(number_counts.keys())

    for number in numbers_sorted:
        if number_counts[number] > 0:
            # Start forming a group with the smallest number.

            start_count = number_counts[number]
            for i in range(group_size):
                next_number = number + i
                if next_number not in number_counts or number_counts[next_number] < start_count:
                    # If a consecutive number is missing or not enough.

                    return False
                number_counts[next_number] -= start_count

    return True

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty input array	Return True if the array is empty, as it trivially satisfies the condition of being divisible into sets of size K.
Array size is not a multiple of K	Return False immediately since the array cannot be divided into sets of size K if its size is not divisible by K.
K is greater than the array size	Return False immediately since we cannot form sets of size K if K is greater than the array size.
Input array contains duplicate numbers	Use a frequency map (Counter) to correctly track the number of occurrences of each element and decrement appropriately as sets are formed.
Input array contains negative numbers	The solution should handle negative numbers correctly as the problem doesn't specify a non-negative constraint.
Input array contains numbers with large absolute values (potential integer overflow if summing)	The solution doesn't perform arithmetic sums so overflow is not a direct concern, but sort operation complexity could be impacted by large numbers.
No valid solution exists (e.g., cannot form consecutive sets)	The algorithm should correctly identify and return False when it's impossible to form consecutive sets of size K, such as when a required element is missing.
K = 1	Return True, because any array is divisible into sets of 1 consecutive number.

Empty input array

How to Handle:

Return True if the array is empty, as it trivially satisfies the condition of being divisible into sets of size K.

Array size is not a multiple of K

How to Handle:

Return False immediately since the array cannot be divided into sets of size K if its size is not divisible by K.

K is greater than the array size

How to Handle:

Return False immediately since we cannot form sets of size K if K is greater than the array size.

Input array contains duplicate numbers

How to Handle:

Use a frequency map (Counter) to correctly track the number of occurrences of each element and decrement appropriately as sets are formed.

Input array contains negative numbers

How to Handle:

The solution should handle negative numbers correctly as the problem doesn't specify a non-negative constraint.

Input array contains numbers with large absolute values (potential integer overflow if summing)

How to Handle:

The solution doesn't perform arithmetic sums so overflow is not a direct concern, but sort operation complexity could be impacted by large numbers.

No valid solution exists (e.g., cannot form consecutive sets)

How to Handle:

The algorithm should correctly identify and return False when it's impossible to form consecutive sets of size K, such as when a required element is missing.

K = 1

How to Handle:

Return True, because any array is divisible into sets of 1 consecutive number.

0/0 Waymo questions completed

0/0 completed