Teaching Kids Programming – Arithmetic Sequence Permutation

Teaching Kids Programming: Videos on Data Structures and Algorithms

Given a list of integers nums, return whether you can rearrange the order of nums such that the difference between every consecutive two numbers is the same.

Constraints
n ≤ 100,000 where n is the length of nums
Example 1
Input
nums = [7, 1, 5, 3]
Output
True
Explanation
If we rearrange nums to [1, 3, 5, 7], then the difference between every two consecutive numbers is 2.

Example 2
Input
nums = [1, 5, 1, 5, 1, 5]
Output
False
Explanation
The difference between every consecutive two numbers alternates between 4 and -4.

Algorithm to Check Arithmetic Sequence

We can sort the numbers, and then check if the distance between any two neighbouring numbers is the same. For a Arithmetic Sequence, the subtraction between any number and its previous number is the same. We can push all distances into a set and return False once the set contains more than 1 value. Due to early break, the space complexity is O(1) constant.

1
2
3
4
5
6
7
8
9

class Solution:
    def arithmeticSequencePermutation(self, nums):
        nums.sort()
        d = set()
        for i in range(1, len(nums)):
            d.add(nums[i] - nums[i - 1])
            if len(d) > 1:
                return False
        return True

class Solution:
    def arithmeticSequencePermutation(self, nums):
        nums.sort()
        d = set()
        for i in range(1, len(nums)):
            d.add(nums[i] - nums[i - 1])
            if len(d) > 1:
                return False
        return True

We can also check at the end if the set contains only 1 element – Time complexity O(NlogN), space complexity O(N).

1
2
3
4
5
6
7

class Solution:
    def arithmeticSequencePermutation(self, nums):
        nums.sort()
        d = set()
        for i in range(1, len(nums)):
            d.add(nums[i] - nums[i - 1])
        return len(d) == 1

class Solution:
    def arithmeticSequencePermutation(self, nums):
        nums.sort()
        d = set()
        for i in range(1, len(nums)):
            d.add(nums[i] - nums[i - 1])
        return len(d) == 1

The distance can be computed by the first two numbers, and thus we can use this value to check all other gaps between other neighbouring numbers. The space complexity is O(1) constant.

1
2
3
4
5
6
7

class Solution:
    def arithmeticSequencePermutation(self, nums):
        nums.sort()
        for i in range(1, len(nums)):
            if nums[i] - nums[i - 1] != nums[1] - nums[0]:
                return False
        return True

class Solution:
    def arithmeticSequencePermutation(self, nums):
        nums.sort()
        for i in range(1, len(nums)):
            if nums[i] - nums[i - 1] != nums[1] - nums[0]:
                return False
        return True

All approaches are O(NLogN) time complexity due to sorting.

–EOF (The Ultimate Computing & Technology Blog) —