Can Make Arithmetic Progression From Sequence

To improve upon the O(N log N) time complexity of the sorting approach, we can use a HashSet to achieve a linear time solution. The core idea is to determine the parameters of the potential arithmetic progression (first term, last term, and common difference) in O(N) time, and then verify if all the required elements of this progression are present in the input array, also in O(N) time.

• Find the minimum (minVal) and maximum (maxVal) elements in arr.
• Store all unique elements of arr in a HashSet for efficient lookups.
• The common difference of the AP must be d = (maxVal - minVal) / (n - 1). If (maxVal - minVal) is not divisible by (n - 1), return false.
• If d == 0, all elements must be the same. Check if the HashSet size is 1. If not, return false.
• If d != 0, all elements must be unique. Check if the HashSet size is n. If not, return false.
• Iterate from i = 0 to n-1. For each i, check if the expected term minVal + i * d exists in the HashSet.
• If any expected term is missing, return false.
• If all terms are found, return true.

This approach avoids a full sort. Here's the breakdown:

1. Find Parameters: We make one pass through the array to find the minimum (minVal) and maximum (maxVal) elements. We also populate a HashSet with all elements from the input array. The set helps in checking for the existence of elements in O(1) average time and also implicitly handles duplicates.
2. Calculate Difference: For an arithmetic progression of n terms, the difference between the maximum and minimum term is (n-1) * diff. So, we can calculate the potential common difference diff = (maxVal - minVal) / (n - 1). If maxVal - minVal is not perfectly divisible by n - 1, it's impossible to form an AP, so we return false.
3. Handle Duplicates: If diff is 0, it means all elements must be the same. This is a valid AP. We can verify this by checking if the size of our HashSet is 1. If diff is not 0, then all elements in an AP must be distinct. We verify this by checking if the HashSet size is equal to the array length n.
4. Verify Progression: We now know the first term (minVal) and the common difference (diff). The expected terms of the AP are minVal, minVal + diff, minVal + 2*diff, ..., maxVal. We can iterate n times and for each step i, check if minVal + i * diff is present in our HashSet. If any of these checks fail, we return false. If all expected elements are found, we return true.

import java.util.HashSet;
import java.util.Set;

class Solution {
    public boolean canMakeArithmeticProgression(int[] arr) {
        int n = arr.length;
        if (n <= 2) {
            return true;
        }

        int minVal = Integer.MAX_VALUE;
        int maxVal = Integer.MIN_VALUE;
        Set<Integer> set = new HashSet<>();

        for (int num : arr) {
            minVal = Math.min(minVal, num);
            maxVal = Math.max(maxVal, num);
            set.add(num);
        }

        if ((maxVal - minVal) % (n - 1) != 0) {
            return false;
        }

        int diff = (maxVal - minVal) / (n - 1);

        // If diff is 0, all elements must be the same. 
        // The set size will be 1 if they are.
        if (diff == 0) {
            return set.size() == 1;
        }

        // If diff is not 0, all elements must be unique.
        // The set size must be n.
        if (set.size() != n) {
            return false;
        }

        for (int i = 0; i < n; i++) {
            if (!set.contains(minVal + i * diff)) {
                return false;
            }
        }

        return true;
    }
}