Can Make Arithmetic Progression From Sequence - Leetcode Solution

Problem Statement: Given an array of numbers arr. A sequence of numbers is called an arithmetic progression if the difference between any two consecutive elements is the same.

Return true if it is possible to rearrange the elements in arr to form an arithmetic progression, otherwise, return false.

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

Example: 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.

Solution: The first thing we need to do is sort the given array in ascending order because the arithmetic progression formula requires that the elements are sorted. We can simply just sort the given array using the built-in Python function sort() which sorts the elements in ascending order.

Once sorted, we can then iterate through each element except for the first element "arr[0]" because we cannot calculate the difference between "arr[0]" and a non-existing previous element. We calculate the difference between each consecutive element and store it in a set "diffs". If the length of the set "diffs" is greater than 1, then it means the sequence of numbers does not form an arithmetic progression i.e there are more than one differences.

If the length of the set "diffs" is equal to 1, then it means the sequence of numbers forms an arithmetic progression. Hence, we return True. Otherwise, we return False.

Python Code:

def canMakeArithmeticProgression(arr: List[int]) -> bool: arr.sort() # sorting the array in ascending order diffs = set(arr[i] - arr[i-1] for i in range(1, len(arr))) # storing the differences between consecutive elements in a set return True if len(diffs) == 1 else False # checking if the sequence forms an arithmetic progression if True return True else return False

Time Complexity: The time complexity of the above code is O(n log n) because of the sorting operation, which takes O(n log n) time in the worst case. The set operation and the calculation of the difference between each consecutive element takes O(n) time.

Space Complexity: The space complexity of the above code is O(n) because we create a set "diffs" and an iterator of length "n-1".

This solution has a space complexity greater than O(1) which is the optimal space complexity because we are using a set to store the differences between consecutive elements. To get an optimal solution, you need to calculate the difference between consecutive elements on the fly and store only the last calculated difference and compare it with the current difference. If the differences are not equal, then the sequence does not form an arithmetic progression and we return False. If we manage to iterate through the entire array without breaking out of the loop, then it means the sequence forms an arithmetic progression and we return True.

1