Problem
Given an unsorted array of numbers, check if the array consists of consecutive numbers only.
Sample Input
[1, 2, 3, 4]
Sample Output
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();
}
Output
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")
Output
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");
}
}
Output
YES
People are also reading:
Leave a Comment on this Post