Effective Techniques to Check Array Consecutiveness in O(n) Time and O(1) Space with Python

Rate this post

πŸ’‘ Problem Formulation: The task is to determine whether the elements of an array are consecutive, ensuring that the solution adheres to time complexity O(n) and space complexity O(1), regardless of the elements being positive or negative. For example, given the array [4, 2, 5, 3, 1], the desired output is True since the numbers are consecutive.

Method 1: Check with Range

An intuitive approach involves checking if the array extends from the minimum to the maximum value without gaps. By determining the array’s range and checking it against the number of elements, we can assess consecutiveness. This method only uses constant additional space and operates in linear time.

Here’s an example:

def are_consecutive(arr):
    if len(arr) == 0: return False
    min_val, max_val = min(arr), max(arr)
    return max_val - min_val == len(arr) - 1

Output: True

This piece of code defines a function are_consecutive(arr) that first handles the edge case of an empty array. It then computes the minimum and maximum values of the array and returns True only if the range of numbers (max – min) is exactly one less than the number of elements in the array, implying they are consecutive.

Method 2: Sorting and Checking

By sorting an array, we can verify consecutiveness through a simple linear scan. Once sorted, we ensure each element sequentially differs by one. Though Python’s sort is not O(1) space, this approach illustrates a straightforward method that is easy to implement.

Here’s an example:

def are_consecutive(arr):
    arr.sort()
    for i in range(1, len(arr)):
        if arr[i] - arr[i - 1] != 1:
            return False
    return True

Output: True

The are_consecutive(arr) function sorts the array and iterates through it, checking if each element is exactly one greater than its predecessor. If not, the function returns False, indicating non-consecutive elements. The final return True implies that all elements are consecutive.

Method 3: Set Validation

Creating a set from the array can quickly tell us if there are duplicates, important for consecutiveness. We can then employ a similar strategy as in Method 1, by relying on the properties of the set without explicitly sorting the array.

Here’s an example:

def are_consecutive(arr):
    if len(arr) != len(set(arr)): return False
    return max(arr) - min(arr) == len(arr) - 1

Output: True

This approach, encapsulated in the are_consecutive(arr) function, converts the array to a set to eliminate duplicates. If the original array’s length equals the set’s length, every element is unique, and we verify consecutiveness by comparing the array’s range with its length as in the first method.

Method 4: Using Array Properties

This algorithm exploits a mathematical property: if an array is consecutive, the sum of its elements should be the same as the sum of an arithmetic series defined by its minimum and maximum. This comparison is done in linear time and without additional space requirements.

Here’s an example:

def are_consecutive(arr):
    if len(arr) <= 1: return True
    min_val = min(arr)
    expected_sum = len(arr) * (min_val + min_val + len(arr) - 1) // 2
    return sum(arr) == expected_sum

Output: True

This function, are_consecutive(arr), finds the minimum value and calculates the expected sum of a consecutive sequence starting from that value. It then compares the expected sum with the actual sum of the array to determine if the array is consecutive.

Bonus One-Liner Method 5: Lambda with All

A Pythonic one-liner leverages the built-in all() function combined with a lambda expression to succinctly express the consecutive property by comparing pairwise differences of sorted elements.

Here’s an example:

are_consecutive = lambda arr: all(arr[i] - arr[i - 1] == 1 for i in range(1, len(sorted(arr))))

Output: True

The lambda function sorts the array, then uses a generator within the all() function to check for consecutive differences. If all differences are exactly one, the result is True, and consequently False if any pair fails this test.

Summary/Discussion

  • Method 1: Check with Range. Straightforward and efficient. However, it fails if elements are repeated.
  • Method 2: Sorting and Checking. Simple to understand and implement. Not O(1) space due to sorting, and it mutates the input array.
  • Method 3: Set Validation. Combines space efficiency with the set uniqueness property. Effective but same weakness as Method 1 with repeated elements.
  • Method 4: Using Array Properties. Clever use of mathematical properties. Handles unique and repeated numbers correctly but slightly less intuitive.
  • Bonus One-Liner Method 5: Lambda with All. Compact code. It is more of a brain teaser and is not truly O(1) space because of sorting.