Beyond Sorting: A mathematical O(n) Solution to Arithmetic Progression

#tutorial #typescript #datascience #algorithms

Leetcode's daily challenges can be extremely difficult at times, yet surprisingly simple at others, however even the straightforward problems offer food for thought - which is precisely why I am writing this article 🥺

But personally, I still think the most straightforward and "standard" solution to this problem is to sort the array first and then check whether it is an arithmetic progression or not.

However, if we can still achieve O(n) solution w/o sorting, I believe it would be a better approach.

Question: 1502. Can Make Arithmetic Progression From Sequence

Description:

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.

Intuition

First of all, let's recall the definition and some basic properties of an arithmetic progression:

The sum of an arithmetic sequence with $n$ elements

S_n = \frac{1}{2}n (2a + (n - 1)d)

The general formula for an arithmetic sequence:

u_n = a + (n - 1)d

Note that: $a$ is the first term, $d$ is the common diff., $n$ is the index.

So for any valid arithmetic sequence, every element must satisfy this formula.

And this leads to a natural idea:

Why not covert the original array into a Set, and check whether every expected value exists in that set?

Refine our validation logic:

The diff between the maximum and minimum values must be divisible by n, where n = arr.length - 1. This is because we need n identical steps (i.e. common diff.) to connect min and max, for example [1(d1)3(d2)5], there is exactly two diffs.
If max == min, then all elements are the same (e.g. [0,0,0,0]), which is trivially an arithmetic progression, we can directly return true.

Approach:

The core steps of the solution are:

Find the max and min vals in the array.
Check whether (max - min) is divisible by n.
Compute the common diff.
Convert the array into a set (or this might be the first step).
Verify that every expected value: $\text{min} + i \times d$ exists in the set. And if any val is missing, return false immediately.

Complexity:

Time Complexity:

Finding min and max: O(n)
Building the set: O(n)
Iterating through expected values: O(n). Overall, O(n).

Space Complexity:

Since an extra set is created to store the els, overall space complexity is O(n)

Code:

Note: in the following code, n = arr.length, and that's why n - 1 is required.

function canMakeArithmeticProgression(arr: number[]): boolean {.

    let n: number = arr.length

    let max: number = Math.max(...arr)
    let min: number = Math.min(...arr)

    if ((max - min) % (n - 1) !== 0){
        return false
    }

    if (max === min){
        return true
    }

    let diff: number = Math.floor((max - min) / (n - 1))

    let tmp =  new Set<number>(arr)

    for (let i = 0; i < n; i++){
        let expected: number = min + i * diff
        if (!tmp.has(expected)){
            return false
        }
    }
    return true
// InkkaPlum https://dev.to/slumhee