# Can Make Arithmetic Progression From Sequence
**Difficulty:** EASY
[External](https://leetcode.com/problems/can-make-arithmetic-progression-from-sequence)
Canonical: https://scaleengineer.com/dsa/problems/can-make-arithmetic-progression-from-sequence
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array
---
## 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`.

**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`
* `-106 <= arr[i] <= 106`

# Approaches
## Sorting
The most straightforward approach is based on the definition of an arithmetic progression. An arithmetic progression is a sequence of numbers such that the difference between the consecutive terms is constant. If an array can be rearranged to form such a progression, then its sorted version must represent that progression (either in increasing or decreasing order). This leads to a simple algorithm: sort the array and then check if the difference between all adjacent elements is the same.
**Time:** O(N log N) · **Space:** O(log N) or O(N)
**Pros:** Very simple to understand and implement.; Robust and easy to debug.
**Cons:** The time complexity of O(N log N) is not optimal for this problem.
### Explanation
This method leverages the property that a sorted arithmetic progression has a constant difference between adjacent elements. 

First, we sort the input array `arr`. This costs `O(N log N)` time. After sorting, if the original numbers can form an arithmetic progression, the sorted array `[a_1, a_2, ..., a_n]` must satisfy `a_2 - a_1 = a_3 - a_2 = ... = a_n - a_{n-1}`.

We can verify this by first calculating the common difference `diff` using the first two elements: `diff = arr[1] - arr[0]`. Then, we iterate through the rest of the array (from the third element onwards) and check if the difference between each element and its predecessor is equal to this `diff`. If we find any pair `(arr[i], arr[i-1])` where `arr[i] - arr[i-1] != diff`, we can immediately conclude that it's not an arithmetic progression and return `false`. If the entire array is traversed without finding such a discrepancy, it confirms the array can form an arithmetic progression, and we return `true`.

```java
import java.util.Arrays;

class Solution {
    public boolean canMakeArithmeticProgression(int[] arr) {
        // An array with 2 or fewer elements can always form an AP.
        if (arr.length <= 2) {
            return true;
        }

        // Sort the array to check for a constant difference.
        Arrays.sort(arr);

        // Calculate the common difference from the first two elements.
        int diff = arr[1] - arr[0];

        // Check if the rest of the elements follow the same difference.
        for (int i = 2; i < arr.length; i++) {
            if (arr[i] - arr[i - 1] != diff) {
                return false;
            }
        }

        return true;
    }
}
```
### Algorithm
- Sort the input array `arr` in non-decreasing order.
- If the array can form an arithmetic progression, its sorted version must also be an arithmetic progression.
- Calculate the difference between the first two elements, `diff = arr[1] - arr[0]`.
- Iterate from the third element (`i = 2`) to the end of the array.
- For each element, check if the difference with its preceding element (`arr[i] - arr[i-1]`) is equal to `diff`.
- If any difference does not match, it's not an AP, so return `false`.
- If the loop completes without any mismatches, return `true`.

## Using a HashSet
To improve upon the `O(N log N)` time complexity of the sorting approach, we can use a `HashSet` to achieve a linear time solution. The core idea is to determine the parameters of the potential arithmetic progression (first term, last term, and common difference) in `O(N)` time, and then verify if all the required elements of this progression are present in the input array, also in `O(N)` time.
**Time:** O(N) · **Space:** O(N)
**Pros:** Achieves optimal O(N) time complexity.; Conceptually clear: determine the expected pattern and then verify its existence.
**Cons:** Requires O(N) extra space for the HashSet, which might be a concern for very large inputs under strict memory constraints.
### Explanation
This approach avoids a full sort. Here's the breakdown:
1.  **Find Parameters**: We make one pass through the array to find the minimum (`minVal`) and maximum (`maxVal`) elements. We also populate a `HashSet` with all elements from the input array. The set helps in checking for the existence of elements in `O(1)` average time and also implicitly handles duplicates.
2.  **Calculate Difference**: For an arithmetic progression of `n` terms, the difference between the maximum and minimum term is `(n-1) * diff`. So, we can calculate the potential common difference `diff = (maxVal - minVal) / (n - 1)`. If `maxVal - minVal` is not perfectly divisible by `n - 1`, it's impossible to form an AP, so we return `false`.
3.  **Handle Duplicates**: If `diff` is 0, it means all elements must be the same. This is a valid AP. We can verify this by checking if the size of our `HashSet` is 1. If `diff` is not 0, then all elements in an AP must be distinct. We verify this by checking if the `HashSet` size is equal to the array length `n`.
4.  **Verify Progression**: We now know the first term (`minVal`) and the common difference (`diff`). The expected terms of the AP are `minVal`, `minVal + diff`, `minVal + 2*diff`, ..., `maxVal`. We can iterate `n` times and for each step `i`, check if `minVal + i * diff` is present in our `HashSet`. If any of these checks fail, we return `false`. If all expected elements are found, we return `true`.

```java
import java.util.HashSet;
import java.util.Set;

class Solution {
    public boolean canMakeArithmeticProgression(int[] arr) {
        int n = arr.length;
        if (n <= 2) {
            return true;
        }

        int minVal = Integer.MAX_VALUE;
        int maxVal = Integer.MIN_VALUE;
        Set<Integer> set = new HashSet<>();

        for (int num : arr) {
            minVal = Math.min(minVal, num);
            maxVal = Math.max(maxVal, num);
            set.add(num);
        }

        if ((maxVal - minVal) % (n - 1) != 0) {
            return false;
        }

        int diff = (maxVal - minVal) / (n - 1);

        // If diff is 0, all elements must be the same. 
        // The set size will be 1 if they are.
        if (diff == 0) {
            return set.size() == 1;
        }

        // If diff is not 0, all elements must be unique.
        // The set size must be n.
        if (set.size() != n) {
            return false;
        }

        for (int i = 0; i < n; i++) {
            if (!set.contains(minVal + i * diff)) {
                return false;
            }
        }

        return true;
    }
}
```
### Algorithm
- Find the minimum (`minVal`) and maximum (`maxVal`) elements in `arr`.
- Store all unique elements of `arr` in a `HashSet` for efficient lookups.
- The common difference of the AP must be `d = (maxVal - minVal) / (n - 1)`. If `(maxVal - minVal)` is not divisible by `(n - 1)`, return `false`.
- If `d == 0`, all elements must be the same. Check if the `HashSet` size is 1. If not, return `false`.
- If `d != 0`, all elements must be unique. Check if the `HashSet` size is `n`. If not, return `false`.
- Iterate from `i = 0` to `n-1`. For each `i`, check if the expected term `minVal + i * d` exists in the `HashSet`.
- If any expected term is missing, return `false`.
- If all terms are found, return `true`.

## In-place Manipulation
This approach provides the most optimal solution with `O(N)` time and `O(1)` space complexity. It avoids both sorting and the use of an auxiliary data structure like a HashSet. The idea is to rearrange the array in-place, such that each element is moved to its correct position in the arithmetic progression. This is similar to the concept of Cycle Sort.
**Time:** O(N) · **Space:** O(1)
**Pros:** Optimal time complexity of O(N).; Optimal space complexity of O(1) as it modifies the array in-place.
**Cons:** More complex to understand and implement correctly.; Modifies the input array, which might not be desirable in all scenarios.
### Explanation
The in-place manipulation method works by treating the array as a direct-mapped hash table. 

1.  First, just like the HashSet approach, we find the `minVal`, `maxVal`, and the potential common difference `diff`. If the parameters are invalid (e.g., `maxVal - minVal` is not divisible by `n-1`), we return `false` immediately.

2.  The core of the algorithm is to place every number `x` at its correct index. If the array were sorted as an AP, the element `x` should be at index `j` such that `x = minVal + j * diff`. This gives us the target index `j = (x - minVal) / diff`.

3.  We iterate through the array from `i = 0` to `n-1`. For each `arr[i]`, we check if it's already in its correct place. If not, we calculate its target index `j`. We then swap `arr[i]` with `arr[j]`. After the swap, `arr[j]` is correct, but the new `arr[i]` might still be in the wrong place. We repeat this swap-and-check process for the current index `i` until the element `arr[i]` is correct.

4.  During this process, we must handle two failure conditions:
    - **Invalid Number**: If we encounter a number `arr[i]` that doesn't fit the AP pattern (i.e., `(arr[i] - minVal) % diff != 0`), we can immediately return `false`.
    - **Duplicate Number**: If we try to swap `arr[i]` to its target position `j`, but find that `arr[j]` already has the same value (`arr[i] == arr[j]`), it implies a duplicate. Since `i != j`, this is an invalid state for an AP with a non-zero difference, so we return `false`.

If we can successfully place every element in its correct position, the array can form an AP.

```java
class Solution {
    public boolean canMakeArithmeticProgression(int[] arr) {
        int n = arr.length;
        if (n <= 2) {
            return true;
        }

        int minVal = Integer.MAX_VALUE;
        int maxVal = Integer.MIN_VALUE;
        for (int num : arr) {
            minVal = Math.min(minVal, num);
            maxVal = Math.max(maxVal, num);
        }

        if (maxVal == minVal) {
            return true; // All elements are the same, diff is 0.
        }

        if ((maxVal - minVal) % (n - 1) != 0) {
            return false;
        }

        int diff = (maxVal - minVal) / (n - 1);
        int i = 0;
        while (i < n) {
            // If element is already in its correct place, move to the next.
            if (arr[i] == minVal + i * diff) {
                i++;
            } else {
                // Check if the number can be part of the AP.
                if ((arr[i] - minVal) % diff != 0) {
                    return false;
                }

                int j = (arr[i] - minVal) / diff;

                // Check for duplicates. If arr[i] and arr[j] are the same,
                // it means we have a duplicate element because arr[i] is not
                // at its correct place (i != j).
                if (arr[i] == arr[j]) {
                    return false;
                }

                // Swap arr[i] with arr[j] to place arr[j] correctly.
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
        return true;
    }
}
```
### Algorithm
- Find `minVal` and `maxVal` in `arr`.
- If `(maxVal - minVal)` is not divisible by `(n - 1)`, return `false`.
- Calculate `diff = (maxVal - minVal) / (n - 1)`.
- If `diff == 0`, check if all elements are equal. If so, return `true`, else `false`.
- Iterate through the array with an index `i` from `0` to `n-1`.
- For each `arr[i]`, if it's not at its correct sorted position (`arr[i] != minVal + i * diff`):
  - Calculate its target index `j = (arr[i] - minVal) / diff`.
  - Check if `arr[i]` is a valid AP number: `(arr[i] - minVal) % diff == 0`. If not, return `false`.
  - Check for duplicates: if `arr[i] == arr[j]`, return `false`.
  - Swap `arr[i]` and `arr[j]`.
  - Repeat the process for the new `arr[i]` without incrementing `i` (using an inner `while` loop).
- If `arr[i]` is already at its correct position, increment `i`.
- If the loop completes, return `true`.

# Solutions
### Java

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

### JavaScript

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

### CPP

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

```

### Python

```python
class Solution : def canMakeArithmeticProgression ( self , arr : List [ int ]) -> bool : arr . sort () d = arr [ 1 ] - arr [ 0 ] return all ( b - a == d for a , b in pairwise ( arr ))
```