Skip to main content

1502. Can Make Arithmetic Progression From Sequence

easy

Determine whether you can reorder an array into an arithmetic progression. Sort, then verify constant pairwise differences. An accessible warm-up on rearrangement reasoning.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

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.

Constraints

  • 2 <= arr.length <= 1000
  • -10^6 <= arr[i] <= 10^6

Examples

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.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

An arithmetic progression's reorder is just its sorted form (or its reverse).

Hint 2

Sort, then check that arr[i+1] - arr[i] is constant across the whole array.

Hint 3

Bit-twist for an O(n)/O(n) variant: find min and max, derive the implied difference d = (max - min) / (n - 1), then verify each element fits the AP using a hash set or by checking divisibility of (x - min) by d.

Solution approach

Reveal approach

Sort and verify constant gap. Sort arr in place. Compute d = arr[1] - arr[0]. For i from 2 to n - 1, return false if arr[i] - arr[i-1] != d. Otherwise return true. O(n log n) time, O(1) extra space (in-place sort). The hash-set O(n) variant: find min and max in one pass, compute d = (max - min) / (n - 1) and reject if (max - min) % (n - 1) != 0, then check each element x satisfies (x - min) % d == 0 and falls in [min, max], and that the set of elements has size n (no duplicates other than when d = 0).

Complexity

Time
O(n log n)
Space
O(1)

Related patterns

  • sorting
  • hash-map

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon

Practice these live with InterviewChamp.AI

Drill Can Make Arithmetic Progression From Sequence and Bit Manipulation problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →