Jobs

Interviews

Discussions

Can Make Arithmetic Progression From Sequence

Easy

Amazon

3 views

Topics:

Arrays

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
-10⁶ <= arr[i] <= 10⁶

Try coding it in LeetCode

Can Make Arithmetic Progression From Sequence

Easy

Amazon

3 views

Topics:

Arrays

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
-10⁶ <= arr[i] <= 10⁶

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the expected size range of the input array?
Can the input array contain negative numbers, zero, or floating-point numbers?
Are duplicate numbers allowed in the input array, and if so, how should they be handled?
What should I return if the input array has fewer than 3 elements?
Is the arithmetic progression required to have a non-zero common difference?

Brute Force Solution

Approach

The goal is to see if a list of numbers can be rearranged to form a perfectly spaced number sequence, like 2, 4, 6, 8. The brute force approach tries every possible order of the numbers until a perfect sequence is found or all orders have been checked.

Here's how the algorithm would work step-by-step:

First, consider all possible arrangements of the numbers.
For each arrangement, figure out the difference between the first two numbers.
Then, see if that same difference exists between the second and third number, the third and fourth number, and so on, across the entire arrangement.
If the difference is consistent throughout the entire arrangement, you've found an arithmetic progression and can stop.
If you've tried every possible arrangement and haven't found a consistent difference, then it's not possible to make an arithmetic progression from the original list.

Code Implementation

def can_make_arithmetic_progression_brute_force(numbers):
    import itertools
    
    # Generate all possible permutations of the input numbers.
    for permutation in itertools.permutations(numbers):
        
        # Need at least two numbers to determine a common difference.
        if len(permutation) < 2:
            return True

        common_difference = permutation[1] - permutation[0]
        
        # Check if the common difference holds for the entire sequence.
        is_arithmetic_progression = True

        for index in range(2, len(permutation)):
            if permutation[index] - permutation[index - 1] != common_difference:
                is_arithmetic_progression = False
                break

        # If progression is found, no need to check other permutations.
        if is_arithmetic_progression:
            return True
    
    # If no arithmetic progression was found return false.
    return False

Big(O) Analysis

Time Complexity

O(n * n!) – The provided approach considers all possible arrangements (permutations) of the input sequence of n numbers. Generating all permutations has a time complexity of O(n!). For each permutation, the algorithm iterates through the arrangement to check if it forms an arithmetic progression. Checking for an arithmetic progression involves iterating through the permutation (up to n elements) to verify the consistent difference between adjacent elements, taking O(n) time. Therefore, the overall time complexity is O(n! * n), simplified as O(n * n!).

Space Complexity

O(N!) – The brute force approach described generates all possible permutations of the input array. Generating permutations requires storing these arrangements. In the worst case, the algorithm needs to explore all N! possible arrangements, each of which takes O(N) space to store, although only one is stored at a time. Therefore, the auxiliary space complexity is dominated by the permutation generation, leading to O(N!).

Optimal Solution

Approach

The best way to check if a sequence can form an arithmetic progression is to first put the numbers in order. Once they're sorted, we can quickly check if the difference between each consecutive pair of numbers is the same.

Here's how the algorithm would work step-by-step:

First, arrange the numbers from smallest to largest.
Then, find the difference between the first two numbers in the sorted list.
After that, make sure that the difference between every other pair of consecutive numbers is the same as the first difference we found.
If all the differences are the same, then the original sequence can form an arithmetic progression. If any difference is different, it cannot.

Code Implementation

def can_make_arithmetic_progression(sequence):
    sequence.sort()

    # Need at least two elements to form a progression.
    if len(sequence) < 2:
        return True

    first_difference = sequence[1] - sequence[0]

    # Check if every difference matches the first difference.
    for i in range(2, len(sequence)):
        current_difference = sequence[i] - sequence[i - 1]

        # Arithmetic progression is invalid if differences don't match
        if current_difference != first_difference:
            return False

    return True

Big(O) Analysis

Time Complexity

O(n log n) – The dominant operation is sorting the input sequence of n numbers. Efficient sorting algorithms like merge sort or quicksort have a time complexity of O(n log n). After sorting, we iterate through the sorted sequence to check if the difference between consecutive elements is constant. This iteration takes O(n) time. Since O(n log n) grows faster than O(n) as n increases, the overall time complexity is determined by the sorting step. Therefore, the time complexity is O(n log n).

Space Complexity

