LeetCode 1502 - Can Make Arithmetic Progression From Sequence

LeetCode Problem 1502

Difficulty: 🟢 Easy
Topics: Array, Sorting

Solution

Problem Understanding

The problem asks us to determine whether the elements of a given array can be rearranged so that they form an arithmetic progression.

An arithmetic progression is a sequence where the difference between every pair of consecutive elements is the same. For example, [1, 3, 5, 7] is an arithmetic progression because every adjacent difference is 2. Similarly, [10, 7, 4, 1] is also an arithmetic progression because every adjacent difference is -3.

The important detail in this problem is that we are allowed to rearrange the array. The original order does not matter. We only need to check whether some ordering of the elements exists that satisfies the arithmetic progression condition.

The input is an integer array arr, and the output is a boolean value:

• Return true if the array can be reordered into an arithmetic progression.
• Return false otherwise.

The constraints tell us several important things:

• The array length is between 2 and 1000, which is relatively small.
• Values range from -10^6 to 10^6, meaning negative numbers are possible.
• Since the array size is modest, an O(n log n) sorting solution is perfectly acceptable.

A key observation is that if an array can be rearranged into an arithmetic progression, then sorting the array reveals the only valid increasing arrangement. Once sorted, every adjacent difference must be identical. If even one difference is different, no rearrangement can fix it.

Several edge cases are worth considering upfront. Arrays with duplicate values can still form arithmetic progressions if the common difference is zero, such as [5, 5, 5]. Negative numbers should work naturally because differences may also be negative before sorting. Arrays of length 2 always form an arithmetic progression because any two numbers define a constant difference. Another important case is when values appear unordered, such as [3, 5, 1], where sorting makes the progression obvious.

Approaches

Brute Force Approach

A brute force approach would try every possible rearrangement of the array and check whether any ordering forms an arithmetic progression.

For each permutation, we would compute the difference between the first two elements and then verify whether every consecutive pair has the same difference. If we find one valid arrangement, we return true. Otherwise, after checking all permutations, we return false.

This approach is correct because it exhaustively explores every possible ordering. If an arithmetic progression exists, one of the permutations must match it.

However, this method is prohibitively expensive. An array of size n has n! permutations, which grows extremely fast. Even for moderate values of n, this becomes computationally infeasible.

Optimal Approach

The key insight is that if a sequence can form an arithmetic progression, then its sorted order must also be an arithmetic progression.

Why is this true? In any arithmetic progression, numbers are evenly spaced. Sorting simply arranges them in ascending order, preserving the constant gap between adjacent terms. Therefore, we only need to:

1. Sort the array.
2. Compute the difference between the first two elements.
3. Verify that every adjacent pair has the same difference.

If every difference matches, return true. Otherwise, return false.

Sorting dramatically reduces the complexity from factorial time to O(n log n).

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n! × n)	O(n)	Tries every permutation and validates arithmetic progression
Optimal	O(n log n)	O(1) or O(log n)	Sorts array and checks adjacent differences

Algorithm Walkthrough

Optimal Algorithm

1. Sort the array in ascending order.

Sorting is necessary because any valid arithmetic progression has a natural ordered form. If the array can be rearranged into a progression, its sorted order must have a constant difference. 2. Compute the expected common difference.

After sorting, calculate:

$$difference = arr[1] - arr[0]$$

This becomes the expected spacing between all adjacent elements. 3. Traverse the sorted array.

Start from index 2 and compare each adjacent difference:

$$arr[i] - arr[i - 1]$$

against the expected difference. 4. Return false if any mismatch occurs.

A single inconsistent gap means the sequence cannot form an arithmetic progression. 5. Return true after completing the traversal.

If every consecutive difference matches, the sorted sequence is an arithmetic progression, which means some rearrangement exists.

Why it works

The correctness relies on the fact that an arithmetic progression is uniquely determined by a constant difference between ordered terms. If the array can be rearranged into such a sequence, sorting those elements preserves the spacing while placing them in increasing order. Therefore, checking adjacent differences in sorted order is sufficient to determine whether a valid progression exists.

Python Solution

from typing import List

class Solution:
    def canMakeArithmeticProgression(self, arr: List[int]) -> bool:
        arr.sort()

        common_difference = arr[1] - arr[0]

        for index in range(2, len(arr)):
            current_difference = arr[index] - arr[index - 1]

            if current_difference != common_difference:
                return False

        return True

The implementation starts by sorting the input array in place using arr.sort(). This ensures the numbers are arranged in ascending order, making it easy to check whether the spacing between consecutive elements is consistent.

Next, the code computes the expected common difference using the first two elements. This value becomes the benchmark for all later comparisons.

