What is the time complexity of LeetCode 1296. Divide Array in Sets of K Consecutive Numbers?

The Python solution on this page runs in O(n \times \log n).

What is the space complexity of LeetCode 1296. Divide Array in Sets of K Consecutive Numbers?

The Python solution on this page uses O(n) auxiliary space.

Divide Array in Sets of K Consecutive Numbers — LeetCode 1296 Python Solution

MediumGreedyArrayHash TableSorting

Problem: #1296
Pattern: Greedy
Reading time: 2 min
Source: leetcode.com

The problem

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.

Example

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].

Python solution

Python

class Solution:
    def isPossibleDivide(self, nums: List[int], k: int) -> bool:
        if len(nums) % k:
            return False
        cnt = Counter(nums)
        for x in sorted(nums):
            if cnt[x]:
                for y in range(x, x + k):
                    if cnt[y] == 0:
                        return False
                    cnt[y] -= 1
        return True

Complexity

Measure	Complexity
Time	O(n \times \log n)
Space	O(n) auxiliary

Pattern: Greedy

Take the locally best option every time — when you can prove that never costs you later. LeetCode 1296. Divide Array in Sets of K Consecutive Numbers is filed here because LeetCode tags it Greedy, which is the vocabulary this hub collects.

The greedy guide has the Python template for the pattern and the 346 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 1296. Divide Array in Sets of K Consecutive Numbers?: LeetCode 1296. Divide Array in Sets of K Consecutive Numbers is rated Medium on LeetCode.
What is the time complexity of LeetCode 1296. Divide Array in Sets of K Consecutive Numbers?: The Python solution on this page runs in O(n \times \log n).
What is the space complexity of LeetCode 1296. Divide Array in Sets of K Consecutive Numbers?: The Python solution on this page uses O(n) auxiliary space.
What topics does LeetCode 1296. Divide Array in Sets of K Consecutive Numbers cover?: LeetCode 1296. Divide Array in Sets of K Consecutive Numbers is tagged Greedy, Array, Hash Table and Sorting on LeetCode.