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