count

Problem

Given a array of unsorted numbers, check if all the numbers in the array are consecutive numbers.

Examples

Example 1:

1
2
3
4
5

Input:
int [] nums = {21,24,22,26,23,25};
Output:
	True
Explanation: All the integers are consecutive from 21 to 26

Example 2:

1
2
3
4
5

Input: 
int [] nums = {11,10,12,14,13};
Output:
	True
Explanation: All the integers are consecutive from 10 to 14

Example 3:

1
2
3
4
5

Input: 
int [] nums = {11,10,14,13};
Output:
	False
Explanation: Integers are not consecutive, 12 is missing

What if all the elements are positive: Check if Array is Consecutive Positive Integers.

Solution

Method 1 - Sorting

Sort the array, and check if consecutive number differ by 1.

Complexity

  • Time Complexity – O(nlogn)
  • Space Complexity - O(1)

Method 2 - Subtract Min from array elements and check duplicates and bounds

Algorithm

  1. Find the Maximum and minimum elements in array (Say the array is arrA)
  2. Check if array length   = max-min+1
  3. Subtract the min from every element of the array.
  4. Check if array doesn’t have duplicates OR if index is out bound from (0 - max-min+1)

for Step 4 - checking the duplicates. Also, the solution assumes that numbers like in range [0, max-min+1). But if they are out of the range, then we again know, that elements can’t be consecutive. 

For Step 4 - checking the duplicates

As, the array contains negative elements, we may have to use aux array.

  • Create an aux array and put 0 at every position
  • Navigate the main array and update the aux array as aux[arrA[i]]=1
  • During step 2 if we find any index position already filled with 1, we have duplicates, return false

Code

 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

public boolean areConsecutive(int[] nums) {
	// this method with work even if numbers are negative
	int[] aux = new int[nums.length];
	int max = findMax(nums);
	int min = findMin(nums);

	if (nums.length != max - min + 1) {
		return false;
	}

	for (int i = 0; i < nums.length; i++) {
		nums[i] = nums[i] - min;
		aux[i] = 0;
	}

	for (int i = 0; i < nums.length; i++) {
		if (aux[nums[i]] == 0) {
			aux[nums[i]] = 1;
		} else {
			return false;
		}
	}
	//If we have reached till here means , we satisfied all the requirements
	return true;
}
 
 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

public int findMax(int[] arrA) {
	// find the maximum in array
	int max = arrA[0];

	for (int i = 1; i < arrA.length; i++) {
		if (max < arrA[i]) {
			max = arrA[i];
		}
	}

	return max;
}


public int findMin(int[] arrA) {
	// find the minimum in array
	int min = arrA[0];

	for (int i = 1; i < arrA.length; i++) {
		if (min > arrA[i]) {
			min = arrA[i];
		}
	}

	return min;
}

Complexity

  • Time Complexity – O(n)
  • Space Complexity - O(n)