Can Make Arithmetic Progression From Sequence: Sort and Verify
LeetCode Can Make Arithmetic Progression From Sequence asks a deceptively simple question: given an array of numbers, can you rearrange them into an arithmetic progression? That means the difference between any two consecutive terms must be the same.
For example, [3, 5, 1] can be rearranged to [1, 3, 5] where every consecutive difference is 2. But [1, 2, 4] cannot form an arithmetic progression because the gaps are 1 and 2.
Why this problem matters
This is a warm-up for harder sequence validation problems. The technique of sorting first, then checking a structural property, appears everywhere. You will use the same approach in problems about consecutive sequences, evenly spaced intervals, and pattern detection in arrays. Mastering the basic version means you will not hesitate when the same idea shows up with additional constraints.
The key insight
An arithmetic progression has a constant difference between consecutive terms. If you sort the array, the elements must have equal spacing. So the algorithm is: sort, compute the expected difference from the first two elements, then verify every consecutive pair matches.
You do not need to try all permutations. Sorting locks the elements into the only order that could possibly form an arithmetic progression (or its reverse, which has the same absolute difference). One sort and one scan is all it takes.
The solution
def canMakeArithmeticProgression(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
After sorting, we grab the difference between the first two elements. Then we walk through the rest of the array checking that every consecutive pair has that same difference. The moment we find a mismatch, we return False. If we make it through the entire array, the answer is True.
This runs in O(n log n) time due to the sort, and O(1) extra space if you sort in place.
There is an O(n) approach that avoids sorting entirely. Find the min and max, compute the expected difference as (max - min) / (n - 1), then use a hash set to verify every expected value exists. This trades space for time, but the sorting approach is simpler to implement and explain in an interview.
Visual walkthrough
Step 1: Sort the array [3, 5, 1]
Sorting brings elements into order so we can check consecutive differences.
Step 2: Compute expected difference = arr[1] - arr[0] = 3 - 1 = 2
In a valid arithmetic progression, every consecutive pair must differ by this amount.
Step 3: Check all consecutive pairs: 3-1=2, 5-3=2. All match!
Every difference equals 2. Return true.
Failing example: [1, 2, 4] (already sorted)
Differences are 1 and 2. They don't match, so return false.
The step-by-step trace shows both paths: the happy case where all differences match and the failure case where a single mismatch is enough to return False immediately. Early termination is a nice bonus of this approach.
Complexity analysis
| Approach | Time | Space |
|---|---|---|
| Sort and check | O(n log n) | O(1) |
| Hash set (O(n)) | O(n) | O(n) |
The sort-based approach is the go-to for interviews because it uses constant extra space and the code is trivially short. The hash set approach is theoretically faster, but the constant factors and extra complexity rarely matter for the input sizes you will see on this problem (n is at most 1000).
If an interviewer asks for O(n), you can pivot to the hash set approach. But lead with the sort version since it is clean, correct, and easy to verify.
The building blocks
1. Sort and consecutive difference check
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
This pattern appears any time you need to verify uniform spacing in a sequence. Sort first to normalize the order, then check that adjacent elements satisfy some constraint. You will see this same structure in problems about detecting evenly spaced numbers, validating sorted sequences, and checking for arithmetic slices.
2. O(n) approach with formula-based indexing
def canMakeArithmeticProgression(arr: list[int]) -> bool:
n = len(arr)
min_val = min(arr)
max_val = max(arr)
if max_val - min_val == 0:
return True
if (max_val - min_val) % (n - 1) != 0:
return False
diff = (max_val - min_val) // (n - 1)
seen = set()
for num in arr:
if (num - min_val) % diff != 0:
return False
seen.add(num)
return len(seen) == n
This approach computes the expected common difference from the range and count. Then it verifies that every element fits the formula min + k * diff for some integer k, and that there are no duplicates. It runs in O(n) time using O(n) space for the set. The key insight is that if an arithmetic progression exists, its common difference is fully determined by the min, max, and length.
Edge cases
- Array of length 2: any two numbers form a valid arithmetic progression. Your code handles this naturally since there is only one difference to check.
- All elements are the same: the common difference is 0, and every pair matches. Works correctly with no special case.
- Negative numbers: sorting handles negatives correctly. The difference can be negative (e.g.,
[5, 3, 1]sorts to[1, 3, 5]with diff = 2) or the values themselves can be negative. - Large range with small n: no overflow issues in Python. In languages like Java or C++, be careful with integer arithmetic when computing differences.
- Already sorted input: the algorithm still works, it just means the sort is a no-op.
From understanding to recall
Reading this solution feels obvious. You sort, you check differences, you return. But in a live interview three weeks from now, will you remember to handle the edge case where all elements are equal? Will you instinctively reach for the sort-and-scan pattern instead of overthinking it?
That gap between understanding and recall is what spaced repetition closes. By drilling the sort-and-verify pattern as an isolated building block, you train your brain to produce it on demand. The first time you see it, you reason through it. After a few spaced repetitions, it fires automatically.
Related posts
- Contains Duplicate - Another problem where sorting reveals structure that would be expensive to find otherwise
- Longest Consecutive Sequence - Uses a hash set to find sequences without sorting, similar to the O(n) approach here
- Arithmetic Slices - Extends the arithmetic progression concept to finding all contiguous subarrays with constant difference
Arithmetic progression detection is a small building block, but it shows up inside larger problems more often than you would expect. Master the sort-and-verify pattern here, and you will recognize it instantly when it appears as a subproblem in medium and hard questions.