Solution Explanation for LeetCode 1502: Can Make Arithmetic Progression From Sequence

This problem asks whether a given array of numbers can be rearranged to form an arithmetic progression (AP). An AP is a sequence where the difference between consecutive terms is constant.

There are two main approaches to solve this problem:

Approach 1: Sorting and Checking

This approach leverages the fact that if an AP can be formed, sorting the array will reveal the constant difference. After sorting, we simply check if the difference between consecutive elements remains constant throughout the array.

Algorithm:

1. Sort the array: Sort the input array arr in ascending order. This ensures that if an AP is possible, the elements will be arranged in the correct order.

2. Calculate the common difference: Find the difference between the first two elements (after sorting). This is the potential common difference d.

3. Check for consistency: Iterate through the sorted array, verifying that the difference between each consecutive pair of elements is equal to d. If a discrepancy is found, the array cannot form an AP, and we return false.

4. Return true: If the loop completes without finding any inconsistencies, it means the array can be rearranged to form an AP, and we return true.

Time Complexity: O(n log n) due to the sorting step. The rest of the algorithm is O(n). Space Complexity: O(log n) or O(1) depending on the sorting algorithm used (in-place sorting algorithms like quicksort have O(log n) space complexity in average cases and O(n) in the worst case, while merge sort has O(n) space complexity).

Approach 2: Hash Table and Mathematics

This approach uses a more mathematical approach combined with a hash table (or set) for efficient lookups.

Algorithm:

1. Find min and max: Determine the minimum (a) and maximum (b) values in the array.

2. Check for possible common difference: If the array can form an AP, the common difference (d) must be an integer and calculated as (b - a) / (n - 1), where n is the array's length. If this division results in a non-integer value, it's impossible to form an AP, and we return false.

3. Use a hash table: Create a hash table (or set) to store the elements of the array for fast lookups.

4. Check for all elements: Iterate from a to b with increments of d, checking if each element (a + d * i) exists in the hash table. If any element is missing, an AP is not possible, and we return false.

5. Return true: If all elements are found, an AP can be formed, and we return true.

Time Complexity: O(n) because we iterate through the array once to find min/max, create the hash table, and then iterate again. Hash table operations (insertion and lookup) are typically O(1) on average. Space Complexity: O(n) to store the hash table.

Code Examples (Python):

Approach 1 (Sorting):

from itertools import pairwise
 
def canMakeArithmeticProgression(arr):
    arr.sort()
    d = arr[1] - arr[0]
    return all(b - a == d for a, b in pairwise(arr))
 

Approach 2 (Hash Table):

def canMakeArithmeticProgression(arr):
    a = min(arr)
    b = max(arr)
    n = len(arr)
    if (b - a) % (n - 1):
        return False
    d = (b - a) // (n - 1)
    s = set(arr)
    return all(a + d * i in s for i in range(n))
 

Both approaches provide correct solutions. Choose the approach that best suits your needs based on the expected input size and performance requirements. For very large arrays, the O(n) time complexity of the hash table approach might be significantly faster than the O(n log n) sorting approach. However, the constant factors in the time complexity might affect the performance for smaller arrays.