#1502

Easy

LeetCode Problem Workspace

Can Make Arithmetic Progression From Sequence

Determine if a given array can be rearranged into a valid arithmetic progression using sorting and consecutive difference checks.

array sorting

Problem Statement

You are given an array of integers. A sequence is an arithmetic progression if the difference between each consecutive element is identical. Determine whether the array can be rearranged to form such a progression.

Return true if it is possible to reorder the array into an arithmetic progression; otherwise, return false. For example, given arr = [3,5,1], reordering to [1,3,5] results in consistent differences of 2 between elements.

Examples

Example 1

Input: arr = [3,5,1]

Output: true

We can reorder the elements as [1,3,5] or [5,3,1] with differences 2 and -2 respectively, between each consecutive elements.

Example 2

Input: arr = [1,2,4]

Output: false

There is no way to reorder the elements to obtain an arithmetic progression.

Constraints

2 <= arr.length <= 1000
-106 <= arr[i] <= 106

Solution Approach

Sort the Array

Start by sorting the array in ascending order. Sorting ensures that if the array can form an arithmetic progression, consecutive elements will reveal the required uniform difference. This step transforms the problem into a simple consecutive difference check.

Compute the Common Difference

Calculate the difference between the first two elements after sorting. This difference becomes the reference to verify the rest of the sequence. It defines the progression pattern and helps detect any deviations quickly.

Verify Consecutive Differences

Iterate through the sorted array, checking that each consecutive pair matches the calculated common difference. If any pair violates this difference, return false immediately. Otherwise, return true after the final comparison.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Sorting the array requires O(n log n) time, and verifying differences is O(n), resulting in overall O(n log n) time complexity. Space complexity is O(1) if sorting in-place or O(n) if a new array is created.

What Interviewers Usually Probe

Focus on transforming the array to detect uniform differences using sorting.
Expect candidates to handle edge cases where negative or large numbers appear.
Watch for efficient single-pass verification after sorting without unnecessary data structures.

Common Pitfalls or Variants

Common pitfalls

Skipping the sorting step and comparing non-consecutive elements directly.
Not checking for arrays with length exactly 2, which are always valid progressions.
Assuming the array is already in order and missing potential reordering needs.

Follow-up variants

Determine the minimal number of swaps needed to convert the array into an arithmetic progression.
Check if the array forms a geometric progression instead of arithmetic.
Handle arrays with floating point numbers and verify approximate equality within a tolerance.

FAQ

What defines a valid arithmetic progression in this problem?

A valid arithmetic progression has a constant difference between all consecutive elements, which can be checked after sorting the array.

Can an array with only two elements always form an arithmetic progression?

Yes, any array of two numbers can be rearranged trivially into an arithmetic progression.

Is sorting necessary to solve the Can Make Arithmetic Progression From Sequence problem?

Yes, sorting ensures that consecutive elements can be compared for uniform differences, which is essential for this Array plus Sorting pattern.

What if the array contains negative or duplicate numbers?

Negative and duplicate numbers are allowed; the progression is valid as long as the differences between consecutive sorted elements remain constant.

What is the time complexity of the recommended approach?

Sorting takes O(n log n) and verifying differences is O(n), resulting in overall O(n log n) time complexity.

terminal

Solution

Solution 1: Sorting + Traversal

We can first sort the array $\textit{arr}$, then traverse the array, and check whether the difference between adjacent items is equal.

1

2

3

4

5

class Solution:
    def canMakeArithmeticProgression(self, arr: List[int]) -> bool:
        arr.sort()
        d = arr[1] - arr[0]
        return all(b - a == d for a, b in pairwise(arr))

Solution 2: Hash Table + Mathematics

We first find the minimum value $a$ and the maximum value $b$ in the array $\textit{arr}$. If the array $\textit{arr}$ can be rearranged into an arithmetic sequence, then the common difference $d = \frac{b - a}{n - 1}$ must be an integer.

1

2

3

4

5

class Solution:
    def canMakeArithmeticProgression(self, arr: List[int]) -> bool:
        arr.sort()
        d = arr[1] - arr[0]
        return all(b - a == d for a, b in pairwise(arr))

Continue Practicing

#1498 number of subsequences that satisfy the given sum condition #1508 range sum of sorted subarray sums #1509 minimum difference between largest and smallest value in three moves