Problem Description

You are given an integer array nums. Your task is to determine if the array contains consecutive integers.

An array is considered consecutive if it contains every integer in a continuous range from the minimum value to the maximum value, with no gaps or duplicates. Specifically, if x is the minimum value in the array and the array has length n, then the array must contain exactly the integers [x, x+1, x+2, ..., x+n-1].

For example:

• The array [4, 5, 6, 7] is consecutive because it contains all integers from 4 to 7
• The array [1, 3, 4, 5] is not consecutive because it's missing the number 2
• The array [1, 2, 2, 3] is not consecutive because it contains a duplicate (2 appears twice)

Return true if the array is consecutive, otherwise return false.

The solution checks three conditions that must all be true for an array to be consecutive:

1. All elements must be unique (no duplicates)
2. The number of unique elements must equal the array length
3. The difference between the maximum and minimum values plus 1 must equal the array length

This works because in a consecutive sequence of n numbers starting from min, the maximum value would be min + n - 1, so max - min + 1 = n.

Intuition

To determine if an array contains consecutive integers, we need to think about what properties a consecutive sequence must have.

First, let's consider what happens when we have n consecutive integers starting from some value x. The sequence would be [x, x+1, x+2, ..., x+n-1]. The smallest value is x and the largest value is x+n-1. This means the difference between the maximum and minimum values is exactly n-1, or equivalently, max - min + 1 = n.

However, just checking if max - min + 1 = n isn't enough. Consider the array [1, 2, 4, 5] - here max = 5, min = 1, and n = 4. We get 5 - 1 + 1 = 5, which doesn't equal 4, so this correctly identifies it as non-consecutive. But what about [1, 2, 2, 3]? Here max = 3, min = 1, n = 4, and 3 - 1 + 1 = 3, which also doesn't equal 4. But the reason is different - we have duplicates!

This leads us to realize that for an array to be consecutive, it must also contain no duplicate values. If we have duplicates, we can't possibly have all the integers in the range because we'd be "wasting" array positions on repeated values.

Therefore, we arrive at the key insight: an array is consecutive if and only if:

1. It has no duplicates (checked by comparing len(set(nums)) with len(nums))
2. The range it spans (max - min + 1) exactly matches the number of elements

We can elegantly combine these checks into a single expression: len(set(nums)) == max - min + 1 == len(nums). This verifies that the number of unique elements equals both the expected range size and the actual array length.

Learn more about Sorting patterns.

Solution Approach

The solution uses a hash table (set) to efficiently check for duplicates and implements a mathematical relationship to verify consecutiveness.

Implementation Steps:

1. Find the minimum and maximum values: We use Python's built-in min() and max() functions to find the smallest and largest elements in the array. These operations scan through the array once each.

   mi, mx = min(nums), max(nums)

2. Create a set from the array: Converting the list to a set automatically removes any duplicate values. This gives us a collection containing only unique elements from the original array.

   set(nums)

3. Perform the three-way equality check: We verify that all three conditions are equal:

   len(set(nums)) == mx - mi + 1 == len(nums)

   This checks:

   • len(set(nums)): The number of unique elements in the array
   • mx - mi + 1: The expected count of integers in the range [mi, mx] inclusive
   • len(nums): The total number of elements in the original array

Why this works:

If the array contains consecutive integers from mi to mx, there should be exactly mx - mi + 1 distinct integers. For example, the range [3, 4, 5, 6] has 6 - 3 + 1 = 4 integers.

The three-way equality ensures:

• No duplicates exist (unique count equals total count)
• No gaps exist in the sequence (unique count equals the range size)
• All conditions are satisfied simultaneously

Time and Space Complexity:

• Time: O(n) where n is the length of the array (for creating the set and finding min/max)
• Space: O(n) for storing the set

Example Walkthrough

Let's walk through the solution with a few examples to understand how it works.

Example 1: Consecutive array [4, 2, 3, 5]

1. First, find the minimum and maximum values:

   • min = 2, max = 5

2. Create a set from the array:

   • set([4, 2, 3, 5]) = {2, 3, 4, 5}
   • Number of unique elements: 4

3. Check the three-way equality:

   • len(set(nums)) = 4 (unique elements)
   • max - min + 1 = 5 - 2 + 1 = 4 (expected range size)
   • len(nums) = 4 (original array length)

   Since 4 == 4 == 4, the result is true. The array contains consecutive integers from 2 to 5.

