Arithmetic Sequence Editorial

Practice Problem Link: Arithmetic Sequence | Practice Problem

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

An Arithmetic progression (AP) or arithmetic sequence is a sequence of numbers such that the difference between the consecutive terms is constant. Given an unsorted array, find if it can be reordered to form an arithmetic sequence.

Naive Approach

A simple solution is to find the smallest and the second smallest element in the array and calculate the common difference (D). Then find the i-th smallest element in the array. If at any point, the difference between two consecutive elements is not equal to D return false otherwise return true.

Analysis

• Time Complexity: O(n²)
• Space Complexity: O(1)

Implementation

C++

bool isArithmeticSequence(vector<int> &arr) {
   int n = arr.size();
   if(n == 1) {
       return true;
   }
   int smallest = INT_MAX, secondSmallest = INT_MAX, commonDiff;
   int smallestIndx;
   for (int i = 0; i < n; i++) {
       if (arr[i] < smallest) {
           secondSmallest = smallest;
           smallest = arr[i];
           smallestIndx = i;
       }
       else if(arr[i] < secondSmallest) {
           secondSmallest = arr[i];
       }
   }
   commonDiff = secondSmallest - smallest;
   arr[smallestIndx] = INT_MAX;
   int prevSmallest = smallest;
   for (int i = 1; i < n; i++) {
       int ithSmallest = INT_MAX, ithIndex;
       for (int j = 0; j < n; j++) {
           if(arr[j] < ithSmallest) {
               ithSmallest = arr[j];
               ithIndex = j;
           }
       }
       arr[ithIndex] = INT_MAX;
       if (commonDiff != ithSmallest - prevSmallest) {
           return false;
       }
       prevSmallest = ithSmallest;
   }
   return true;
}

Java

class Solution {
   boolean isArithmeticSequence (int[] arr) {
       int n = arr.length;
       if(n == 1) {
           return true;
       }
       int smallest = Integer.MAX_VALUE; 
       int secondSmallest = Integer.MAX_VALUE, commonDiff;
       int smallestIndx = 0;
       for (int i = 0; i < n; i++) {
           if (arr[i] < smallest) {
               secondSmallest = smallest;
               smallest = arr[i];
               smallestIndx = i;
           }
           else if(arr[i] < secondSmallest) {
               secondSmallest = arr[i];
           }
       }
       commonDiff = secondSmallest - smallest;
       arr[smallestIndx] = Integer.MAX_VALUE;
       int prevSmallest = smallest;
       for (int i = 1; i < n; i++) {
           int ithSmallest = Integer.MAX_VALUE;
           int ithIndex = 0;
           for (int j = 0; j < n; j++) {
               if(arr[j] < ithSmallest) {
                   ithSmallest = arr[j];
                   ithIndex = j;
               }
           }
           arr[ithIndex] = Integer.MAX_VALUE;
           if (commonDiff != ithSmallest - prevSmallest) {
               return false;
           }
           prevSmallest = ithSmallest;
       }
       return true;
   }
}

Optimal Approach

The problem will be much easier after sorting the array as now only the differences between two consecutive elements of the sorted array need to be checked. If at any point two different common difference (D) is encountered return false otherwise return true.

Analysis

• Time Complexity: O(n * log(n))
• Space Complexity: O(1)

Implementation

C++

bool isArithmeticSequence(vector<int> &arr) {
   int n = arr.size();
   if (n == 1) {
       return true;
   }
   sort(arr.begin(), arr.end());
   int commonDiff = arr[1] - arr[0];
   for (int i = 1; i < n; i++) {
       if (arr[i] - arr[i - 1] != commonDiff) {
           return false;
       }
   }
   return true;
}

Java

class Solution {
   boolean isArithmeticSequence (int[] arr) {
       int n = arr.length;
       if (n == 1) {
           return true;
       }
       Arrays.sort(arr);
       int commonDiff = arr[1] - arr[0];
       for (int i = 1; i < n; i++) {
           if (arr[i] - arr[i - 1] != commonDiff) {
               return false;
           }
       }
       return true;
   }
}