Leetcode 1502. Can Make Arithmetic Progression From Sequence

Problem Explanation

Given an array of numbers, a sequence is considered an arithmetic progression if the difference between any two consecutive elements is the same throughout the sequence. The task is to determine if the array can be rearranged to form this arithmetic progression.

Through an example, if we take array [3,5,1], this array can be reordered as [1,3,5] or [5,3,1] where the difference between consecutive elements is 2 or -2 respectively. Hence, it can form an arithmetic progression and the output is True.

Let's look at another example with [1,2,4]. There is no possible way to reorder this array to form an arithmetic progression because there's no common difference that applies to all pairs of consecutive numbers. Hence, it cannot form an arithmetic progression and the output is False.

Solution Approach

The solution approach follows these steps:

1. Finding the smallest and largest values in the array.
2. Calculating the difference between the largest and smallest values.
3. If the difference is not divisible by the size of the array, then we cannot arrange it in an arithmetic progression, so we return False.
4. If the difference is zero (all elements are the same), it's an arithmetic progression, so we return True.
5. Otherwise, we try to place each value in the array at its correct position if we were to arrange the terms in the progression. If a value does not fall into a correct position or if a position should be occupied by multiple values, we return False.
6. Lastly, If we've passed all the checks above, we return True, indicating that the array can form an arithmetic progression.

The data structure used here is unordered_set and the algorithm uses hash table pattern.

Python Code

1
2python
3class Solution:
4    def canMakeArithmeticProgression(self, arr):
5        arr.sort()
6        diff = arr[1] - arr[0]
7        for i in range(2, len(arr)):
8            if arr[i] - arr[i-1] != diff:
9                return False
10        return True

Java Code

1
2java
3import java.util.Arrays;
4
5public class Solution {
6    public boolean canMakeArithmeticProgression(int[] arr) {
7        Arrays.sort(arr);
8        int diff = arr[1] - arr[0];
9        for (int i = 2; i < arr.length; i++){
10            if (arr[i] - arr[i-1] != diff)
11                return false;
12        }
13        return true;
14    }
15}

Javascript Code

1
2javascript
3var canMakeArithmeticProgression = function(arr) {
4    arr.sort((a,b) => a-b);
5    let diff = arr[1] - arr[0];
6    for(let i = 2; i < arr.length; i++){
7        if (arr[i] - arr[i-1] != diff)
8            return false;
9    }
10    return true;
11};

C++ Code

1
2c++
3class Solution {
4public:
5    bool canMakeArithmeticProgression(vector<int>& arr) {
6        sort(arr.begin(), arr.end());
7        int diff = arr[1] - arr[0];
8        for(int i=2; i<arr.size(); i++) {
9            if(arr[i]-arr[i-1]!=diff)
10                return false;
11        }
12        return true;
13    }
14};

C# Code

1
2csharp
3public class Solution {
4    public bool CanMakeArithmeticProgression(int[] arr) {
5        Array.Sort(arr);
6        int diff = arr[1] - arr[0];
7        for (int i = 2; i < arr.Length; i++){
8            if (arr[i] - arr[i-1] != diff)
9                return false;
10        }
11        return true;
12    }
13}

In each of these solutions, we first sort the array and calculate the difference between the first two elements. Then we iterate through the remaining elements checking if the difference between consecutive elements is the same as the initial difference. If there is a mismatch, we return false. If we get to the end of the iteration without finding a mismatch, we return true.## Ruby Code

You can solve the problem by a similar algorithm in the Ruby language with the following code:

1
2ruby
3def can_make_arithmetic_progression(arr)
4  arr.sort!
5  diff = arr[1] - arr[0]
6  (2...arr.length).each do |i|
7    return false if arr[i] - arr[i-1] != diff
8  end
9  true
10end

Here, we start by sorting the array using Ruby's built-in sort method. Next, we calculate the difference between the first two elements. After that, we traverse the remaining elements using a Range. For each remaining element, we check if the difference between it and the preceding element is the same as the initial difference. If we find a mismatch, we immediately return false. If we get to the end of the range without finding a mismatch, we return true.

Time Complexity Analysis

The time complexity of these solutions is dominated by the sort operation. For a typical efficient sorting algorithm such as quicksort, heapsort, or mergesort, this is O(n log n), where n is the number of elements in the array. Every other operation (subtraction, comparison, assignment) is O(1) and is done at most n times, so they do not change the overall time complexity.

The space complexity for all these solutions is O(1) - constant, because they only use a few additional variables and do not allocate any data structures that grow with the input size. Note that this does not consider the space used by the function call stack (with recursive sorting algorithms), or by the input array itself.