Code Implementation

class Solution:
    def isConsecutive(self, nums):
        if not nums:
            return False
        n = len(nums)
        min_num = min(nums)
        max_num = max(nums)
        if max_num - min_num + 1 != n:
            return False
        seen = set()
        for num in nums:
            if num in seen:
                return False
            seen.add(num)
        return True
      

class Solution {
public:
    bool isConsecutive(vector<int>& nums) {
        if (nums.empty()) return false;
        int n = nums.size();
        int min_num = *min_element(nums.begin(), nums.end());
        int max_num = *max_element(nums.begin(), nums.end());
        if (max_num - min_num + 1 != n) return false;
        unordered_set<int> seen;
        for (int num : nums) {
            if (seen.count(num)) return false;
            seen.insert(num);
        }
        return true;
    }
};
      

class Solution {
    public boolean isConsecutive(int[] nums) {
        if (nums == null || nums.length == 0) return false;
        int n = nums.length;
        int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
        for (int num : nums) {
            if (num < min) min = num;
            if (num > max) max = num;
        }
        if (max - min + 1 != n) return false;
        Set<Integer> seen = new HashSet<>();
        for (int num : nums) {
            if (seen.contains(num)) return false;
            seen.add(num);
        }
        return true;
    }
}
      

var isConsecutive = function(nums) {
    if (!nums || nums.length === 0) return false;
    let minNum = Math.min(...nums);
    let maxNum = Math.max(...nums);
    if (maxNum - minNum + 1 !== nums.length) return false;
    let seen = new Set();
    for (let num of nums) {
        if (seen.has(num)) return false;
        seen.add(num);
    }
    return true;
};
      

Problem Description

Given an integer array nums, determine if it contains a set of consecutive numbers (with no duplicates and no gaps), regardless of their order in the array. In other words, after sorting, the numbers should form a sequence where each number is exactly one greater than the previous. The array must not contain any repeated elements.

• The array can be in any order.
• Each element in nums must be unique.
• If the array is empty, return False.
• Return True if the array is consecutive, False otherwise.

Thought Process

The most direct way to check if an array is consecutive is to sort it and then check if every element differs from the previous by exactly one. However, sorting takes O(n log n) time, and we can do better.

Let's think about the properties of consecutive numbers:

• The difference between the maximum and minimum should be exactly the length of the array minus one: max - min + 1 == n.
• All elements should be unique (no duplicates).

Instead of sorting, we can find the minimum and maximum, check the range, and use a set to check for duplicates. This approach leverages hash sets for O(1) lookups.

Solution Approach

• Step 1: Check if the array is empty. If so, return False.
• Step 2: Find the minimum and maximum values in the array.
• Step 3: Verify that the difference between the maximum and minimum plus one equals the length of the array. This ensures there are no gaps.
• Step 4: Use a hash set to check for duplicate elements as you iterate through the array. If a duplicate is found, return False.
• Step 5: If all checks pass, return True.

We use a hash set because it allows us to check for duplicates in constant time, and the min/max checks ensure the range is exactly right for consecutiveness.

Example Walkthrough

Let's use the input nums = [4, 2, 3, 5, 6].

• Step 1: The array is not empty.
• Step 2: min = 2, max = 6.
• Step 3: max - min + 1 = 6 - 2 + 1 = 5, which equals the length of the array (5).
• Step 4: Add each element to a set:
  • Add 4: set = {4}
  • Add 2: set = {2, 4}
  • Add 3: set = {2, 3, 4}
  • Add 5: set = {2, 3, 4, 5}
  • Add 6: set = {2, 3, 4, 5, 6}
  No duplicates found.
• Step 5: All checks pass, so return True.

If the input had been [1, 2, 4, 5], then max - min + 1 = 5 - 1 + 1 = 5 but the length is 4, so we'd return False due to the gap.

Time and Space Complexity

• Brute-force approach: Sort the array (O(n log n)), then check consecutive differences (O(n)). Total: O(n log n) time, O(1) extra space if sorting in-place.
• Optimized approach: One pass to find min and max (O(n)), one pass to check for duplicates with a set (O(n)). Total: O(n) time, O(n) space for the set.

The optimized approach is faster for large arrays and avoids the overhead of sorting.

Summary

To check if an array is consecutive, we:

• Ensure the range matches the array length.
• Ensure all elements are unique.