Can Make Arithmetic Progression From Sequence

Leetcode Daily Challenge (6th June, 2023)

6 June, 2023

Contributors

Lakshit Chiranjiv Sagar

@lakshit-cs

Problem Statement:-

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.

Link: https://leetcode.com/problems/can-make-arithmetic-progression-from-sequence/description/

Problem Explanation with examples:-

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

Intuition:-

Sorting the array in any order will bring the elements in order. And an AP is always sorted.
So, we sort the array and check if the difference between any two adjacent elements is the same for all the elements.
If the difference between any two adjacent elements is not the same, then the array is not an AP. So, we return False.

Solution:-

We sort the array using the sort() function.
We iterate over the array using a for loop considering 3 elements at a time using the range of the for loop as range(len(arr)-2).
We check if the difference between any two adjacent elements is the same. If not, then we return False.
If the difference between any two adjacent elements is the same, then we return True at the end of the for loop.

Code:-

JAVA Solution

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

Python Solution

class Solution:
    def canMakeArithmeticProgression(self, arr: List[int]) -> bool:
        arr.sort()
        for i in range(len(arr)-2):
            if arr[i+1]-arr[i] != arr[i+2]-arr[i+1]:
                return False
        return True

Complexity Analysis:-

TIME:-

The time complexity is O(n log n), where n is the length of the input array. This is because the code uses Arrays.sort() to sort the array, which has a time complexity of O(n log n). After sorting, it iterates over the array once, performing a constant number of operations for each element.

SPACE:-

The space complexity is O(1). It does not use any additional data structures that scale with the input size. Only a constant amount of space is required to store the variables and perform the sorting.

References:-

Sorting

Connect with me:-

java

python

leetcode

dsa