Arithmetic Subarrays

Problem Statement

In mathematics, a sequence is termed arithmetic if it consists of at least two elements, and the difference between every two consecutive elements is the same throughout the sequence. Given an array of integers called nums, and two additional arrays, l and r, which represent a series of range queries, the task is to determine whether the subarray extracted from nums using the ranges specified by l[i] to r[i] can be rearranged to form an arithmetic sequence.

For each query defined by a pair of indices from l and r, you should return a boolean value indicating if the subarray from nums within that range can be reordered to an arithmetic sequence. The answers to all the queries are to be collected in a boolean array where true signifies that the subarray can indeed be rearranged into an arithmetic sequence, and false otherwise.

Examples

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 0th query, the subarray is [4,6,5]. This can be rearranged as [6,5,4], which is an arithmetic sequence.
In the 1st query, the subarray is [4,6,5,9]. This cannot be rearranged as an arithmetic sequence.
In the 2nd 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]

Constraints

• n == nums.length
• m == l.length
• m == r.length
• 2 <= n <= 500
• 1 <= m <= 500
• 0 <= l[i] < r[i] < n
• -105 <= nums[i] <= 105

Approach and Intuition

1. Understanding Arithmetic Sequences:
   A valid arithmetic sequence has a constant difference, d, between any two consecutive terms. This means that by sorting any section of the array, if it can form a valid arithmetic sequence, it should exhibit this property of constant difference.

2. Approach to Solve the Problem:

   • For each query (l[i], r[i]), extract the subarray from nums.
   • Sort this subarray.
   • Calculate the difference d between the first two elements.
   • Iterate through the sorted subarray and check if the difference between each successive pair of elements remains equal to d.
   • If for any pair it doesn't hold, the sequence can't form an arithmetic sequence upon rearrangement, return false for that query.
   • If it holds for all elements, return true.

3. Using Sample Inputs to Understand the Logic:
   Consider the sample input, where nums = [4,6,5,9,3,7]:

   • Query 0: Subarray is [4,6,5]. When sorted, it becomes [4,5,6], which is an arithmetic sequence with d = 1.
   • Query 1: Subarray is [4,6,5,9]. Sorting gives [4,5,6,9]. The differences here are 1, 1, and 3, which are not consistent. Thus, it is not possible to rearrange it into an arithmetic sequence.
   • Query 2: Subarray from indices 2 to 5 is [5,9,3,7]. Sorting this results in [3,5,7,9], forming a valid arithmetic sequence.

Intuitive Insight:

• The core of the approach lies in rearranging and verifying a consistent pattern (uniform differences). Sorting helps streamline this process by reducing it to a simple comparison of differences between consecutive elements.
• Efficient checks on each subarray post sorting, benefits from the constrained array length, ensuring that the solution remains computationally feasible.

These steps and deliberations encapsulate the proposed solution to determine if subarrays can be rearranged into arithmetic sequences based on given range queries.

Solutions

class Solution {
public:
    bool checkArithmetic(vector<int>& sequence) {
        int smallest = INT_MAX;
        int largest = INT_MIN;
        unordered_set<int> elements;
            
        for (int value : sequence) {
            smallest = min(smallest, value);
            largest = max(largest, value);
            elements.insert(value);
        }
            
        if ((largest - smallest) % (sequence.size() - 1) != 0) {
            return false;
        }
            
        int commonDifference = (largest - smallest) / (sequence.size() - 1);
        int nextTerm = smallest + commonDifference;
            
        while (nextTerm < largest) {
            if (elements.find(nextTerm) == elements.end()) {
                return false;
            }
                
            nextTerm += commonDifference;
        }
            
        return true;
    }
        
    vector<bool> evaluateSubarrays(vector<int>& data, vector<int>& starts, vector<int>& ends) {
        vector<bool> results;
        for (int j = 0; j < starts.size(); j++) {
            vector<int> subarray(begin(data) + starts[j], begin(data) + ends[j] + 1);
            results.push_back(checkArithmetic(subarray));
        }
            
        return results;
    }
};