Can Make Arithmetic Progression From Sequence Python/Java solution

In Python or Java, the simplest solution sorts the array using built-in sorting and then compares adjacent differences in a loop. The optimized version uses a HashSet (Java) or set (Python) to store elements and validate each expected value in O(1) lookup time.

How to solve Can Make Arithmetic Progression From Sequence in O(n)?

Compute the minimum and maximum values in the array and derive the common difference as (max - min) / (n - 1). Insert all elements into a hash set, then check whether the sequence min, min + diff, min + 2*diff, ... exists in the set. Each lookup is O(1), so the full validation runs in O(n) time.

What is the best approach for Can Make Arithmetic Progression From Sequence?

The most practical approach sorts the array and then checks whether every adjacent pair has the same difference. Sorting takes O(n log n) time and the validation pass is O(n). An alternative linear-time solution uses a hash set with the formula (max - min) / (n - 1) to verify all expected elements exist.

Is Can Make Arithmetic Progression From Sequence asked at Google/Amazon/Meta?

Arithmetic progression validation problems appear frequently in technical screens focused on array manipulation and basic math reasoning. Variants of this problem have appeared in interviews at companies like Amazon and other large tech firms during early algorithm rounds.

What data structure is used in Can Make Arithmetic Progression From Sequence?

The typical implementations rely on arrays and sorting. The optimized approach introduces a hash set to perform constant-time membership checks when validating the expected arithmetic sequence.

What is the time complexity of Can Make Arithmetic Progression From Sequence?

The common solution that sorts the array runs in O(n log n) time and O(1) extra space if sorting is in-place. A more optimized method using a hash set runs in O(n) time with O(n) space by verifying each expected value in the progression directly.

Description Hints 2 Solution Video 16:11

1502. Can Make Arithmetic Progression From Sequence

Q: Is Can Make Arithmetic Progression From Sequence easy or hard?

LeetCode classifies this problem as Easy. The logic mainly involves sorting and verifying equal differences, though recognizing the O(n) hash-set optimization demonstrates stronger algorithmic understanding.

Easy68.9% acceptance5 companies

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
-10⁶ <= arr[i] <= 10⁶

Asked at 5 companies

Google Bloomberg Amazon Microsoft Meta

Topics

Array Sorting

Hints open one at a time

Hint 1

Consider that any valid arithmetic progression will be in sorted order.

Hint 2

Sort the array, then check if the differences of all consecutive elements are equal.

16:11

Still stuck?Read 4 approaches, or watch a walkthrough.

Open solution