Problem

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

This problem is special case for Check if Array is Consecutive Integers.

Examples

Example 1:

1
2
3

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

Example 2:

1
2
3

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

Example 3:

1
2
3

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

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 nums)
  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

This case is special, that we have positive elements.

  1. Navigate the array.
  2. Update the array as for ith index :- nums[nums[i]] = nums[nums[i]]*-1 (if it already not negative).
  3. If is already negative, 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 if numbers are non negative
	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 + 1;
	}

	for (int i = 0; i < nums.length; i++) {
		int x = Math.abs(nums[i]);

		if (nums[x - 1] > 0) {
			nums[x - 1] = nums[x - 1] * -1;
		} else {
			return false;
		}
	}

	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[] nums) {
	// find the maximum in array
	int max = nums[0];

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

	return max;
}


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

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

	return min;
}

Complexity

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