1502. Can Make Arithmetic Progression From Sequence

Problem Description

The problem gives us an array of numbers named arr and asks us to determine whether we can rearrange the array's elements to form an arithmetic progression. An arithmetic progression is a sequence of numbers where the difference between any two consecutive numbers is always the same. For example, in the sequence [1, 3, 5, 7], the difference between consecutive elements is 2, which is consistent throughout the sequence, so it is an arithmetic progression. The goal is to return true if the given array can be rearranged to form such a sequence, or false otherwise.

Intuition

The intuition behind the solution is to first sort the array. Sorting the array is a key step because if an arithmetic progression exists, it must be the case that when sorted, the difference between each pair of consecutive elements is consistent. Once the array is sorted, we calculate the common difference, which should be the difference between the first two elements (since the sorted array should now represent an arithmetic progression if one is possible).

After calculating this common difference, we iterate through the array to check if every consecutive pair of elements has this same difference. If at any point we find a pair of elements that do not have the common difference, we can conclude that it is not possible to form an arithmetic progression and should return false. If we successfully iterate through the entire array without finding discrepancies, then the array can indeed form an arithmetic progression and we return true.

The pairwise function utilized in the solution is a Python utility that allows us to iterate through the array in element pairs which simplifies the process of checking the difference between consecutive elements. With all, we check if all pairs have the same difference d, and hence it satisfies the condition of an arithmetic progression.

Learn more about Sorting patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Which of the following is the prefix sum of array [1, 2, 3, 4, 5]?

[1, 2, 3, 4, 5][1, 3, 6, 10, 15][15, 14, 12, 9, 5][5, 4, 3, 2, 1]

I don’t know

Solution Approach

The solution approach leverages a sorting algorithm and a simple iteration pattern to verify the arithmetic progression. Here’s a step-by-step breakdown of the implementation applied in the provided Python code:

Sorting the Array: The first line in the function sorts the array in-place using arr.sort(), which is a built-in Python method that sorts the list ascendingly by default. The sorted array is necessary to easily compare the difference between consecutive elements.
Finding the Common Difference: The variable d is computed as arr[1] - arr[0] i.e., the difference between the first two elements of the sorted array. This difference d is what we expect between every pair of consecutive elements in an arithmetic progression.
Verifying the Arithmetic Progression: The last step is to verify if each consecutive pair of elements in the sorted array has the same difference d. This is done using the expression all(b - a == d for a, b in pairwise(arr)).
The pairwise function is from Python's itertools module (potentially, the grouper pattern could also be used), which is used here to iterate over the array elements in pairs. Each pair of elements (a, b) consists of consecutive elements from the sorted array.
The all function ensures that every element of the provided iterator evaluates to True. It processes the generator expression, which for each pair of elements checks if the difference b - a is equal to d.
If any pair does not satisfy this, all will immediately return False, indicating that the progression cannot be formed. Otherwise, it will return True, confirming that the array is indeed an arithmetic progression.

The elegance of this approach lies in its simplicity and the efficient use of Python's standard libraries to achieve the desired outcome with very few lines of code. Since sorting is the most computationally expensive part of the algorithm, the overall time complexity is O(n log n) where n is the number of elements in the array due to the sorting operation. The verification process has a time complexity of O(n) since it iterates through the sorted elements once. Therefore, the total time complexity remains O(n log n).

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Example Walkthrough

Let's take an example to illustrate the solution approach. Consider the array arr = [9, 5, 1, 3, 7]. Our goal is to check whether we can rearrange this array into an arithmetic progression.

Following the solution approach:

Sorting the Array: We first sort the array, which results in arr = [1, 3, 5, 7, 9].
Finding the Common Difference: We calculate the common difference d as the difference between the first two elements, which is d = arr[1] - arr[0] = 3 - 1 = 2.
Verifying the Arithmetic Progression: We then check if the difference between every consecutive pair of elements is equal to d.
- The difference between the second and the third elements (3 and 5) is 5 - 3 = 2, which is equal to d.
- The difference between the third and the fourth elements (5 and 7) is 7 - 5 = 2, which is again equal to d.
- The difference between the fourth and the fifth elements (7 and 9) is 9 - 7 = 2, which is also equal to d.

Since all pairs have the same difference, which is equal to d, the function all(b - a == d for a, b in pairwise(arr)) would return True.

Therefore, based on the solution approach, we can conclude that it is indeed possible to rearrange the array [9, 5, 1, 3, 7] to form an arithmetic progression [1, 3, 5, 7, 9].

The consistent common difference and the successful run of the all function on pairwise compared elements support the conclusion that arr can be rearranged to form an arithmetic progression, and thus, the final answer is true.

Solution Implementation

1from typing import List
2
3class Solution:
4    def canMakeArithmeticProgression(self, arr: List[int]) -> bool:
5        # Sort the array in non-decreasing order
6        arr.sort()
7      
8        # Calculate the common difference 'd' between the first two elements
9        common_difference = arr[1] - arr[0]
10      
11        # Iterate over the sorted array to check if each pair of successive
12        # elements has the same difference 'd'
13        for i in range(1, len(arr) - 1):
14            # If the difference between the current and next element does not equal
15            # the common difference 'd', the sequence is not an arithmetic progression
16            if arr[i + 1] - arr[i] != common_difference:
17                return False
18      
19        # If all differences are equal, return True (it is an arithmetic progression)
20        return True
21