The loop begins at index 2 because the first difference has already been established. For each position, the implementation calculates the difference between the current element and the previous one. If the difference does not match the expected value, the function immediately returns False.

If the loop finishes without finding any inconsistency, all adjacent differences are identical, meaning the sequence forms an arithmetic progression. The function then returns True.

Go Solution

package main

import "sort"

func canMakeArithmeticProgression(arr []int) bool {
	sort.Ints(arr)

	commonDifference := arr[1] - arr[0]

	for i := 2; i < len(arr); i++ {
		currentDifference := arr[i] - arr[i-1]

		if currentDifference != commonDifference {
			return false
		}
	}

	return true
}

The Go implementation follows the same logic as the Python version. The array is sorted using sort.Ints(), which sorts the slice in place.

One Go specific detail is that slices are reference-like structures, so sorting directly modifies the input slice. This is acceptable in LeetCode because mutation of the input is allowed.

Integer overflow is not a concern here because the difference between values within the given constraints still fits comfortably inside Go's int type.

Worked Examples

Example 1

Input:

arr = [3,5,1]

Step 1: Sort the array

Step	Array State
Initial	[3,5,1]
After sorting	[1,3,5]

Step 2: Compute common difference

common_difference = 3 - 1 = 2

Step 3: Check remaining differences

Index	Current Pair	Difference	Matches Expected?
2	(5, 3)	2	Yes

All differences match.

Output:

true

Example 2

Input:

arr = [1,2,4]

Step 1: Sort the array

Step	Array State
Initial	[1,2,4]
After sorting	[1,2,4]

Step 2: Compute common difference

common_difference = 2 - 1 = 1

Step 3: Check remaining differences

Index	Current Pair	Difference	Matches Expected?
2	(4, 2)	2	No

Since the difference does not match, return false.

Output:

false

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n)	Sorting dominates the runtime
Space	O(1) or O(log n)	Depends on the sorting implementation

The dominant operation is sorting the array, which takes O(n log n) time. After sorting, we perform a single linear scan through the array, which takes O(n) time. Since O(n log n) dominates O(n), the overall complexity is O(n log n).

The space complexity depends on the underlying sorting implementation. Python's sorting algorithm may use additional memory internally, while Go's sort implementation uses logarithmic recursion depth in practice. Conceptually, excluding sort internals, the algorithm only uses a few extra variables.

Test Cases

solution = Solution()

assert solution.canMakeArithmeticProgression([3, 5, 1]) is True  # Example 1
assert solution.canMakeArithmeticProgression([1, 2, 4]) is False  # Example 2

assert solution.canMakeArithmeticProgression([1, 3]) is True  # Minimum size array
assert solution.canMakeArithmeticProgression([5, 5, 5]) is True  # All equal values
assert solution.canMakeArithmeticProgression([7, 3, -1, -5]) is True  # Negative progression
assert solution.canMakeArithmeticProgression([1, 1, 2]) is False  # Duplicates but invalid
assert solution.canMakeArithmeticProgression([10, 0, -10]) is True  # Negative common difference after rearrangement
assert solution.canMakeArithmeticProgression([1000000, 0, -1000000]) is True  # Large values
assert solution.canMakeArithmeticProgression([1, 4, 7, 11]) is False  # One incorrect difference
assert solution.canMakeArithmeticProgression([9, 7, 5, 3, 1]) is True  # Reverse order input

Test	Why
[3,5,1]	Validates provided positive example
[1,2,4]	Validates provided negative example
[1,3]	Tests minimum valid input size
[5,5,5]	Tests zero common difference
[7,3,-1,-5]	Tests negative numbers
[1,1,2]	Tests invalid duplicate handling
[10,0,-10]	Tests rearrangement into progression
[1000000,0,-1000000]	Tests extreme values
[1,4,7,11]	Tests mismatch in differences
[9,7,5,3,1]	Tests reverse ordered input

Edge Cases

Arrays with only two elements

Any array of length 2 automatically forms an arithmetic progression because there is only one difference to consider. A naive implementation might overcomplicate this case or accidentally access out-of-bounds indices. This implementation handles it naturally because the loop starts at index 2, meaning no comparisons are needed beyond computing the initial difference.

Arrays with duplicate numbers

Duplicate values can be tricky because repeated numbers only form an arithmetic progression if the common difference is zero. For example, [5,5,5] is valid, while [1,1,2] is not. After sorting, the implementation simply checks whether all adjacent differences match, which correctly distinguishes valid and invalid duplicate patterns.

Unordered input

The input may arrive in any arbitrary order, such as [3,5,1]. A naive implementation that checks differences without rearranging would incorrectly return false. By sorting first, the implementation guarantees that it evaluates the only meaningful ordered arrangement, ensuring correctness regardless of input order.