TODO: 1502. Can Make Arithmetic Progression From Sequence

#sorting #array

Problem

Can Make Arithmetic Progression From Sequence - LeetCodeLeetCode

Intuition

Time Complexity

Space Complexity

Solution

Using Sort

class Solution {
    public boolean canMakeArithmeticProgression(int[] arr) {
        // n -> arr.length, number of elements in array
        // Time Complexity: O(n log n)
        // O(n log n)[sorting] + O(n) [traversal] = O(n log n)

        // Space Complexity: O(1), auxillary space. No extra space is used
        // Sort the array in ascending order
        Arrays.sort(arr);

        // Calculate the common difference between consecutive elements
        int diff = arr[1] - arr[0];

        // Check if the remaining elements also have the same difference
        for (int i = 2; i < arr.length; i++) {
            if (arr[i] - arr[i - 1] != diff) {
                // If the difference is not consistent, it's not an arithmetic progression
                return false;
            }
        }

        // If all differences are consistent, it's an arithmetic progression
        return true;
    }
}

Without Sort