1class Solution {
2
3    // Function to check if it is possible to form an arithmetic progression
4    public boolean canMakeArithmeticProgression(int[] arr) {
5        // Sort the array in non-decreasing order
6        Arrays.sort(arr);
7      
8        // Find the common difference 'difference' by subtracting the second element by the first element
9        int difference = arr[1] - arr[0];
10      
11        // Iterate through the sorted array starting from the third element
12        for (int i = 2; i < arr.length; ++i) {
13            // Check if the current difference is equal to the common difference 'difference'
14            // If not, return false since it can't form an arithmetic progression
15            if (arr[i] - arr[i - 1] != difference) {
16                return false;
17            }
18        }
19      
20        // If the loop completes without returning false, it means the array can form an arithmetic progression
21        return true;
22    }
23}
24

1#include <vector>   // Include the vector header
2#include <algorithm> // Include the algorithm header for sort
3using namespace std; // Using the standard namespace
4
5class Solution {
6public:
7    bool canMakeArithmeticProgression(vector<int>& arr) {
8        // Sort the array in non-decreasing order
9        sort(arr.begin(), arr.end());
10      
11        // Calculate the common difference 'd' of the first two elements
12        int commonDifference = arr[1] - arr[0];
13      
14        // Iterate through the array starting from the third element
15        for (size_t i = 2; i < arr.size(); i++) {
16            // If the difference between the current and the previous element
17            // is not equal to the common difference 'd', return false
18            if (arr[i] - arr[i - 1] != commonDifference) {
19                return false;
20            }
21        }
22      
23        // If all consecutive elements have the same difference, return true
24        return true;
25    }
26};
27

1// Function to check if the provided array can form an arithmetic progression
2function canMakeArithmeticProgression(arr: number[]): boolean {
3    // Sort the input array in ascending order
4    arr.sort((a, b) => a - b);
5    const lengthOfArray = arr.length; // Store the length of the array
6
7    // Loop through the array starting from the third element
8    for (let i = 2; i < lengthOfArray; i++) {
9        // Calculate the differences between the consecutive elements
10        const firstDifference = arr[i - 1] - arr[i - 2];
11        const secondDifference = arr[i] - arr[i - 1];
12
13        // If the consecutive differences are not equal, return false
14        if (firstDifference !== secondDifference) {
15            return false;
16        }
17    }
18
19    // If all consecutive differences are equal, return true
20    return true;
21}
22

Not Sure What to Study? Take the 2-min Quiz：

Which of these pictures shows the visit order of a depth-first search?

I don’t know

Time and Space Complexity

Time Complexity

The time complexity of the canMakeArithmeticProgression function is determined primarily by the sorting operation. In Python, the default sort function uses an algorithm called Timsort, which has a time complexity of O(n log n), where n is the length of the array.

The subsequent operation consists of iterating through the sorted array to check if every pair of successive elements has the same difference, d. This check uses a generator expression with the all() function combined with pairwise iteration, which is O(n-1) or simply O(n) since it's walking through the array only once.

Thus, the dominating factor here is the sorting, and the overall time complexity of the function is O(n log n).

Space Complexity

For space complexity, the sort operation can be done in-place, but certain implementations may require additional space. Python's Timsort requires O(n) space in the worst case.

The pairwise iteration does create pairs for every two adjacent elements in the array, but since this is done by the generator expression, it doesn't create an additional list in memory, it simply iterates through the existing sorted array yielding one element at a time.

Hence, the space complexity of the function, which is mostly governed by the sorting operation's space requirement, is O(n).

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Overview

Basic Data Structures

Basic Algorithms

Overview

Sorted Array

Implicitly Sorted Array

Advanced

Speedrun

Introduction

DFS on Tree

Binary Search Tree

Advanced

Combinatorial Search

Pruning

Additional States

Aggregation and Memoization

Dedup

Additional Practices

Speedrun

Introduction

BFS on Tree

Introduction

Vanilla BFS

Matrix as Graph

Implicit Graph

Directed Graph / Topological Sort

Weighted Graph

Minimum Spanning Tree

Speedrun

Introduction

Same Direction

Opposite Direction

Sliding Window

Prefix Sum

Cycle Finding

Advanced

Speedrun

Introduction

Top K

Moving Best

Multiple Heaps

Introduction

Grid

Dynamic number of subproblems

Interval

Dual-Sequence

Knapsack

Bitmask

Additional Practices

Disjoint Set Union | Union Find

Trie

Data Structure Design

Segment Tree

Interval

Monotonic Stack

Divide and Conquer

Line Sweep

Tree Traversal without Recursion

Greedy

Math

Matrix

Classics

Concepts

Projects

Amazon OA

Microsoft OA

Google OA

Twitter OA

Editorials

1502. Can Make Arithmetic Progression From Sequence

Problem Description

Intuition

Solution Approach

Example Walkthrough

Solution Implementation

Time and Space Complexity

Time Complexity

Space Complexity

Recommended Readings