Watch 10 video solutions for Can Make Arithmetic Progression From Sequence, a easy level problem involving Array, Sorting. This walkthrough by codestorywithMIK has 2,728 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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] <= 106Problem 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 | 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. |