Can Make Arithmetic Progression From Sequence
What is this problem about?
The Can Make Arithmetic Progression From Sequence interview question asks you to determine if a given array of numbers can be rearranged to form an arithmetic progression. A sequence is an arithmetic progression if the difference between any two consecutive elements is constant. This Can Make Arithmetic Progression From Sequence coding problem is a fundamental test of pattern recognition and sorting.
Why is this asked in interviews?
Amazon uses this "Easy" level question to check for basic algorithmic thinking and familiarity with sequence properties. It tests if you can identify the necessary conditions for a progression (sorting) or if you can optimize it using a set-based approach to achieve O(N) time complexity.
Algorithmic pattern used
This follows the Array, Sorting interview pattern.
- Sort the array.
- Calculate the difference between the first two elements (diff = nums[1] - nums[0]).
- Iterate through the rest of the array and ensure that nums[i] - nums[i-1] == diff.
An alternative O(N) approach involves finding the min and max, calculating the expected diff, and checking if all expected elements exist in a Hash Set.
Example explanation
Input: [3, 5, 1]
- Sort the array: [1, 3, 5].
- First difference: 3 - 1 = 2.
- Next difference: 5 - 3 = 2.
- All differences are equal. Result: True.
Input: [1, 2, 4]
- Sorted: [1, 2, 4].
- 2 - 1 = 1, but 4 - 2 = 2.
- Result: False.
Common mistakes candidates make
- Not sorting first: Trying to check differences in the original order, which might not be an arithmetic progression yet.
- Handling duplicates: Forgetting that an arithmetic progression can have a difference of 0 (all elements are the same).
- Floating point errors: Not an issue with integers, but something to keep in mind if the input was decimal-based.
Interview preparation tip
Always consider both the sorting approach (O(N log N)) and the Hash Set approach (O(N)). While sorting is simpler to implement, mentioning the O(N) optimization shows the interviewer you're thinking about performance.
