Table of Contents
If you want to practice data structure and algorithm programs, you can go through 100+ data structure and algorithm programs.
In this post, we will see how to check if array elements are consecutive.
Problem
Given an array, we need to check if array contains consecutive elements.
For example:
Input: array[] = {5, 3, 4, 1, 2}
Output: true
As array contains consecutive elements from 1 to 5
Input: array[] = {47, 43, 45, 44, 46}
Output: true
As array contains consecutive elements from 43 to 47
Input: array[] = {6, 7, 5, 6}
Output: false
As array does not contain consecutive elements.
Output: true
As array contains consecutive elements from 1 to 5
Input: array[] = {47, 43, 45, 44, 46}
Output: true
As array contains consecutive elements from 43 to 47
Input: array[] = {6, 7, 5, 6}
Output: false
As array does not contain consecutive elements.
Solution
Simple solution will be to sort the array and check if elements are consecutive just by iterative over array but time complexity of this solution will be o(n^logn).
Can we do better?
Yes, we can do better
- Find minimum and maximum element in the array.
- Check if max-min+1==n, if elements are consecutive then this condition should meet.
- Create a visited boolean array.
- Iterate over the array and check
- visited[arr[i]-min] is true, then return false as elements are repeated.
- mark the element visited.
Program to check if Array Elements are Consecutive
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 |
package org.arpit.java2blog; public class ArrayConsecutiveElementMain{ /* Method return minimum value*/ private int getMinimum(int arr[], int n) { int min = arr[0]; for (int i = 1; i < n; i++) if (arr[i] < min) min = arr[i]; return min; } /* Method return maximum value*/ private int getMaximum(int arr[], int n) { int max = arr[0]; for (int i = 1; i < n; i++) if (arr[i] > max) max = arr[i]; return max; } /* This method checks if array elements are consecutive */ public boolean checkArrayContainsConsecutiveElements(int arr[], int n) { if ( n < 1 ) return false; int min = getMinimum(arr, n); int max = getMaximum(arr, n); if (max - min + 1 == n) { boolean[] visited=new boolean[arr.length]; for (int i = 0; i < n; i++) { if ( visited[arr[i] - min] != false ) return false; visited[arr[i] - min] = true; } return true; } return false; } public static void main(String args[]) { ArrayConsecutiveElementMain acem=new ArrayConsecutiveElementMain(); int arr[]= {47, 43, 45, 44, 46}; if(acem.checkArrayContainsConsecutiveElements(arr, arr.length)) System.out.println(" Array elements are consecutive "); else System.out.println(" Array elements are not consecutive "); return; } } |
Array elements are consecutive
Time complexity of this solution is o(n).
That’s all about how to check if Array Elements are Consecutive.
Was this post helpful?
Let us know if this post was helpful. Feedbacks are monitored on daily basis. Please do provide feedback as that\'s the only way to improve.
