Be the first user to complete this post
|
Add to List |
Check if Array is Consecutive Integers
Objective: Given a array of unsorted numbers, check if all the numbers in the array are consecutive numbers.
Examples:
int [] arrA = {21,24,22,26,23,25}; - True (All the integers are consecutive from 21 to 26) int [] arrB = {11,10,12,14,13}; - True (All the integers are consecutive from 10 to 14) int [] arrC = {11,10,14,13}; - False (Integers are not consecutive, 12 is missing)
Approach:
Naive Approach: Sorting . Time Complexity - O(nlogn).
Better Approach: Time Complexity - O(n).
- Find the Maximum and minimum elements in array (Say the array is arrA)
- Check if array length = max-min+1
- Subtract the min from every element of the array.
- Check if array doesn't have duplicates
for Step 4
a) If array contains negative elements
- Create an aux array and put 0 at every position
- Navigate the main array and update the aux array as aux[arrA[i]]=1
- During step 2 if u find any index position already filled with 1, we have duplicates, return false
- This operation performs in O(n) time and O(n) space
b) If array does not contains negative elements - Time Complexity : O(n), Space Complexity : O(1)
- Navigate the array.
- Update the array as for ith index :- arrA[arrA[i]] = arrA[arrA[i]]*-1 (if it already not negative).
- If is already negative, we have duplicates, return false.
Code:
Output:
true true false
Also Read: