Check if an Array Is Consecutive solution and explanation
The problem
Given an integer array nums, return true if nums is consecutive, otherwise return false.
An array is consecutive if it contains every number in the range [x, x + n - 1] (inclusive), where x is the minimum number in the array and n is the length of the array.
Example 1:
Input: nums = [1,3,4,2] Output: true Explanation: The minimum value is 1 and the length of nums is 4. All of the values in the range [x, x + n - 1] = [1, 1 + 4 - 1] = [1, 4] = (1, 2, 3, 4) occur in nums. Therefore, nums is consecutive.
Example 2:
Input: nums = [1,3] Output: false Explanation: The minimum value is 1 and the length of nums is 2. The value 2 in the range [x, x + n - 1] = [1, 1 + 2 - 1], = [1, 2] = (1, 2) does not occur in nums. Therefore, nums is not consecutive.
Example 3:
Input: nums = [3,5,4] Output: true Explanation: The minimum value is 3 and the length of nums is 3. All of the values in the range [x, x + n - 1] = [3, 3 + 3 - 1] = [3, 5] = (3, 4, 5) occur in nums. Therefore, nums is consecutive.
Constraints:
1 <= nums.length <= 1050 <= nums[i] <= 105
Approach overview
Problem Overview: You get an integer array nums. The task is to check whether its elements can form a sequence of consecutive integers with no gaps and no duplicates. Order does not matter, but every value between the minimum and maximum must appear exactly once.
Approach 1: Brute Force Range Check (O(n²) time, O(1) space)
Start by finding the minimum value in the array. If the numbers are consecutive, the expected values should be min, min+1, min+2 ... min+n-1. For each expected value, scan the entire array to see if it exists. If any value is missing, the array cannot be consecutive. This approach repeatedly iterates through the array for each required number, which leads to O(n²) time complexity. It demonstrates the core idea but is inefficient for larger inputs.
Approach 2: Sorting (O(n log n) time, O(1) or O(log n) space)
Sort the array first. Once sorted, consecutive numbers must differ by exactly 1 between adjacent elements. Iterate through the sorted array and check if nums[i] - nums[i-1] == 1. If the difference is larger, there is a gap; if it is zero, a duplicate exists. Sorting simplifies the validation logic but adds an O(n log n) cost. This approach is straightforward and often used when sorting is already part of the workflow. It relies on the properties of ordered data from Sorting algorithms.
Approach 3: Hash Table with Min/Max Check (O(n) time, O(n) space)
The optimal solution uses a hash set to track elements while scanning the array once. First compute the minimum and maximum values. For a valid consecutive sequence, the condition max - min + 1 == n must hold. Next insert every element into a set while checking for duplicates. If a duplicate appears or the range condition fails, the array cannot be consecutive. The set enables constant-time lookups, keeping the overall complexity at O(n). This pattern—tracking unique elements with constant lookup—is common in problems involving Hash Table usage on Array data.
Recommended for interviews: The hash table approach is the expected answer. Interviewers want to see that you recognize two key properties: the range size (max - min + 1) must equal the array length, and every value must be unique. A brute force explanation shows understanding of the problem constraints, while the O(n) hash-based solution demonstrates strong algorithmic thinking.
Solution
We can use a hash table s to store all the elements in the array nums, and use two variables mi and mx to represent the minimum and maximum values in the array, respectively.
If all elements in the array are distinct and the length of the array equals the difference between the maximum and minimum values plus 1, then the array is consecutive, and we return true; otherwise, we return false.
The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the array nums.
class Solution:
def isConsecutive(self, nums: List[int]) -> bool:
mi, mx = min(nums), max(nums)
return len(set(nums)) == mx - mi + 1 == len(nums)class Solution {
public boolean isConsecutive(int[] nums) {
int mi = nums[0], mx = 0;
Set<Integer> s = new HashSet<>();
for (int x : nums) {
if (!s.add(x)) {
return false;
}
mi = Math.min(mi, x);
mx = Math.max(mx, x);
}
return mx - mi + 1 == nums.length;
}
}class Solution {
public:
bool isConsecutive(vector<int>& nums) {
unordered_set<int> s;
int mi = nums[0], mx = 0;
for (int x : nums) {
if (s.contains(x)) {
return false;
}
s.insert(x);
mi = min(mi, x);
mx = max(mx, x);
}
return mx - mi + 1 == nums.size();
}
};/**
* @param {number[]} nums
* @return {boolean}
*/
var isConsecutive = function (nums) {
let [mi, mx] = [nums[0], 0];
const s = new Set();
for (const x of nums) {
if (s.has(x)) {
return false;
}
s.add(x);
mi = Math.min(mi, x);
mx = Math.max(mx, x);
}
return mx - mi + 1 === nums.length;
};function isConsecutive(nums: number[]): boolean {
let [mi, mx] = [nums[0], 0];
const s = new Set<number>();
for (const x of nums) {
if (s.has(x)) {
return false;
}
s.add(x);
mi = Math.min(mi, x);
mx = Math.max(mx, x);
}
return mx - mi + 1 === nums.length;
}func isConsecutive(nums []int) bool {
s := map[int]bool{}
mi, mx := nums[0], 0
for _, x := range nums {
if s[x] {
return false
}
s[x] = true
mi = min(mi, x)
mx = max(mx, x)
}
return mx-mi+1 == len(nums)
}Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Range Check | O(n²) | O(1) | Educational baseline to understand the consecutive range requirement |
| Sorting | O(n log n) | O(1) or O(log n) | Useful when the array is already being sorted or simplicity is preferred |
| Hash Table with Min/Max | O(n) | O(n) | Best general solution with linear time and fast duplicate detection |
Frequently asked questions
Is Check if an Array Is Consecutive easy or hard?
Check if an Array Is Consecutive is generally categorized as an easy problem. The main challenge is recognizing the mathematical property that max - min + 1 must equal the array length and combining it with duplicate detection.
Check if an Array Is Consecutive Python/Java solution
In Python, a set is used to store numbers while checking duplicates and validating the range condition. Java solutions typically use HashSet for the same purpose. Both implementations achieve O(n) time complexity and O(n) extra space.
How to solve Check if an Array Is Consecutive in O(n)?
Compute the minimum and maximum values in the array and check if max - min + 1 equals n. Then insert every element into a hash set. If a duplicate appears or the range condition fails, return false; otherwise the array forms a consecutive sequence.
What is the best approach for Check if an Array Is Consecutive?
The most efficient approach uses a hash set along with minimum and maximum values. First compute min and max, then verify that max - min + 1 equals the array length. Insert elements into a set to detect duplicates. This guarantees O(n) time complexity and O(n) space.
Is Check if an Array Is Consecutive asked at Google/Amazon/Meta?
Problems involving consecutive sequences and hash set validation frequently appear in interviews at large tech companies such as Amazon, Google, and Meta. Variants often test understanding of range checks, duplicate detection, and hash-based lookups.
What data structure is used in Check if an Array Is Consecutive?
The optimal approach uses a hash set to store elements and check duplicates in constant time. This data structure allows fast membership checks while scanning the array once.
What is the time complexity of Check if an Array Is Consecutive?
The optimal solution runs in O(n) time using a hash table to track elements and detect duplicates. Sorting-based solutions take O(n log n), while brute force approaches can degrade to O(n²) due to repeated scans.