Teaching Kids Programming – Check if an Array Is Consecutive via Sorting Algorithm

Teaching Kids Programming: Videos on Data Structures and Algorithms

Given an integer array nums, return true if nums is consecutive, otherwise return false. An array is consecutive if it contains every number in the range [x, x + n – 1] (inclusive), where x is the minimum number in the array and n is the length of the array.

Example 1:
Input: nums = [1,3,4,2]
Output: true
Explanation:
The minimum value is 1 and the length of nums is 4.
All of the values in the range [x, x + n – 1] = [1, 1 + 4 – 1] = [1, 4] = (1, 2, 3, 4) occur in nums.
Therefore, nums is consecutive.

Example 2:
Input: nums = [1,3]
Output: false
Explanation:
The minimum value is 1 and the length of nums is 2.
The value 2 in the range [x, x + n – 1] = [1, 1 + 2 – 1], = [1, 2] = (1, 2) does not occur in nums.
Therefore, nums is not consecutive.

Example 3:
Input: nums = [3,5,4]
Output: true
Explanation:
The minimum value is 3 and the length of nums is 3.
All of the values in the range [x, x + n – 1] = [3, 3 + 3 – 1] = [3, 5] = (3, 4, 5) occur in nums.
Therefore, nums is consecutive.

Constraints:
1 <= nums.length <= 10^5
0 <= nums[i] <= 10^5

Hints:
Try sorting nums.
If nums is consecutive and sorted in ascending order, then nums[i] + 1 = nums[i + 1] for every i in the range 0 ≤ i < nums.length – 1.

Check if an Array Is Consecutive via Sorting Algorithm

If we sort the numbers, it will be easy to check if it is consecutive. Once we find an violation (consecutive numbers difference not one), we return false.

1
2
3
4
5
6
7

class Solution:
    def isConsecutive(self, nums: List[int]) -> bool:
        nums.sort()
        for i in range(1, len(nums)):
            if nums[i] != nums[i - 1] + 1:
                return False
        return True

class Solution:
    def isConsecutive(self, nums: List[int]) -> bool:
        nums.sort()
        for i in range(1, len(nums)):
            if nums[i] != nums[i - 1] + 1:
                return False
        return True

This is the same using the “all” keyword to test all consecutive numbers differ by one.

1
2
3
4

class Solution:
    def isConsecutive(self, nums: List[int]) -> bool:
        nums.sort()
        return all(nums[i] == nums[i - 1] + 1 for i in range(1, len(nums)))

class Solution:
    def isConsecutive(self, nums: List[int]) -> bool:
        nums.sort()
        return all(nums[i] == nums[i - 1] + 1 for i in range(1, len(nums)))

Time complexity is O(NLogN+N) which is O(NLogN), as the sorting is dominating the complexity.

–EOF (The Ultimate Computing & Technology Blog) —