LeetCode 2229 - Check if an Array Is Consecutive

Difficulty: 🟢 Easy
Topics: Array, Hash Table, Sorting

Solution

Problem Understanding

The problem asks us to determine whether an integer array forms a perfect sequence of consecutive numbers without gaps or duplicates.

More formally, if the array has length n and its minimum value is x, then the array is considered consecutive if it contains every integer in the range:

$$[x, x + n - 1]$$

exactly once.

For example, if the smallest value is 3 and the array length is 4, then the array must contain:

$$3, 4, 5, 6$$

in any order.

The input is an integer array nums, and the expected output is a boolean value:

Return true if the array contains all consecutive integers in the required range
Return false otherwise

The constraints tell us several important things:

The array length can be as large as 10^5
Each value can also be as large as 10^5

Since the input size is large, inefficient approaches such as repeatedly scanning the array for missing numbers can become too slow. We should aim for either:

O(n log n) using sorting
O(n) using hashing

There are several important edge cases to consider:

Duplicate values, such as [1,2,2,3]
Missing values inside the expected range, such as [1,3]
Arrays of length 1, which are always consecutive
Unsorted arrays, since the numbers may appear in any order
Large ranges near the upper constraint limit

The problem guarantees that the array contains at least one element, so we do not need to handle empty arrays.

Approaches

Brute Force Approach

A straightforward solution is to first find the minimum value x, then check whether every value from x to x + n - 1 exists in the array.

One naive way to do this is:

Find the minimum value
For every number in the required range:

Scan the array to see whether the number exists

This works because the definition of consecutiveness directly requires every number in the range to appear.

However, this approach is inefficient. If the array has n elements, and for each required number we scan the array again, the total complexity becomes O(n^2).

With n = 10^5, quadratic time is too slow.

Optimal Approach

The key observation is that a consecutive array must satisfy two properties simultaneously:

All numbers must be unique
The difference between the maximum and minimum values must equal n - 1

Why does this work?

If there are n unique integers and the range size is exactly n, then every value inside the range must appear exactly once.

For example:

min = 3
max = 6
n = 4

The range size is:

$$6 - 3 + 1 = 4$$

If we also know there are exactly 4 unique values, then the array must contain all numbers from 3 through 6.

A hash set is ideal here because it allows:

Fast duplicate detection
Fast uniqueness counting

We can solve the problem in linear time.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(1)	Repeatedly scans the array for each required value
Optimal	O(n)	O(n)	Uses a hash set and range properties

Algorithm Walkthrough

Optimal Algorithm

Compute the minimum value in the array.

We need the minimum because the required consecutive range always starts from the smallest number. 2. Compute the maximum value in the array.

The maximum helps determine the total size of the numeric range. 3. Create a hash set from the array.

A set automatically removes duplicates. This allows us to check whether duplicate numbers exist. 4. Compare the size of the set with the array length.

If the set size is smaller than the array length, duplicates exist. A consecutive array cannot contain duplicates, so we immediately return false. 5. Check whether:

$$\text{maxValue} - \text{minValue} + 1 = n$$

This verifies that the numeric range has exactly the same size as the number of elements.

If both conditions are satisfied, return true.

Why it works

A consecutive sequence of length n must contain exactly n distinct integers spanning a range of size n.

If duplicates exist, then some required value is missing. Similarly, if the range size is larger than n, there must be a gap somewhere in the sequence.

Therefore, the combination of:

unique values
correct range size

guarantees that every required integer appears exactly once.

Python Solution

from typing import List

class Solution:
    def isConsecutive(self, nums: List[int]) -> bool:
        n = len(nums)

        unique_values = set(nums)

        if len(unique_values) != n:
            return False

        min_value = min(nums)
        max_value = max(nums)

        return max_value - min_value + 1 == n

The implementation begins by storing all elements in a set. Since sets only keep unique values, comparing the set size against the original array length immediately tells us whether duplicates exist.

Next, the algorithm computes the minimum and maximum values in the array. These values determine the expected consecutive range.

Finally, the expression:

max_value - min_value + 1 == n

checks whether the range size matches the number of elements.

If both the uniqueness condition and the range condition hold, the array must be consecutive.

Go Solution

func isConsecutive(nums []int) bool {
	n := len(nums)

	seen := make(map[int]bool)

	minValue := nums[0]
	maxValue := nums[0]

	for _, num := range nums {
		if seen[num] {
			return false
		}

		seen[num] = true

		if num < minValue {
			minValue = num
		}

		if num > maxValue {
			maxValue = num
		}
	}

	return maxValue-minValue+1 == n
}