O(1) – The provided algorithm sorts the input sequence in-place. After sorting, it calculates the difference between the first two elements and then iterates through the rest of the sorted sequence to check if the differences are consistent. It does not use any auxiliary data structures that scale with the input size N. Thus, the space complexity is constant.

Edge Cases

Case	How to Handle
Null or empty input array	Return true if the input array is null or has fewer than two elements since a single element or no elements inherently forms an arithmetic progression.
Array with only two elements	Return true as any two elements trivially form an arithmetic progression.
Array with all identical values	Return true, as a sequence of identical values has a common difference of 0, forming an arithmetic progression.
Integer overflow when calculating the difference	Use long data type to store the difference to avoid overflow.
Array with negative numbers	The solution should correctly handle negative numbers without any modification, as arithmetic progression works with negative differences as well.
Array contains duplicate values that would result in a misleading 'true' output if not handled correctly	The algorithm needs to count occurrences of each element to make sure there are no more occurrences than expected based on the common difference.
Large input array leading to potential performance issues if not sorted efficiently	Use an efficient sorting algorithm like mergesort or quicksort, which have an average time complexity of O(n log n).
The sequence does not form an arithmetic progression.	The algorithm must return false when, after sorting and computing differences, not all consecutive differences are the same.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the expected size range of the input array?
Can the input array contain negative numbers, zero, or floating-point numbers?
Are duplicate numbers allowed in the input array, and if so, how should they be handled?
What should I return if the input array has fewer than 3 elements?
Is the arithmetic progression required to have a non-zero common difference?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

First, consider all possible arrangements of the numbers.
For each arrangement, figure out the difference between the first two numbers.
Then, see if that same difference exists between the second and third number, the third and fourth number, and so on, across the entire arrangement.
If the difference is consistent throughout the entire arrangement, you've found an arithmetic progression and can stop.
If you've tried every possible arrangement and haven't found a consistent difference, then it's not possible to make an arithmetic progression from the original list.

Code Implementation

def can_make_arithmetic_progression_brute_force(numbers):
    import itertools
    
    # Generate all possible permutations of the input numbers.
    for permutation in itertools.permutations(numbers):
        
        # Need at least two numbers to determine a common difference.
        if len(permutation) < 2:
            return True

        common_difference = permutation[1] - permutation[0]
        
        # Check if the common difference holds for the entire sequence.
        is_arithmetic_progression = True

        for index in range(2, len(permutation)):
            if permutation[index] - permutation[index - 1] != common_difference:
                is_arithmetic_progression = False
                break

        # If progression is found, no need to check other permutations.
        if is_arithmetic_progression:
            return True
    
    # If no arithmetic progression was found return false.
    return False

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

First, arrange the numbers from smallest to largest.
Then, find the difference between the first two numbers in the sorted list.
After that, make sure that the difference between every other pair of consecutive numbers is the same as the first difference we found.
If all the differences are the same, then the original sequence can form an arithmetic progression. If any difference is different, it cannot.

Code Implementation

def can_make_arithmetic_progression(sequence):
    sequence.sort()

    # Need at least two elements to form a progression.
    if len(sequence) < 2:
        return True

    first_difference = sequence[1] - sequence[0]

    # Check if every difference matches the first difference.
    for i in range(2, len(sequence)):
        current_difference = sequence[i] - sequence[i - 1]

        # Arithmetic progression is invalid if differences don't match
        if current_difference != first_difference:
            return False

    return True

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty input array	Return true if the input array is null or has fewer than two elements since a single element or no elements inherently forms an arithmetic progression.
Array with only two elements	Return true as any two elements trivially form an arithmetic progression.
Array with all identical values	Return true, as a sequence of identical values has a common difference of 0, forming an arithmetic progression.
Integer overflow when calculating the difference	Use long data type to store the difference to avoid overflow.
Array with negative numbers	The solution should correctly handle negative numbers without any modification, as arithmetic progression works with negative differences as well.
Array contains duplicate values that would result in a misleading 'true' output if not handled correctly	The algorithm needs to count occurrences of each element to make sure there are no more occurrences than expected based on the common difference.
Large input array leading to potential performance issues if not sorted efficiently	Use an efficient sorting algorithm like mergesort or quicksort, which have an average time complexity of O(n log n).
The sequence does not form an arithmetic progression.	The algorithm must return false when, after sorting and computing differences, not all consecutive differences are the same.