Code Implementation

class Solution:
    def checkArithmeticSubarrays(self, nums, l, r):
        res = []
        for left, right in zip(l, r):
            sub = nums[left:right+1]
            sub.sort()
            if len(sub) <= 1:
                res.append(True)
                continue
            diff = sub[1] - sub[0]
            is_arith = True
            for i in range(2, len(sub)):
                if sub[i] - sub[i-1] != diff:
                    is_arith = False
                    break
            res.append(is_arith)
        return res
      

class Solution {
public:
    vector<bool> checkArithmeticSubarrays(vector<int>& nums, vector<int>& l, vector<int>& r) {
        vector<bool> res;
        for (int i = 0; i < l.size(); ++i) {
            vector<int> sub(nums.begin() + l[i], nums.begin() + r[i] + 1);
            sort(sub.begin(), sub.end());
            if (sub.size() <= 1) {
                res.push_back(true);
                continue;
            }
            int diff = sub[1] - sub[0];
            bool is_arith = true;
            for (int j = 2; j < sub.size(); ++j) {
                if (sub[j] - sub[j-1] != diff) {
                    is_arith = false;
                    break;
                }
            }
            res.push_back(is_arith);
        }
        return res;
    }
};
      

class Solution {
    public List<Boolean> checkArithmeticSubarrays(int[] nums, int[] l, int[] r) {
        List<Boolean> res = new ArrayList<>();
        for (int i = 0; i < l.length; i++) {
            int left = l[i], right = r[i];
            int[] sub = Arrays.copyOfRange(nums, left, right + 1);
            Arrays.sort(sub);
            if (sub.length <= 1) {
                res.add(true);
                continue;
            }
            int diff = sub[1] - sub[0];
            boolean is_arith = true;
            for (int j = 2; j < sub.length; j++) {
                if (sub[j] - sub[j-1] != diff) {
                    is_arith = false;
                    break;
                }
            }
            res.add(is_arith);
        }
        return res;
    }
}
      

var checkArithmeticSubarrays = function(nums, l, r) {
    const res = [];
    for (let i = 0; i < l.length; i++) {
        let sub = nums.slice(l[i], r[i]+1);
        sub.sort((a, b) => a - b);
        if (sub.length <= 1) {
            res.push(true);
            continue;
        }
        let diff = sub[1] - sub[0];
        let is_arith = true;
        for (let j = 2; j < sub.length; j++) {
            if (sub[j] - sub[j-1] !== diff) {
                is_arith = false;
                break;
            }
        }
        res.push(is_arith);
    }
    return res;
};
      

Problem Description

Given an integer array nums and two integer arrays l and r of the same length, you are to answer several queries. Each query is defined by the indices l[i] and r[i], and asks whether the subarray nums[l[i]], nums[l[i]+1], ..., nums[r[i]] can be rearranged to form an arithmetic sequence (a sequence where the difference between any two consecutive elements is the same).

For each query, return true if the subarray can be rearranged into an arithmetic sequence, or false otherwise.

• Each query is independent.
• Elements are not reused across queries; each subarray is considered separately.
• Constraints: The input arrays can be up to length 500, and values can be up to 10⁵.

Thought Process

The main challenge is to efficiently determine, for each query, if a subarray can be reordered to make an arithmetic sequence. A brute-force approach would be to generate all permutations of the subarray and check which one is arithmetic, but this is highly inefficient.

Instead, we can leverage the property that a sorted arithmetic sequence has a constant difference between consecutive elements. Thus, for each subarray, we can sort it and check if the difference between each pair of adjacent elements is the same.

This reduces the problem from checking all rearrangements to simply sorting and verifying the difference, which is much more efficient.

Solution Approach

• Step 1: For each query, extract the subarray from nums using the indices l[i] and r[i].
• Step 2: Sort the subarray. Sorting brings any potential arithmetic sequence into order, making it easy to check the difference.
• Step 3: If the subarray has 0 or 1 elements, it is trivially arithmetic.
• Step 4: Calculate the difference between the first two elements. Then, iterate through the rest of the sorted subarray and check if the difference between each consecutive pair matches this value.
• Step 5: If all differences match, the subarray can be rearranged into an arithmetic sequence; otherwise, it cannot.
• Step 6: Repeat for all queries and return the results as a list of boolean values.

This approach is efficient because sorting a small subarray is fast (since subarrays are at most length 500), and checking differences is linear in the subarray size.

Example Walkthrough

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

• First query: l[0]=0, r[0]=2 → subarray is [4, 6, 5].
  Sort: [4, 5, 6].
  Differences: 5-4=1, 6-5=1 (all equal).
  Result: true.
• Second query: l[1]=0, r[1]=3 → subarray is [4, 6, 5, 9].
  Sort: [4, 5, 6, 9].
  Differences: 5-4=1, 6-5=1, 9-6=3 (not all equal).
  Result: false.
• Third query: l[2]=2, r[2]=5 → subarray is [5, 9, 3, 7].
  Sort: [3, 5, 7, 9].
  Differences: 5-3=2, 7-5=2, 9-7=2 (all equal).
  Result: true.

The final result is [true, false, true].

Time and Space Complexity

• Brute-force approach: Generating all permutations for each subarray would take O(k!) time per query (where k is the subarray length), which is infeasible for even moderate sizes.
• Optimized approach: For each query, we sort a subarray of length k (O(k log k)), then check differences in O(k). For q queries, the total time is O(q * k log k), where k is the maximum subarray length.
• Space complexity: Each subarray copy uses O(k) space. The result array uses O(q) space for the booleans.

Since both q and k are up to 500, this approach is efficient and practical.

Summary

The key insight is that checking for an arithmetic sequence only requires sorting and verifying constant differences, not generating all permutations. By applying this to each query, we achieve an efficient and elegant solution that leverages basic array operations and simple logic.

This method is both intuitive and optimal for the given constraints, making it a great example of reducing a seemingly complex problem to a manageable one by recognizing underlying mathematical properties.