Code Implementation

class Solution:
    def canMakeArithmeticProgression(self, arr):
        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
      

class Solution {
public:
    bool canMakeArithmeticProgression(vector<int>& arr) {
        sort(arr.begin(), arr.end());
        int diff = arr[1] - arr[0];
        for (int i = 2; i < arr.size(); ++i) {
            if (arr[i] - arr[i-1] != diff) return false;
        }
        return true;
    }
};
      

import java.util.*;
class Solution {
    public boolean canMakeArithmeticProgression(int[] arr) {
        Arrays.sort(arr);
        int diff = arr[1] - arr[0];
        for (int i = 2; i < arr.length; i++) {
            if (arr[i] - arr[i-1] != diff) return false;
        }
        return true;
    }
}
      

/**
 * @param {number[]} arr
 * @return {boolean}
 */
var canMakeArithmeticProgression = function(arr) {
    arr.sort((a, b) => a - b);
    let diff = arr[1] - arr[0];
    for (let i = 2; i < arr.length; i++) {
        if (arr[i] - arr[i-1] !== diff) return false;
    }
    return true;
};
      

Problem Description

You are given an array of numbers, named arr. Your task is to determine if you can reorder the elements of arr (i.e., arrange them in any order) so that the resulting sequence forms an arithmetic progression.

An arithmetic progression is a sequence where the difference between any two consecutive elements is always the same. For example, [3, 5, 7, 9] is an arithmetic progression with a common difference of 2.

• You can rearrange the elements in any order.
• Each element must be used exactly once; you cannot reuse or skip elements.
• You must decide if at least one valid ordering exists that forms an arithmetic progression.

Thought Process

The first thought might be to try all possible permutations of the array and check if any of them form an arithmetic progression. However, this brute-force approach is inefficient, especially for larger arrays, since the number of permutations grows factorially with the array size.

Instead, let's consider the properties of an arithmetic progression. If we sort the array, then for it to be an arithmetic progression, the difference between each consecutive pair must be the same. This insight allows us to reduce the problem to a simple check after sorting.

By focusing on the sorted version, we avoid the need to try every permutation, and we can check the condition in a single pass.

Solution Approach

To solve this problem efficiently, follow these steps:

1. Sort the array: Sorting arranges the numbers in increasing order. In an arithmetic progression, the difference between consecutive elements must be equal, so sorting puts the numbers in the only order that could possibly work.
2. Find the common difference: After sorting, the common difference is simply the difference between the first two elements.
3. Check all consecutive pairs: Loop through the sorted array and check if the difference between each pair of consecutive elements matches the common difference.
4. Return the result: If all differences match, return true; otherwise, return false.

This approach is efficient because:

• Sorting takes O(n log n) time.
• Checking differences takes O(n) time.
• No extra space is needed beyond the sort (unless the language requires copying).

Example Walkthrough

Let's consider the input arr = [3, 5, 1]:

1. Sort the array: [1, 3, 5]
2. Find the common difference: 3 - 1 = 2
3. Check differences:
   • 3 - 1 = 2 (matches)
   • 5 - 3 = 2 (matches)
4. All differences match the common difference, so return true.

If we try an array like arr = [1, 2, 4]:

• Sorted: [1, 2, 4]
• Common difference: 2 - 1 = 1
• 4 - 2 = 2 (does not match 1)

Since not all differences are equal, return false.

Time and Space Complexity

Brute-force approach:

• Time Complexity: O(n!) due to checking all permutations.
• Space Complexity: O(n) for each permutation being checked.

• Time Complexity: O(n log n) for sorting, plus O(n) for checking differences, so overall O(n log n).
• Space Complexity: O(1) if sorting in place, or O(n) if the sort creates a new array.

The optimized approach is much faster and more practical for larger arrays.

Summary

To determine if an array can form an arithmetic progression, we can sort the array and check if all consecutive differences are the same. This insight allows us to move from a brute-force, inefficient solution to a simple and elegant one that is efficient and easy to implement. The key is recognizing that sorting reveals the only possible order for an arithmetic progression and that the condition can be checked in a single scan.