Be the first user to complete this post
|
Add to List |
91. Check if Array is Consecutive Integers
Objective: Given an array of unsorted numbers, check if all the numbers are consecutive.
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 an array (Say the array is arrA)
- Check if array length = max-min+1
- Subtract the min from every element of the array.
- Check if the array doesn't have duplicates
for Step 4
a) If the 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 the array does not contain 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 is already not negative).
- If is already negative, we have duplicates, return false.
Output:
true true false