Problem Description

An arithmetic progression is a sequence of numbers where the difference between any two consecutive elements is always the same constant value.

Given an array of numbers arr, determine if it's possible to rearrange the elements to form an arithmetic progression. Return true if the array can be rearranged into an arithmetic progression, otherwise return false.

For example:

• The array [3, 5, 1] can be rearranged to [1, 3, 5], which forms an arithmetic progression with a common difference of 2 between consecutive elements.
• The array [1, 2, 4] cannot be rearranged to form an arithmetic progression since no arrangement would have equal differences between all consecutive pairs.

The solution works by first sorting the array, then checking if all consecutive pairs have the same difference. After sorting, if the array can form an arithmetic progression, the difference between the first two elements should be maintained throughout the entire sorted sequence.

Intuition

The key insight is that an arithmetic progression has a natural ordering - the elements must be arranged in either ascending or descending order for the constant difference property to hold. If we have numbers that can form an arithmetic progression, there's only one valid arrangement (ignoring the reverse).

Think about it this way: if we have numbers that form an arithmetic progression with difference d, then starting from the smallest number, each subsequent number must be exactly d units larger. This means the numbers have a fixed relative positioning to each other.

By sorting the array first, we automatically arrange the numbers in the only possible order they could form an arithmetic progression. Once sorted, we just need to verify that the difference between every pair of consecutive elements is the same.

For example, if we have [3, 5, 1]:

• After sorting: [1, 3, 5]
• Check differences: 3 - 1 = 2 and 5 - 3 = 2
• Since all differences equal 2, it's an arithmetic progression

This approach eliminates the need to try different arrangements - sorting gives us the canonical arrangement to check. If this sorted arrangement doesn't have a constant difference between consecutive elements, then no rearrangement will work.

Learn more about Sorting patterns.

Solution Approach

The implementation follows a straightforward two-step process:

Step 1: Sort the array

arr.sort()

We sort the array in ascending order using Python's built-in sort() method. This arranges all elements from smallest to largest, which is the natural ordering for an arithmetic progression.

Step 2: Check constant difference

d = arr[1] - arr[0]
return all(b - a == d for a, b in pairwise(arr))

After sorting, we:

1. Calculate the expected common difference d by finding the difference between the first two elements: arr[1] - arr[0]
2. Use the pairwise() function to iterate through consecutive pairs of elements in the sorted array
3. For each pair (a, b), check if their difference b - a equals the expected difference d
4. Use the all() function to verify that every consecutive pair has the same difference

The pairwise(arr) function generates tuples of consecutive elements: (arr[0], arr[1]), (arr[1], arr[2]), ..., (arr[n-2], arr[n-1]). This allows us to efficiently check all adjacent differences in a single expression.

Time Complexity: O(n log n) due to sorting, where n is the length of the array
Space Complexity: O(1) if we consider the sorting to be in-place, or O(n) depending on the sorting algorithm implementation

The solution is elegant because it leverages Python's built-in functions to create a concise and readable implementation that directly reflects the mathematical definition of an arithmetic progression.

Example Walkthrough

Let's walk through the solution with the array [5, 1, 9, 3].

Step 1: Sort the array

• Original array: [5, 1, 9, 3]
• After sorting: [1, 3, 5, 9]

Step 2: Calculate the expected common difference

• Take the first two elements: arr[0] = 1 and arr[1] = 3
• Calculate difference: d = 3 - 1 = 2

Step 3: Check all consecutive pairs Using pairwise(arr), we get the following pairs and check each difference:

• Pair (1, 3): difference = 3 - 1 = 2 ✓ (equals d)
• Pair (3, 5): difference = 5 - 3 = 2 ✓ (equals d)
• Pair (5, 9): difference = 9 - 5 = 4 ✗ (does not equal d)

Step 4: Return result Since not all consecutive differences equal d = 2, the all() function returns false. The array cannot be rearranged to form an arithmetic progression.

Counter-example that works: If we had [5, 1, 9, 13] instead:

• After sorting: [1, 5, 9, 13]
• Expected difference: d = 5 - 1 = 4
• Check pairs: (1, 5) → 4, (5, 9) → 4, (9, 13) → 4
• All differences equal 4, so return true

This walkthrough demonstrates how sorting automatically arranges the elements in the only possible order for an arithmetic progression, and then we simply verify if the constant difference property holds throughout the sorted sequence.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n × log n)

The time complexity is dominated by the arr.sort() operation, which uses Python's Timsort algorithm with a worst-case time complexity of O(n × log n), where n is the length of the array. The subsequent iteration through pairwise(arr) with the all() function takes O(n) time, as it iterates through n-1 pairs. Therefore, the overall time complexity is O(n × log n) + O(n) = O(n × log n).

Space Complexity: O(log n)

The space complexity comes from the sorting operation. Python's Timsort algorithm uses O(log n) space for its recursive call stack in the worst case. The pairwise() function returns an iterator that generates pairs on-the-fly, using only O(1) additional space. The all() function also uses O(1) space as it processes the generator expression without creating a list. Therefore, the overall space complexity is O(log n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Assuming the Input Array is Already Sorted

One of the most common mistakes is forgetting to sort the array before checking differences. Developers might incorrectly assume the input is sorted or try to check differences in the original order.

Incorrect approach:

def canMakeArithmeticProgression(self, arr: List[int]) -> bool:
    # WRONG: Checking differences without sorting first
    d = arr[1] - arr[0]
    for i in range(2, len(arr)):
        if arr[i] - arr[i-1] != d:
            return False
    return True

Why it fails: For input [3, 5, 1], this would check differences as 5-3=2 and 1-5=-4, returning False even though the array can form an arithmetic progression when rearranged.

2. Not Handling Edge Cases with Small Arrays

Arrays with fewer than 2 elements require special handling. While arrays with 0 or 1 element technically form an arithmetic progression, the code might crash when trying to access arr[1].

Solution:

def canMakeArithmeticProgression(self, arr: List[int]) -> bool:
    # Handle edge cases
    if len(arr) <= 2:
        return True
  
    arr.sort()
    common_difference = arr[1] - arr[0]
    # Continue with the rest of the logic...

3. Off-by-One Errors in Loop Boundaries

When manually iterating through pairs, it's easy to create index out of bounds errors or miss checking certain pairs.

Incorrect approach:

# WRONG: Loop goes too far, causing index out of bounds
for i in range(len(arr)):
    if arr[i + 1] - arr[i] != common_difference:  # IndexError when i = len(arr)-1
        return False

Correct approach:

# Correct: Loop stops at len(arr) - 1
for i in range(len(arr) - 1):
    if arr[i + 1] - arr[i] != common_difference:
        return False

4. Modifying the Original Array Unexpectedly

Using arr.sort() modifies the input array in-place, which might cause issues if the caller expects the original array to remain unchanged.

Solution for preserving original array:

def canMakeArithmeticProgression(self, arr: List[int]) -> bool:
    # Create a sorted copy instead of modifying original
    sorted_arr = sorted(arr)
  
    common_difference = sorted_arr[1] - sorted_arr[0]
    return all(second - first == common_difference 
               for first, second in pairwise(sorted_arr))

5. Integer Overflow in Other Languages

While not an issue in Python (which handles arbitrary precision integers), in languages like Java or C++, calculating differences between large integers could cause overflow.

Prevention strategy: In other languages, consider using appropriate data types (like long in Java) or check for overflow conditions when dealing with large values.