The Go implementation combines multiple operations into a single loop:

Detect duplicates using a map
Track the minimum value
Track the maximum value

Go does not have a built in set type, so a map[int]bool is used instead.

The constraints are small enough that integer overflow is not a concern here.

Unlike Python, Go slices are references to arrays, but that detail does not affect this solution since the input is only read, never modified.

Worked Examples

Example 1

Input:

nums = [1,3,4,2]

Initial values:

Variable	Value
n	4
set(nums)	{1,2,3,4}

Set size equals array length, so there are no duplicates.

Compute range:

Variable	Value
min_value	1
max_value	4

Check:

$$4 - 1 + 1 = 4$$

This equals n, so the result is true.

Example 2

Input:

nums = [1,3]

Initial values:

Variable	Value
n	2
set(nums)	{1,3}

No duplicates exist.

Compute range:

Variable	Value
min_value	1
max_value	3

Check:

$$3 - 1 + 1 = 3$$

This does not equal n = 2.

The range is too large, meaning there is a missing value, specifically 2.

Return false.

Example 3

Input:

nums = [3,5,4]

Initial values:

Variable	Value
n	3
set(nums)	{3,4,5}

No duplicates exist.

Compute range:

Variable	Value
min_value	3
max_value	5

Check:

$$5 - 3 + 1 = 3$$

This equals n, so the array is consecutive.

Return true.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each element is processed a constant number of times
Space	O(n)	The hash set stores up to `n` unique elements

The algorithm performs linear work:

Building the set takes O(n)
Finding the minimum and maximum values takes O(n)

Since these operations are sequential rather than nested, the total complexity remains linear.

The additional memory comes from storing unique elements in the set.

Test Cases

from typing import List

class Solution:
    def isConsecutive(self, nums: List[int]) -> bool:
        n = len(nums)

        unique_values = set(nums)

        if len(unique_values) != n:
            return False

        min_value = min(nums)
        max_value = max(nums)

        return max_value - min_value + 1 == n

solution = Solution()

assert solution.isConsecutive([1, 3, 4, 2]) is True   # basic consecutive case
assert solution.isConsecutive([1, 3]) is False        # missing number
assert solution.isConsecutive([3, 5, 4]) is True      # unsorted consecutive numbers

assert solution.isConsecutive([5]) is True            # single element array
assert solution.isConsecutive([1, 2, 2, 3]) is False # duplicate value
assert solution.isConsecutive([0, 1, 2, 3, 4]) is True # starts from zero
assert solution.isConsecutive([10, 11, 12, 14]) is False # gap in sequence
assert solution.isConsecutive([100000]) is True       # upper bound single value
assert solution.isConsecutive([99997, 99998, 99999, 100000]) is True # large consecutive range
assert solution.isConsecutive([2, 1, 4, 3, 6]) is False # missing value in middle

Test	Why
`[1,3,4,2]`	Standard valid consecutive sequence
`[1,3]`	Detects missing values
`[3,5,4]`	Confirms ordering does not matter
`[5]`	Smallest possible input
`[1,2,2,3]`	Detects duplicates
`[0,1,2,3,4]`	Handles sequences starting at zero
`[10,11,12,14]`	Detects internal gaps
`[100000]`	Tests upper constraint boundary
`[99997,99998,99999,100000]`	Large valid consecutive range
`[2,1,4,3,6]`	Missing middle element despite near consecutiveness

Edge Cases

Duplicate Values

An array such as:

[1,2,2,3]

can easily fool an incorrect implementation that only checks the minimum and maximum range.

Here:

min = 1
max = 3
range size = 3

But the array length is 4, because one value is duplicated.

The implementation handles this correctly by comparing the set size against the array length. Since duplicates reduce the number of unique values, the algorithm immediately returns false.

Single Element Arrays

An array containing only one number is always consecutive because the required range contains exactly one value.

Example:

[7]

Here:

min = max = 7
range size = 1

The algorithm naturally handles this case without requiring any special logic.

Missing Internal Values

Arrays such as:

[2,3,5]

contain unique numbers, but there is a gap inside the expected range.

The implementation detects this through the range size check:

$$5 - 2 + 1 = 4$$

But the array length is only 3.

Since the range size is larger than the number of elements, at least one value must be missing. Therefore, the algorithm correctly returns false.