Example 2: Non-consecutive array with gap [1, 3, 4, 5]

1. Find min and max:

   • min = 1, max = 5

2. Create set:

   • set([1, 3, 4, 5]) = {1, 3, 4, 5}
   • Number of unique elements: 4

3. Check equality:

   • len(set(nums)) = 4
   • max - min + 1 = 5 - 1 + 1 = 5
   • len(nums) = 4

   Since 4 ≠ 5, the result is false. The array is missing the number 2.

Example 3: Non-consecutive array with duplicate [1, 2, 2, 3]

1. Find min and max:

   • min = 1, max = 3

2. Create set:

   • set([1, 2, 2, 3]) = {1, 2, 3}
   • Number of unique elements: 3

3. Check equality:

   • len(set(nums)) = 3
   • max - min + 1 = 3 - 1 + 1 = 3
   • len(nums) = 4

   Since 3 ≠ 4, the result is false. The duplicate 2 prevents consecutiveness.

The beauty of this approach is that it catches both types of violations (gaps and duplicates) with a single elegant check.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n)

The time complexity is determined by the following operations:

• min(nums): O(n) - iterates through all elements to find minimum
• max(nums): O(n) - iterates through all elements to find maximum
• set(nums): O(n) - creates a set from n elements
• len(set(nums)): O(1) - getting length of set
• len(nums): O(1) - getting length of list
• Comparisons: O(1) - comparing three values

Since these operations are performed sequentially (not nested), the overall time complexity is O(n) + O(n) + O(n) + O(1) = O(n), where n is the length of the array nums.

Space Complexity: O(n)

The space complexity comes from creating a set from the input array. The set(nums) operation creates a new data structure that, in the worst case where all elements are unique, stores n elements. The variables mi and mx only use O(1) additional space. Therefore, the total space complexity is O(n), where n is the length of the array nums.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Empty Array Handling

The current solution will crash when given an empty array because min() and max() cannot operate on empty sequences.

Problem Example:

nums = []
min(nums)  # Raises ValueError: min() arg is an empty sequence

Solution: Add an edge case check at the beginning:

def isConsecutive(self, nums: List[int]) -> bool:
    if not nums:
        return False  # or True, depending on problem requirements
  
    min_val, max_val = min(nums), max(nums)
    return len(set(nums)) == max_val - min_val + 1 == len(nums)

2. Single Element Array Ambiguity

A single-element array like [5] technically contains consecutive integers (just one), but the problem statement might not clearly define this case.

Problem Example:

nums = [5]
# Current solution returns True, but is this the intended behavior?

Solution: Clarify requirements and potentially add explicit handling:

def isConsecutive(self, nums: List[int]) -> bool:
    if len(nums) <= 1:
        return True  # Single element or empty is trivially consecutive
  
    min_val, max_val = min(nums), max(nums)
    return len(set(nums)) == max_val - min_val + 1 == len(nums)

3. Integer Overflow in Other Languages

While Python handles large integers gracefully, implementing this solution in languages like Java or C++ could face integer overflow when calculating max_val - min_val + 1.

Problem Example:

nums = [-2147483648, 2147483647]  # Min and max 32-bit integers
# max_val - min_val + 1 would overflow in 32-bit arithmetic

Solution: Use appropriate data types or rearrange the calculation:

def isConsecutive(self, nums: List[int]) -> bool:
    if not nums:
        return False
  
    min_val, max_val = min(nums), max(nums)
    # Rearrange to avoid overflow: check if max - min == len - 1
    return len(set(nums)) == len(nums) and max_val - min_val == len(nums) - 1

4. Misunderstanding the Three-Way Equality

Developers might incorrectly assume that checking only two conditions is sufficient, missing edge cases.

Problem Example:

# Checking only uniqueness and range might miss cases
nums = [1, 2, 4, 5]  # Has 4 unique elements, max-min+1 = 5
# Without checking len(nums), we might incorrectly validate this

Solution: Always maintain the complete three-way check or explicitly separate the conditions for clarity:

def isConsecutive(self, nums: List[int]) -> bool:
    if not nums:
        return False
  
    unique_nums = set(nums)
    min_val, max_val = min(nums), max(nums)
  
    # Explicitly check all three conditions
    has_no_duplicates = len(unique_nums) == len(nums)
    covers_full_range = max_val - min_val + 1 == len(nums)
  
    return has_no_duplicates and covers_full_range