Home » Technical Interview Questions » Array Interview Questions » Check if the Elements of an Array are Consecutive

Check if the Elements of an Array are Consecutive


Reading Time - 4 mins

Given an array, Check if the elements of an array are consecutive. Here, consecutive elements mean, when we take all the elements in the array they need to form a consecutive sequence.

Example

Input

arr[]={65,68,66,64,67}

Output

array contains consecutive elements

here, all the elements in the array are consecutive as they are in increasing order ie, 64,65,66,67,68

Approach 1: Using Minimum and Maximum Element

Algorithm

1. First, find the minimum and maximum element in the array, Assign two variables min and max to the maximum and minimum integer values respectively.
Till less than the size of the array, pick each element in the array
a. If the element is greater than the max element, assign the max element to the picked element
b. If the element is less than the min element, assign min element to the picked element.
2. If the number of elements between max and min including themselves equals the size of the array then proceed.
Till less than the size of the array, pick each element in the array
a. If the element is repeated, then print that all elements are not consecutive and stop.
b. If the  Loop didn’t break, then print all are consecutive elements

READ  Subarray Sum Equals k

C++ Program for Check if the Elements of an Array are Consecutive

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int N;//size of the array
    cin>>N;
    int arr[N];
    for(int i=0;i<N;i++)
    {
        cin>>arr[i];
    }
    int min = INT_MAX , max = INT_MIN ;
  for(int i = 0 ; i < N; i++) //find minimum and maximum element
  {
    if(arr[i] > max)
      max = arr[i];
    if(arr[i] < min)
      min = arr[i];
  }
  if(max-min+1==N) // if the number of elements between max and min including themselves equals size of array then proceed
  {
    bool visited_nodes[N]={0};
    
    for(int i=0;i<N;i ++)
      {
        if(visited_nodes[arr[i] -  min] == 1) //it means the element is repeated so we cant get consecutive elements
          {
           cout << " Not all consecutive elements \n" ;
           return 0;  
          }  
        else
          visited_nodes[arr[i] - min] = 1;
      }
    cout << "Consecutive element set\n";
    return 0;
  }
  
  cout << " Not all consecutive elements \n" ;
  
  return 0;
}
5
3 5 2 4 6
Consecutive element set

Complexity Analysis for Check if the Elements of an Array are Consecutive

Time Complexity

O(n) where n is the number of elements present in the given array. Here we find the minimum and maximum element of the array in one traversal. And then check for contiguous sequence.

Space Complexity

O(1) because we don’t use any auxiliary space here. The above algorithm leads us to constant space complexity.

Approach 2: Using Sorting

Algorithm

1. Sort the elements in the array
2. Till the end of the sorted array, do linear scan
a. If the difference between the current element and the next element is anything other than     1, then print all elements are not consecutive
else,
b. If all differences are 1, then print all elements are consecutive.

READ  Median of Two Sorted Arrays

C++ Program for Check if the Elements of an Array are Consecutive

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int N;//size of the array
    cin>>N;
    int arr[N];
    for(int i=0;i<N;i++)
    {
        cin>>arr[i];
    }
    sort(arr,arr+N);
    for(int i=0 ; i < N - 1; i++)
    if(arr[i+1] > arr[i] + 1)
    {
        cout << "Not all consecutive elements\n";
        return 0;
    }
    cout<<"Consecutive element set\n";
    return 0;
}
5
3 5 2 4 7
Not all consecutive elements

Complexity Analysis for Check if the Elements of an Array are Consecutive

Time Complexity

O(nlogn) where n is the number of elements present in the given array. Here we use inbuild sort() function which has O(nlogn) time complexity.

Space Complexity

O(1) because we don’t use any auxiliary space here. The above algorithm leads us to constant space complexity.

References

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions