Check if an array is formed by consecutive integers

Posted in

Check if an array is formed by consecutive integers
maazbinasad

Maaz Bin Asad
Last updated on March 29, 2024

    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

    0 Comments