# Check if an array is formed by consecutive integers

Posted in

Last updated on July 11, 2022

## Problem

Given an unsorted array of numbers, check if the array consists of consecutive numbers only.

[1, 2, 3, 4]

YES

### Approach 1

You can sort the array and check if all adjacent elements have absolute difference as 1. If any pair with a difference other than 1 is found, return False. This approach takes O(NlogN) time (because of sorting).

### Approach 2

We only need to check two conditions. Condition 1 : maximum element -  minimum element + 1 = size of array Condition 2 : There should be no duplicate elements in the array This approach takes O(N) time and O(N) auxiliary space for creating extra data structures for checking duplicates. Let’s implement this approach

#### C++ Programming

#include<bits/stdc++.h>
using namespace std;
class Solution{
int arr[5] = {1, 3, 4, 2};
int n = sizeof(arr)/sizeof(arr[0]);
unordered_map<int,int>vis;        // map to check if number is visited;
int diff;
bool dup = false;
public:
void solve(){
// find difference b/w max and min element
diff = *max_element(arr, arr+n)-*min_element(arr, arr+n)+1;
for(int i=0;i<n;i++){
if(vis[arr[i]]==-1){      // if duplicate found
dup =  true;
break;
}
vis[arr[i]]=-1;
}
if(!dup && diff==n) cout<<"YES";    //if both conditions satisfy
else cout<<"NO";
}
};
int main(){
Solution sol;
sol.solve();
}

YES

#### Python Programming

def solve(arr, n):
if ( n < 1 ):
return False
Min = min(arr)
Max = max(arr)
if (Max - Min + 1 == n):
vis = [False for i in range(n)]
for i in range(n):
if (vis[arr[i] - Min] != False):
return False
vis[arr[i] - Min] = True
return True
arr = [1, 3, 4, 2]
n = len(arr)
if(solve(arr, n) == True):
print("YES")
else:
print("NO")

YES

#### Java Programming

class Solution
{
boolean solve(int arr[], int n)
{
if (n < 1)
return false;

int min = getMin(arr, n);

int max = getMax(arr, n);

if (max - min + 1 == n)
{

boolean vis[] = new boolean[n];
int i;
for (i = 0; i < n; i++)
{
if (vis[arr[i] - min] != false)
return false;

vis[arr[i] - min] = true;
}

return true;
}
return false;
}

int getMin(int arr[], int n)
{

int min = arr[0];
for (int i = 1; i < n; i++)
{
if (arr[i] < min)
min = arr[i];
}
return min;
}

int getMax(int arr[], int n)
{
int max = arr[0];
for (int i = 1; i < n; i++) { if (arr[i] > max)
max = arr[i];
}
return max;
}

public static void main(String[] args)
{
Solution consecutive = new Solution();
int arr[] = {1, 3, 4, 2};
int n = arr.length;
if (consecutive.solve(arr, n) == true)
System.out.println("YES");
else
System.out.println("NO");
}
}

YES