Can Make Arithmetic Progression From Sequence - Solution & Explanation
Problem Statement
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.
Example 1:
Input: arr = [3,5,1] Output: true Explanation: 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 Explanation: There is no way to reorder the elements to obtain an arithmetic progression.
Constraints:
2 <= arr.length <= 1000-106 <= arr[i] <= 106
Approach Overview
Problem Overview: You receive an integer array. Rearrange the numbers and determine whether they can form an arithmetic progression. In an arithmetic progression, the difference between every pair of adjacent elements is the same.
Approach 1: Sorting and Checking (Time: O(n log n), Space: O(1))
The most direct approach sorts the array first using a standard sorting algorithm. Once sorted, the numbers must already be in the only order where an arithmetic progression could exist. Compute the difference between the first two elements (arr[1] - arr[0]) and iterate through the rest of the array verifying that every adjacent pair has the same difference. If any pair breaks the pattern, return false. Sorting costs O(n log n) time, and the verification pass is O(n). Extra space is O(1) if the sort is done in-place.
This approach is reliable and easy to implement. You simply reorder the array, then validate the arithmetic property with one linear scan. Because of its simplicity, many interview solutions start here before discussing more optimal alternatives.
Approach 2: Hash Set for Difference Tracking (Time: O(n), Space: O(n))
You can avoid sorting by using a hash-based membership check. First compute the minimum and maximum values in the array. If the numbers form an arithmetic progression of length n, the common difference must be (max - min) / (n - 1). If this value is not an integer, forming a valid progression is impossible.
Next insert every element into a hash set. Starting from min, repeatedly add the calculated difference and check whether each expected value exists in the set. Perform this check exactly n times. If any value is missing, the sequence cannot form the progression. Hash lookups run in constant time, so the entire algorithm completes in O(n) time with O(n) space.
This approach relies on constant-time membership checks and simple arithmetic rather than reordering the data. The technique commonly appears in array and hash-based interview problems where the target pattern can be computed directly from the minimum and maximum values.
Recommended for interviews: The sorting approach is usually expected first because it shows you recognize that order matters in an arithmetic progression. After presenting that solution, discussing the hash-set optimization demonstrates deeper algorithmic thinking by reducing the complexity from O(n log n) to O(n). Many interviewers are satisfied with the sorted approach, but the linear-time method shows stronger problem-solving skills.
Approach 1: Sorting and Checking
To determine if the array can be rearranged to form an arithmetic progression, first sort the array. If the sorted array has a consistent difference between every consecutive pair of elements, it is an arithmetic progression. This approach involves sorting the array and then simply checking the difference between each pair of adjacent elements.
The C code sorts the input array using qsort and then checks if each consecutive pair of elements has the same difference. If they do, the function returns true. Otherwise, it returns false.
Complexity
Time Complexity: O(n log n) due to sorting. Space Complexity: O(1) since the algorithm uses constant extra space.
Approach 2: Hash Set for Difference Tracking
We can use a HashSet (or similar data structure) to track the number of unique differences between pairs of elements in the array without sorting. If the array can be rearranged into an arithmetic progression, the number of unique differences should equal exactly one when you compare all pairs.
This Python solution calculates the expected difference and checks if every value that should be present in the arithmetic progression exists in the set (array is treated as a set to facilitate O(1) lookup).
Code
Python
Complexity
Time Complexity: O(n), for the set operations. Space Complexity: O(n) due to using a set.
Approach 3: Sorting + Traversal
We can first sort the array arr, then traverse the array, and check whether the difference between adjacent items is equal.
The time complexity is O(n times log n), and the space complexity is O(log n). Here, n is the length of the array arr.
Code
Python
Java
C++
Go
TypeScript
Rust
JavaScript
C
Approach 4: Hash Table + Mathematics
We first find the minimum value a and the maximum value b in the array arr. If the array arr can be rearranged into an arithmetic sequence, then the common difference d = \frac{b - a}{n - 1} must be an integer.
We can use a hash table to record all elements in the array arr, then traverse i \in [0, n), and check whether a + d times i is in the hash table. If not, it means that the array arr cannot be rearranged into an arithmetic sequence, and we return false. Otherwise, after traversing the array, we return true.
The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the array arr.
Code
Python
Java
C++
Go
TypeScript
Rust
JavaScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Sorting and Checking | Time Complexity: O(n log n) due to sorting. Space Complexity: O(1) since the algorithm uses constant extra space. |
| Hash Set for Difference Tracking | Time Complexity: O(n), for the set operations. Space Complexity: O(n) due to using a set. |
| Sorting + Traversal | — |
| Hash Table + Mathematics | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sorting and Checking | O(n log n) | O(1) | Best default solution. Simple implementation when modifying the array order is allowed. |
| Hash Set Difference Tracking | O(n) | O(n) | When you want linear time without sorting and can afford extra memory. |
Video Solution
Can Make Arithmetic Progression From Sequence | 2 Approaches | GOOGLE | Leetcode-1502 • codestorywithMIK • 2,952 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Can Make Arithmetic Progression From Sequence easy or hard?
Can Make Arithmetic Progression From Sequence Python/Java solution
How to solve Can Make Arithmetic Progression From Sequence in O(n)?
What is the best approach for Can Make Arithmetic Progression From Sequence?
Is Can Make Arithmetic Progression From Sequence asked at Google/Amazon/Meta?
What data structure is used in Can Make Arithmetic Progression From Sequence?
What is the time complexity of Can Make Arithmetic Progression From Sequence?
Ready to solve this problem?
Practice Can Make Arithmetic Progression From Sequence with our built-in code editor and test cases.
Practice on FleetCode