1502. Can Make Arithmetic Progression From Sequence

Can Make Arithmetic Progression From Sequence

Problem Description

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

Approach) Sorting

•    Sort arr
•    Find difference in arr[1]-arr[0]
•    Check arr[i+1]-arr[i]. It is no equal difference, return False. Else, return True.

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

Approach) One Liner

var canMakeArithmeticProgression = function(arr) {
     return arr.sort((a,b) => a-b).every((n, i, arr) => !arr[i + 1] || arr[i + 1] - n === arr[1] - arr[0])
};

Approach) Merge Sort

var canMakeArithmeticProgression = function(arr) {
    function mergeSort(array) {
        if (array.length <= 1) return array
        let mid = Math.floor(array.length/2)
        let left = mergeSort(array.slice(0,mid))
        let right = mergeSort(array.slice(mid))
        return merge(left, right)
    }  
    
    function merge(left, right) {
        let result = []
        while(left.length && right.length) {
            result.push(left[0] < right[0] ? left.shift() : right.shift())
        }
        return result.concat(left, right)
    }
    
    let sortedArr = mergeSort(arr)
    
    let diff = Math.abs(sortedArr[0] - sortedArr[1])
    for (let i = 0; i < sortedArr.length - 1; i++) {
        if (Math.abs(sortedArr[i] - sortedArr[i+1]) !== diff) {
            return false
        }
    }
    
    return true
};

Conclusion

That’s all folks! In this post, we solved LeetCode problem #1502. Can Make Arithmetic Progression From Sequence

I hope you have enjoyed this post. Feel free to share your thoughts on this.

You can find the complete source code on my GitHub repository. If you like what you learn. feel free to fork 🔪 and star ⭐ it.

In this blog, I have tried to collect & present the most important points to consider when improving Data structure and logic, feel free to add, edit, comment, or ask. For more information please reach me here
Happy coding!