Arithmetic Subarrays Interview Question for Amazon

A sequence of numbers is called arithmetic if it consists of at least two elements, and the difference between every two consecutive elements is the same. More formally, a sequence s is arithmetic if and only if s[i+1] - s[i] == s[1] - s[0] for all valid i.

For example, these are arithmetic sequences:

1, 3, 5, 7, 9
7, 7, 7, 7
3, -1, -5, -9

The following sequence is not arithmetic:

1, 1, 2, 5, 7

You are given an array of n integers, nums, and two arrays of m integers each, l and r, representing the m range queries, where the i<sup>th</sup> query is the range [l[i], r[i]]. All the arrays are 0-indexed.

Return a list of boolean elements answer, where answer[i] is true if the subarray nums[l[i]], nums[l[i]+1], ... , nums[r[i]]* can be rearranged to form an arithmetic sequence, and* false otherwise.

Example 1:

Input: nums = `[4,6,5,9,3,7]`, l = `[0,0,2]`, r = `[2,3,5]`
Output: `[true,false,true]`
Explanation:
In the 0<sup>th</sup> query, the subarray is [4,6,5]. This can be rearranged as [6,5,4], which is an arithmetic sequence.
In the 1<sup>st</sup> query, the subarray is [4,6,5,9]. This cannot be rearranged as an arithmetic sequence.
In the 2<sup>nd</sup> query, the subarray is `[5,9,3,7]. This` can be rearranged as `[3,5,7,9]`, which is an arithmetic sequence.

Example 2:

Input: nums = [-12,-9,-3,-12,-6,15,20,-25,-20,-15,-10], l = [0,1,6,4,8,7], r = [4,4,9,7,9,10]
Output: [false,true,false,false,true,true]

## Problem: Arithmetic Subarrays

Given an array `nums` of `n` integers, and two arrays `l` and `r` of `m` integers each, representing `m` range queries, where the `i`-th query is the range `[l[i], r[i]]`. Return a list of boolean elements `answer`, where `answer[i]` is `true` if the subarray `nums[l[i]], nums[l[i]+1], ..., nums[r[i]]` can be rearranged to form an arithmetic sequence, and `false` otherwise.

An arithmetic sequence consists of at least two elements, and the difference between every two consecutive elements is the same.

**Example:**

`nums = [4, 6, 5, 9, 3, 7], l = [0, 0, 2], r = [2, 3, 5]`

Output: `[true, false, true]`

Brute Force Solution

The brute-force solution involves iterating through each query, extracting the subarray, sorting it, and then checking if the sorted subarray forms an arithmetic sequence.

def is_arithmetic(arr):
    if len(arr) < 2:
        return False
    diff = arr[1] - arr[0]
    for i in range(2, len(arr)):
        if arr[i] - arr[i-1] != diff:
            return False
    return True

def solve_brute_force(nums, l, r):
    result = []
    for i in range(len(l)):
        sub_array = nums[l[i]:r[i]+1]
        sub_array.sort()
        result.append(is_arithmetic(sub_array))
    return result

Optimal Solution

Instead of sorting the subarray each time, we can find the minimum and maximum values, and check if the difference between them is divisible by len(subarray) - 1. We can also use a set to check for duplicate numbers in the subarray. This avoids sorting and improves efficiency.

def solve_optimal(nums, l, r):
    result = []
    for i in range(len(l)):
        start = l[i]
        end = r[i]
        sub_array = nums[start:end+1]
        
        if len(sub_array) <= 1:
            result.append(False)
            continue

        min_val = min(sub_array)
        max_val = max(sub_array)
        
        if min_val == max_val:
          result.append(len(set(sub_array)) <= 1)
          continue

        if (max_val - min_val) % (len(sub_array) - 1) != 0:
            result.append(False)
            continue

        diff = (max_val - min_val) // (len(sub_array) - 1)

        if diff == 0:
            result.append(len(set(sub_array)) <= 1)
            continue

        seen = set()
        is_arithmetic = True
        for num in sub_array:
            if (num - min_val) % diff != 0:
                is_arithmetic = False
                break
            if num in seen:
                is_arithmetic = False
                break
            seen.add(num)

        result.append(is_arithmetic)
    return result

Big(O) Runtime Analysis

Brute Force:

For each query, we extract a subarray of size k = r[i] - l[i] + 1. This takes O(k) time.
Sorting the subarray takes O(k log k) time.
Checking if the sorted array is arithmetic takes O(k) time.
Since we have m queries, the overall time complexity is O(m * k log k).

Optimal Solution:

For each query, we extract a subarray of size k = r[i] - l[i] + 1. This takes O(k) time.
Finding the minimum and maximum values takes O(k) time.
Checking for duplicates using a set and verifying the arithmetic property takes O(k) time.
Since we have m queries, the overall time complexity is O(m * k).

Big(O) Space Usage Analysis

Brute Force:

We create a subarray of size k for each query, which takes O(k) space.
The sorting algorithm might take O(k) space in the worst case.
Therefore, the overall space complexity is O(k).

Optimal Solution:

We create a subarray of size k for each query, which takes O(k) space.
The set to track seen numbers takes O(k) space in the worst case.
Therefore, the overall space complexity is O(k).

Edge Cases

Empty Subarray: If l[i] == r[i] and nums has only one element in that range, then the subarray has only one element and it is not considered arithmetic. Return false.
Subarray with same elements: If the subarray contains the same elements, it forms an arithmetic sequence with a common difference of 0. For example, [7, 7, 7, 7]. In this case, return true.
Subarray with two elements: The most basic arithmetic sequence is of length 2. For example, [1, 2] is an arithmetic sequence.
Zero Difference: Handle cases where the common difference is zero (all elements are same). The optimal code covers this edge case.
Large differences: If the difference between min and max is very large compared to number of elements in sub array, it can lead to integer overflow, but python handles these types of overflows automatically.