Problem

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 ith query is the range [l[i], r[i]]. All the arrays are 0-indexed.

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

Examples

Example 1

1
2
3
4
5
6

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

1
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
  • -10^5 <= nums[i] <= 10^5

Solution

Method 1 – Sorting and Checking Differences

Intuition

The key idea is that a sequence can be rearranged into an arithmetic sequence if, after sorting, the difference between every two consecutive elements is the same. For each query, we extract the subarray, sort it, and check if all consecutive differences are equal.

Approach

  1. Initialize an empty list ans to store the results.
  2. For each query, extract the subarray from nums using the indices from l[i] to r[i].
  3. Sort the subarray.
  4. Compute the difference between the first two elements.
  5. Iterate through the sorted subarray and check if every consecutive pair has the same difference.
  6. If all differences are equal, append true to ans; otherwise, append false.
  7. Return ans after processing all queries.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
public:
    vector<bool> checkArithmeticSubarrays(vector<int>& nums, vector<int>& l, vector<int>& r) {
        vector<bool> ans;
        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());
            int d = sub[1] - sub[0];
            bool ok = true;
            for (int j = 2; j < sub.size(); ++j) {
                if (sub[j] - sub[j - 1] != d) {
                    ok = false;
                    break;
                }
            }
            ans.push_back(ok);
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
    public List<Boolean> checkArithmeticSubarrays(int[] nums, int[] l, int[] r) {
        List<Boolean> ans = new ArrayList<>();
        for (int i = 0; i < l.length; i++) {
            int start = l[i], end = r[i];
            int[] sub = Arrays.copyOfRange(nums, start, end + 1);
            Arrays.sort(sub);
            int d = sub[1] - sub[0];
            boolean ok = true;
            for (int j = 2; j < sub.length; j++) {
                if (sub[j] - sub[j - 1] != d) {
                    ok = false;
                    break;
                }
            }
            ans.add(ok);
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution:
    def checkArithmeticSubarrays(self, nums: list[int], l: list[int], r: list[int]) -> list[bool]:
        ans: list[bool] = []
        for i in range(len(l)):
            sub = nums[l[i]:r[i]+1]
            sub.sort()
            d = sub[1] - sub[0]
            ok = all(sub[j] - sub[j-1] == d for j in range(2, len(sub)))
            ans.append(ok)
        return ans

Complexity

  • ⏰ Time complexity: O(m * k log k), where m is the number of queries and k is the maximum length of a subarray (since we sort each subarray).
  • 🧺 Space complexity: O(k) per query for the subarray copy.