2229. Check if an Array Is Consecutive
Problem Description
The given problem presents us with a challenge to determine whether an array of integers, named nums
, is consecutive or not. An array is considered consecutive if it includes all the numbers from x
to x + n - 1
without any gaps or repetitions, where x
is the smallest number in the array, and n
is the total count of numbers in the array. To reiterate, our task is to analyze the integer array and return true
if the array meets this consecutive criteria or false
otherwise.
Intuition
To intuitively solve this problem, we can break down the definition of a consecutive array into two main conditions:
- The array must not contain any duplicate values, which is essential for ensuring that the array includes a complete range of numbers without repetition.
- The difference between the maximum and minimum number in the array should be exactly
n - 1
, wheren
is the size of the array. This condition guarantees that the range spans enough numbers to fill the array without gaps.
So, the straightforward approach is to first identify the smallest and largest numbers in the array. Once these are identified, we can check whether all array elements are unique and whether the difference between the maximum and minimum values equals n - 1
. If both conditions are satisfied, we can confidently determine that the array is consecutive.
Here's a step by step reasoning of the implementation:
- Find the minimum value
mi
in the arraynums
using themin()
function. This representsx
. - Find the maximum value
mx
in the arraynums
using themax()
function. This representsx + n - 1
. - Calculate the array size
n
using thelen()
function. - Check if all elements in the array are unique by converting the array into a
set
and comparing its length ton
. - Finally, check if the maximum value equals the minimum value plus
n
minus 1, i.e.,mx == mi + n - 1
. - If both checks pass, return
true
. Otherwise, returnfalse
.
By checking each of these conditions with simple operations, we can solve the problem in an efficient and understandable manner.
Solution Approach
The solution is implemented using simple Python constructs and relies on the unique properties of sets in Python, and mathematical reasoning. Here's the breakdown of the steps involved in checking if the list of integers is consecutive:
-
Minimum and Maximum Values: We begin by using Python's built-in
min()
andmax()
functions to find the smallest numbermi
and the largest numbermx
in thenums
array. These functions iterate through the list and deliver the minimum and maximum values efficiently. -
Unique Elements Check: We then convert the list
nums
into a set. Sets in Python are unordered collections of unique elements. By comparing the length of this set with the length of the original list (usinglen(set(nums)) == n
), we determine if all elements in the array are unique. If there are any duplicates, the set's length will be smaller than that of the list because sets automatically remove duplicate items. -
Consecutive Numbers Check: Finally, we check if the numbers are consecutive by verifying that the maximum element
mx
equals the minimum elementmi
plusn - 1
. This check ensures that the numbers span a range which corresponds to the size of the list. If the length of the set is equal to the length of the list and the maximum value is as expected, the list is consecutive.
The solution code combines these three checks into one line:
return len(set(nums)) == n and mx == mi + n - 1
This line of code first asserts that each number in the array is unique (since the size of the set should be equal to the length of the array) and then ensures that the range (mx - mi
) is exactly one less than the length of the array (n - 1
). If both conditions are satisfied, this indicates that the array contains exactly n
consecutive numbers starting at the minimum value found, thus making it a consecutive array, and the function returns True
. Otherwise, the function returns False
.
In terms of efficiency, this is a very concise approach since it involves a single pass over the array to check for all the required conditions, making it an O(n) time complexity algorithm, with O(n) space complexity due to set creation where n
is the number of elements in the nums
array.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
To illustrate the solution approach, consider a small example where the nums
array is [4, 5, 6, 7]
.
-
Finding Minimum and Maximum Values: First, the smallest number
mi
is found usingmin(nums)
, which is4
in this case. The largest numbermx
is found usingmax(nums)
, which is7
in our example. -
Unique Elements Check: We convert the
nums
array into a set{4, 5, 6, 7}
. The original list's lengthn
is4
and the set's length is also4
. As the lengths are equal, we can conclude that all elements in the array are unique. -
Consecutive Numbers Check: We now verify if the numbers are consecutive. We do this by checking if
mx = mi + n - 1
. In our example,7 = 4 + 4 - 1
simplifies to7 = 7
, which is true.
The array [4, 5, 6, 7]
passed the unique elements check and the consecutive numbers check. Thus, by implementing the solution approach:
mi = min(nums)
mx = max(nums)
n = len(nums)
return len(set(nums)) == n and mx == mi + n - 1
The conditions are satisfied and the function would return True
, confirming that the array is consecutive.
Solution Implementation
1class Solution:
2 def isConsecutive(self, nums: List[int]) -> bool:
3 # Find the minimum and maximum value in the list
4 min_value = min(nums)
5 max_value = max(nums)
6 # Get the length of the list
7 num_length = len(nums)
8
9 # To be a consecutive sequence, two conditions must be met:
10 # 1. All numbers must be unique (no duplicates) which is checked by converting
11 # the list to a set and comparing its length with the original list length.
12 # 2. The difference between max and min value should be exactly one less than
13 # the length of the list (since a consecutive sequence increments by one
14 # for each element).
15 # Therefore, we return True if both conditions are met, False otherwise.
16 return len(set(nums)) == num_length and max_value == min_value + num_length - 1
17
1class Solution {
2 public boolean isConsecutive(int[] nums) {
3 int minVal = nums[0]; // Initialize minimum value with the first element.
4 int maxVal = nums[0]; // Initialize maximum value with the first element.
5 Set<Integer> seenNumbers = new HashSet<>(); // Create a set to store unique numbers.
6
7 for (int value : nums) {
8 minVal = Math.min(minVal, value); // Update the minimum value.
9 maxVal = Math.max(maxVal, value); // Update the maximum value.
10 seenNumbers.add(value); // Add the current value to the set.
11 }
12
13 int length = nums.length; // Store the length of the input array.
14
15 // Verify two conditions for the array to consist of consecutive elements:
16 // 1. The set size should be equal to the array length (no duplicates).
17 // 2. The maximum value should equal the minimum value plus the array length minus 1.
18 return seenNumbers.size() == length && maxVal == minVal + length - 1;
19 }
20}
21
1#include <vector>
2#include <unordered_set>
3#include <algorithm>
4
5class Solution {
6public:
7 bool isConsecutive(std::vector<int>& nums) {
8 // Create a set containing all elements from the vector.
9 // Sets automatically remove duplicates.
10 std::unordered_set<int> elementsSet(nums.begin(), nums.end());
11
12 // Find the smallest element in the vector.
13 int minElement = *std::min_element(nums.begin(), nums.end());
14
15 // Find the largest element in the vector.
16 int maxElement = *std::max_element(nums.begin(), nums.end());
17
18 // Get the count of unique numbers in the vector.
19 int numCount = nums.size();
20
21 // Check if there are no duplicates (set size == vector size)
22 // and if the range between min and max elements is exactly the size of the vector - 1.
23 // This ensures that the vector contains consecutive numbers.
24 return elementsSet.size() == numCount && maxElement == minElement + numCount - 1;
25 }
26};
27
1// Imports not required in TypeScript for array operations
2
3// Function to check if an array consists of consecutive integers.
4function isConsecutive(nums: number[]): boolean {
5 // Convert the array into a set to filter out duplicate elements.
6 const elementsSet: Set<number> = new Set(nums);
7
8 // Find the smallest element in the array.
9 const minElement: number = Math.min(...nums);
10
11 // Find the largest element in the array.
12 const maxElement: number = Math.max(...nums);
13
14 // Count the number of unique elements in the array.
15 const numCount: number = nums.length;
16
17 // Check if there are no duplicates (set size equals array size) and
18 // if the range between the smallest and largest elements equals to the array length - 1.
19 // This condition confirms the array contains consecutive numbers.
20 return elementsSet.size === numCount && maxElement === minElement + numCount - 1;
21}
22
23// Example usage:
24// const result = isConsecutive([1, 2, 3, 4, 5]);
25// console.log(result); // Output should be true if the input array is consecutive.
26
Time and Space Complexity
The time complexity of the code is O(n)
where n
is the length of the nums
list. This is because the min()
and max()
functions will each take O(n)
to find the minimum and maximum elements in the list, and len()
takes O(1)
time. Furthermore, converting the list to a set also takes O(n)
time in average case to eliminate duplicates and check if all the elements are unique.
The space complexity of the code is O(n)
since we are creating a new set from the list of numbers, which in the worst case will contain a unique value for every element in the list if there are no duplicates.
Learn more about how to find time and space complexity quickly using problem constraints.
Which algorithm is best for finding the shortest distance between two points in an unweighted graph?
Recommended Readings
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Want a Structured Path to Master System Design Too? Don’t Miss This!