Can Make Arithmetic Progression From Sequence

• 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.

1import java.util.HashSet;2import java.util.Set;3 4class Solution {5    public boolean canMakeArithmeticProgression(int[] arr) {6        int n = arr.length;7        if (n <= 2) {8            return true;9        }10 11        int minVal = Integer.MAX_VALUE;12        int maxVal = Integer.MIN_VALUE;13        Set<Integer> set = new HashSet<>();14 15        for (int num : arr) {16            minVal = Math.min(minVal, num);17            maxVal = Math.max(maxVal, num);18            set.add(num);19        }20 21        if ((maxVal - minVal) % (n - 1) != 0) {22            return false;23        }24 25        int diff = (maxVal - minVal) / (n - 1);26 27        // If diff is 0, all elements must be the same. 28        // The set size will be 1 if they are.29        if (diff == 0) {30            return set.size() == 1;31        }32 33        // If diff is not 0, all elements must be unique.34        // The set size must be n.35        if (set.size() != n) {36            return false;37        }38 39        for (int i = 0; i < n; i++) {40            if (!set.contains(minVal + i * diff)) {41                return false;42            }43        }44 45        return true;46    }47}

• Find minVal and maxVal in arr.
• If (maxVal - minVal) is not divisible by (n - 1), return false.
• Calculate diff = (maxVal - minVal) / (n - 1).
• If diff == 0, check if all elements are equal. If so, return true, else false.
• Iterate through the array with an index i from 0 to n-1.
• For each arr[i], if it's not at its correct sorted position (arr[i] != minVal + i * diff):
  • Calculate its target index j = (arr[i] - minVal) / diff.
  • Check if arr[i] is a valid AP number: (arr[i] - minVal) % diff == 0. If not, return false.
  • Check for duplicates: if arr[i] == arr[j], return false.
  • Swap arr[i] and arr[j].
  • Repeat the process for the new arr[i] without incrementing i (using an inner while loop).
• If arr[i] is already at its correct position, increment i.
• If the loop completes, return true.

The in-place manipulation method works by treating the array as a direct-mapped hash table.

1. First, just like the HashSet approach, we find the minVal, maxVal, and the potential common difference diff. If the parameters are invalid (e.g., maxVal - minVal is not divisible by n-1), we return false immediately.

2. The core of the algorithm is to place every number x at its correct index. If the array were sorted as an AP, the element x should be at index j such that x = minVal + j * diff. This gives us the target index j = (x - minVal) / diff.

3. We iterate through the array from i = 0 to n-1. For each arr[i], we check if it's already in its correct place. If not, we calculate its target index j. We then swap arr[i] with arr[j]. After the swap, arr[j] is correct, but the new arr[i] might still be in the wrong place. We repeat this swap-and-check process for the current index i until the element arr[i] is correct.

4. During this process, we must handle two failure conditions:

   • Invalid Number: If we encounter a number arr[i] that doesn't fit the AP pattern (i.e., (arr[i] - minVal) % diff != 0), we can immediately return false.
   • Duplicate Number: If we try to swap arr[i] to its target position j, but find that arr[j] already has the same value (arr[i] == arr[j]), it implies a duplicate. Since i != j, this is an invalid state for an AP with a non-zero difference, so we return false.

If we can successfully place every element in its correct position, the array can form an AP.

1class Solution {2    public boolean canMakeArithmeticProgression(int[] arr) {3        int n = arr.length;4        if (n <= 2) {5            return true;6        }7 8        int minVal = Integer.MAX_VALUE;9        int maxVal = Integer.MIN_VALUE;10        for (int num : arr) {11            minVal = Math.min(minVal, num);12            maxVal = Math.max(maxVal, num);13        }14 15        if (maxVal == minVal) {16            return true; // All elements are the same, diff is 0.17        }18 19        if ((maxVal - minVal) % (n - 1) != 0) {20            return false;21        }22 23        int diff = (maxVal - minVal) / (n - 1);24        int i = 0;25        while (i < n) {26            // If element is already in its correct place, move to the next.27            if (arr[i] == minVal + i * diff) {28                i++;29            } else {30                // Check if the number can be part of the AP.31                if ((arr[i] - minVal) % diff != 0) {32                    return false;33                }34 35                int j = (arr[i] - minVal) / diff;36 37                // Check for duplicates. If arr[i] and arr[j] are the same,38                // it means we have a duplicate element because arr[i] is not39                // at its correct place (i != j).40                if (arr[i] == arr[j]) {41                    return false;42                }43 44                // Swap arr[i] with arr[j] to place arr[j] correctly.45                int temp = arr[i];46                arr[i] = arr[j];47                arr[j] = temp;48            }49        }50        return true;51    }52}

• Sort the input array arr in non-decreasing order.
• If the array can form an arithmetic progression, its sorted version must also be an arithmetic progression.
• Calculate the difference between the first two elements, diff = arr[1] - arr[0].
• Iterate from the third element (i = 2) to the end of the array.
• For each element, check if the difference with its preceding element (arr[i] - arr[i-1]) is equal to diff.
• If any difference does not match, it's not an AP, so return false.
• If the loop completes without any mismatches, return true.

This method leverages the property that a sorted arithmetic progression has a constant difference between adjacent elements.

First, we sort the input array arr. This costs O(N log N) time. After sorting, if the original numbers can form an arithmetic progression, the sorted array [a_1, a_2, ..., a_n] must satisfy a_2 - a_1 = a_3 - a_2 = ... = a_n - a_{n-1}.

We can verify this by first calculating the common difference diff using the first two elements: diff = arr[1] - arr[0]. Then, we iterate through the rest of the array (from the third element onwards) and check if the difference between each element and its predecessor is equal to this diff. If we find any pair (arr[i], arr[i-1]) where arr[i] - arr[i-1] != diff, we can immediately conclude that it's not an arithmetic progression and return false. If the entire array is traversed without finding such a discrepancy, it confirms the array can form an arithmetic progression, and we return true.

1import java.util.Arrays;2 3class Solution {4    public boolean canMakeArithmeticProgression(int[] arr) {5        // An array with 2 or fewer elements can always form an AP.6        if (arr.length <= 2) {7            return true;8        }9 10        // Sort the array to check for a constant difference.11        Arrays.sort(arr);12 13        // Calculate the common difference from the first two elements.14        int diff = arr[1] - arr[0];15 16        // Check if the rest of the elements follow the same difference.17        for (int i = 2; i < arr.length; i++) {18            if (arr[i] - arr[i - 1] != diff) {19                return false;20            }21        }22 23        return true;24    }25}