Leetcode – Can Make Arithmetic Progression From Sequence Solution

Spread the love

Arithmetic progression is a topic that spans across multiple domains such as mathematics, computer science, and even real-world applications. Leetcode’s “Can Make Arithmetic Progression From Sequence” problem offers a hands-on exercise for understanding and implementing the concept of arithmetic progression in a programmatic way. This problem provides the right mix of array manipulation and sorting algorithms, with a dash of mathematical knowledge. In this comprehensive guide, we will cover multiple approaches to solving the problem, discuss their time and space complexities.

Problem Statement

Given an array of numbers arr, the task is to return True if the array can be rearranged to form an arithmetic sequence; otherwise, return False.

Example

Input: arr = [3, 5, 1]
Output: True
Explanation: The array can be rearranged as [1, 3, 5], which is an arithmetic sequence (1, 3, 5) with a common difference of 2.

The Brute-Force Approach: Generating All Permutations

One could think of generating all permutations of the array and checking each one to see if it forms an arithmetic sequence. However, this approach would have a time complexity of O(n!), which is not feasible for large arrays. Hence, this approach is generally not recommended for this problem.

Sorting the Array: The Simplified Approach

The most straightforward way to solve this problem is by sorting the array. Once sorted, it becomes easy to check for an arithmetic progression.

Python Code:

def canMakeArithmeticProgression(arr):
    arr.sort()
    diff = arr[1] - arr[0]

    for i in range(1, len(arr) - 1):
        if arr[i + 1] - arr[i] != diff:
            return False
    return True

# Test the function
print(canMakeArithmeticProgression([3, 5, 1]))  # Output should be True

Time Complexity

The time complexity for sorting the array is O(n log ⁡n) and checking for an arithmetic progression takes O(n), making the overall time complexity O(n log⁡ n).

Space Complexity

The space complexity is O(1) since no additional space is used other than the input array and some variables.

Optimized Approach: Using the Formula for Arithmetic Progressions

Arithmetic progressions have a mathematical property: the maximum and minimum elements of the sequence determine all other elements. Specifically, every element can be represented as min+(i×difference), where difference=max−min / length of array−1​. We can use this property to create a more optimized solution:

Python Code:

def canMakeArithmeticProgression(arr):
    min_val, max_val = min(arr), max(arr)
    if min_val == max_val:
        return True
    
    n = len(arr)
    diff = (max_val - min_val) / (n - 1)
    
    if diff == 0:
        return False
    
    visited = set()
    for num in arr:
        if (num - min_val) % diff != 0:
            return False
        if num in visited:
            return False
        visited.add(num)
    
    return True

# Test the function
print(canMakeArithmeticProgression([3, 5, 1]))  # Output should be True

Time Complexity

This approach has a time complexity of O(n) for finding the minimum and maximum and another O(n) for the iteration, making it O(n) overall.

Space Complexity

The space complexity is O(n) for the set visited.

Edge Cases and Further Considerations

  • Small Arrays: What if the array has fewer than 2 elements? In that case, the array can always be considered an arithmetic progression.
  • Duplicate Elements: What if the array has duplicate elements? An arithmetic progression must consist of distinct elements.

Conclusion

The “Can Make Arithmetic Progression From Sequence” problem is a classic example that combines array manipulation with mathematical reasoning. It allows one to explore different approaches ranging from sorting algorithms to the mathematical properties of arithmetic sequences.

Leave a Reply