Can Make Arithmetic Progression From Sequence

Difficulty: Easy | Acceptance: 69.00% | Paid: No Topics: Array, Sorting

A sequence of numbers is called an arithmetic progression if the difference between any two consecutive elements is the same.

Given an array of numbers arr, return true if the array can be rearranged to form an arithmetic progression. Otherwise, return false.

• Examples
• Constraints
• Sorting Approach
• Mathematical Set Approach

Examples

Input: arr = [3,5,1]
Output: true
Explanation: We can reorder the elements as [1,3,5] or [5,3,1] which are arithmetic progressions with difference 2 or -2 respectively.

Input: arr = [1,2,4]
Output: false
Explanation: There is no way to reorder the elements to form an arithmetic progression.

Constraints

2 <= arr.length <= 1000
-10^6 <= arr[i] <= 10^6

Sorting Approach

Intuition If we sort the array, an arithmetic progression will naturally appear in order. We can then simply verify that the difference between every consecutive pair of elements is constant.

Steps

• Sort the array in ascending order.
• Calculate the difference diff between the first two elements.
• Iterate through the array starting from the third element.
• If the difference between the current element and the previous one is not equal to diff, return false.
• If the loop finishes without mismatches, return true.

class Solution:
    def canMakeArithmeticProgression(self, arr: list[int]) -> bool:
        arr.sort()
        diff = arr[1] - arr[0]
        for i in range(2, len(arr)):
            if arr[i] - arr[i - 1] != diff:
                return False
        return True

Complexity

• Time: $O(n \log n)$ due to the sorting step.
• Space: $O(1)$ or $O(\log n)$ depending on the sorting algorithm’s memory usage.
• Notes: Simple to implement and understand, but not the most time-efficient.

Mathematical Set Approach

Intuition In a valid arithmetic progression, the minimum and maximum values are the first and last terms. The common difference d must be (max - min) / (n - 1). We can calculate this d and verify that every expected term exists in the array using a hash set.

Steps

• Find the minimum (min_val) and maximum (max_val) in the array.
• If min_val equals max_val, return true (all elements are the same).
• Calculate the common difference d = (max_val - min_val) / (n - 1).
• If (max_val - min_val) is not divisible by (n - 1), return false (progression impossible).
• Store all elements of the array in a hash set.
• Iterate i from 0 to n - 1. For each i, check if min_val + i * d exists in the set.
• If any term is missing, return false; otherwise, return true.

class Solution:
    def canMakeArithmeticProgression(self, arr: list[int]) -> bool:
        n = len(arr)
        if n <= 2:
            return True
        
        min_val = min(arr)
        max_val = max(arr)
        
        if (max_val - min_val) % (n - 1) != 0:
            return False
        
        diff = (max_val - min_val) // (n - 1)
        if diff == 0:
            return True
            
        s = set(arr)
        for i in range(n):
            if (min_val + i * diff) not in s:
                return False
        return True

Complexity

• Time: $O(n)$ since we iterate through the array a constant number of times.
• Space: $O(n)$ to store the elements in the hash set.
• Notes: Faster time complexity than sorting, but uses extra memory.