Domain 1EasyCORE

Can Make Arithmetic Progression From Sequence

The problem asks us to determine if an array can be rearranged into an arithmetic progression. An arithmetic progression is defined as a sequence where the difference between any two consecutive elements is constant.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Array#Sort

1502. Can Make Arithmetic Progression From Sequence

Model: qwen2.5-coder:14b
Topics: Array,Sort
FAANG asked: 1
Acceptance rate: 71.2%


Problem Breakdown

The problem asks us to determine if an array can be rearranged into an arithmetic progression. An arithmetic progression is defined as a sequence where the difference between any two consecutive elements is constant.

Inputs:

  • An array of integers arr.

Outputs:

  • A boolean value: true if the array can be rearranged into an arithmetic progression, otherwise false.

Implicit Constraints and Edge Cases:

  • The array length is between 2 and 1000.
  • Array elements range from -10^6 to 10^6.
  • Duplicates are allowed.
  • Negative numbers are possible.

Intuition

A brute-force approach would involve generating all permutations of the array and checking if any permutation forms an arithmetic progression. However, this is computationally expensive with a time complexity of O(n!), which is infeasible given the constraints.

The key insight is that for an array to form an arithmetic progression, once sorted, the difference between consecutive elements should be constant. This leads us to sort the array and then check if the differences between consecutive elements are consistent.

Approach

  1. Sort the Array: Sort the input array arr.
  2. Calculate Common Difference: Compute the common difference as the difference between the first two elements of the sorted array.
  3. Verify Consistency: Iterate through the sorted array and check if the difference between each pair of consecutive elements is equal to the common difference.
  4. Return Result: If all differences are consistent, return true. Otherwise, return false.

Complexity Analysis

  • Time Complexity: O(n log n) due to the sorting step, where n is the length of the array.
  • Space Complexity: O(1) if we sort the array in place. If we consider the space used by the sorting algorithm (e.g., Timsort), it would be O(log n).

Solution

def canMakeArithmeticProgression(arr):
    arr.sort()  # Sort the array
    common_diff = arr[1] - arr[0]  # Calculate the common difference
    
    for i in range(2, len(arr)):
        if arr[i] - arr[i - 1] != common_diff:
            return False  # If any difference is not equal to the common difference, return False
    
    return True  # All differences are consistent

Edge Cases Handled

  • Empty Input: The problem constraints specify that the array length is between 2 and 1000, so this case does not apply.
  • Duplicates: Duplicates are allowed and handled naturally by sorting. If all elements are the same, they will form a valid arithmetic progression with a common difference of 0.
  • Negative Numbers: Negative numbers are handled correctly by the sorting and difference calculation.
  • Overflow: The problem constraints ensure that the array elements fit within the specified range, so overflow is not an issue.