# Arithmetic Subarrays
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/arithmetic-subarrays)
Canonical: https://scaleengineer.com/dsa/problems/arithmetic-subarrays
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array, Hash Table
---
## 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 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 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`

# Approaches
## Brute-Force with Sorting
This approach processes each query independently. For each given range `[l, r]`, we extract the corresponding subarray from `nums`. To check if it can form an arithmetic sequence, we can sort it. An array can be rearranged into an arithmetic sequence if and only if its sorted version is an arithmetic sequence. After sorting, we can easily check this property by iterating through the sorted subarray and verifying that the difference between any two consecutive elements is constant.
**Time:** O(m * k log k), where `m` is the number of queries and `k` is the length of the subarray for a query (`r[i] - l[i] + 1`). In the worst case, `k` can be up to `n`, the length of `nums`. So the worst-case time complexity is O(m * n log n). · **Space:** O(k) or O(n) in the worst case. For each query, we create a temporary subarray of size `k = r[i] - l[i] + 1`. The space used by the sorting algorithm also depends on the implementation (e.g., `Arrays.sort` in Java for primitives is mostly in-place, but we are creating a copy first, so space is dominated by the copy).
**Pros:** Conceptually simple and easy to implement.; Directly models the definition of a rearranged arithmetic sequence.
**Cons:** The sorting step for each query makes it less efficient, especially for large subarrays or a high number of queries.
### Explanation
The overall algorithm iterates through each of the `m` queries. For each query `i` with range `[l[i], r[i]]`:
1.  A new array, `subArray`, is created by copying the elements from `nums` in the specified range. The length of this subarray is `k = r[i] - l[i] + 1`.
2.  If `k <= 2`, the subarray can always form an arithmetic sequence, so we consider it `true`.
3.  Otherwise, we sort `subArray` in non-decreasing order.
4.  We calculate the common difference `diff` using the first two elements: `diff = subArray[1] - subArray[0]`.
5.  We then loop from the third element to the end of `subArray`, checking if `subArray[j] - subArray[j-1]` is equal to `diff`.
6.  If we find any pair of consecutive elements with a different difference, we know it's not an arithmetic sequence, and we mark the result for this query as `false`.
7.  If the loop completes without finding any inconsistencies, the subarray is arithmetic, and we mark the result as `true`.
This process is repeated for all queries.
```java
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution {
    public List<Boolean> checkArithmeticSubarrays(int[] nums, int[] l, int[] r) {
        List<Boolean> result = new ArrayList<>();
        for (int i = 0; i < l.length; i++) {
            // Extract the subarray for the current query
            int[] subArray = Arrays.copyOfRange(nums, l[i], r[i] + 1);
            result.add(isArithmetic(subArray));
        }
        return result;
    }

    private boolean isArithmetic(int[] arr) {
        // A sequence with 2 or fewer elements is always arithmetic.
        if (arr.length <= 2) {
            return true;
        }
        
        // Sort the array to check for the arithmetic property.
        Arrays.sort(arr);
        
        // Calculate the common difference from the first two elements.
        int diff = arr[1] - arr[0];
        
        // Check if the rest of the elements follow the same difference.
        for (int i = 2; i < arr.length; i++) {
            if (arr[i] - arr[i - 1] != diff) {
                return false;
            }
        }
        
        return true;
    }
}
```
### Algorithm
- Initialize an empty list `answer` to store the boolean results.
- Loop through each query `i` from `0` to `m-1`.
- For each query, extract the subarray `nums[l[i]...r[i]]` into a temporary array.
- If the array length is 2 or less, it's arithmetic. Add `true` to `answer` and continue to the next query.
- Sort the temporary array in non-decreasing order.
- Calculate the difference `d` between the first two elements of the sorted array.
- Iterate from the third element to the end, checking if the difference between consecutive elements equals `d`.
- If any difference is not equal to `d`, the subarray is not arithmetic. Add `false` to `answer` and break the inner loop to proceed to the next query.
- If the loop finishes without finding any inconsistencies, the subarray is arithmetic. Add `true` to `answer`.
- After checking all queries, return the `answer` list.

## Optimized Approach without Sorting (Using a HashSet)
This approach improves upon the sorting method by avoiding the `O(k log k)` sorting cost for each query. The key insight is that if a set of numbers can form an arithmetic sequence, it must contain specific elements. An arithmetic sequence is uniquely determined by its minimum value, maximum value, and the number of elements. We can calculate the expected common difference `d = (max - min) / (count - 1)`. Then, we can verify if all expected terms (`min`, `min + d`, `min + 2d`, ...) are present in the original subarray. A `HashSet` provides an efficient way to perform these existence checks in average O(1) time.
**Time:** O(m * k), where `m` is the number of queries and `k` is the length of the subarray. In the worst case, `k` is `n`, so the complexity is O(m * n). For each query, we iterate through the subarray a constant number of times (to find min/max, populate the set, and check for elements). · **Space:** O(k) or O(n) in the worst case. The `HashSet` stores up to `k = r[i] - l[i] + 1` unique elements from the subarray.
**Pros:** More efficient than the sorting approach, with a better time complexity.; Avoids the overhead of sorting for each query.
**Cons:** Requires extra space for the `HashSet`, which could be significant for large subarrays.
### Explanation
For each query, instead of sorting, we perform the check in linear time with respect to the subarray length.
1.  First, we iterate through the subarray `nums[l[i]...r[i]]` to find its minimum (`minVal`) and maximum (`maxVal`) elements.
2.  Let the length of the subarray be `k`. An arithmetic sequence requires the difference between the maximum and minimum elements to be perfectly divisible by `k-1`. If `(maxVal - minVal) % (k - 1) != 0`, it's impossible to form such a sequence, so we can immediately determine the result is `false`.
3.  A special case is when `maxVal == minVal`. This means all elements are identical, forming an arithmetic sequence with a difference of 0. We can return `true`.
4.  If the divisibility check passes, we calculate the common difference `d = (maxVal - minVal) / (k - 1)`.
5.  Now we must verify that all `k` terms of the potential arithmetic sequence (`minVal`, `minVal + d`, `minVal + 2*d`, ..., `maxVal`) are actually present. We use a `HashSet` for efficient lookups. We populate the set with all numbers from the subarray.
6.  We iterate from `j = 0` to `k-1` and for each `j`, we check if `minVal + j * d` exists in our `HashSet`.
7.  If any of these expected terms is not found in the set, the subarray cannot form an arithmetic sequence. If all expected terms are found, it can.
```java
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

class Solution {
    public List<Boolean> checkArithmeticSubarrays(int[] nums, int[] l, int[] r) {
        List<Boolean> result = new ArrayList<>();
        for (int i = 0; i < l.length; i++) {
            result.add(isArithmetic(nums, l[i], r[i]));
        }
        return result;
    }

    private boolean isArithmetic(int[] nums, int start, int end) {
        int len = end - start + 1;
        if (len <= 2) {
            return true;
        }

        int minVal = Integer.MAX_VALUE;
        int maxVal = Integer.MIN_VALUE;
        Set<Integer> numSet = new HashSet<>();

        for (int i = start; i <= end; i++) {
            minVal = Math.min(minVal, nums[i]);
            maxVal = Math.max(maxVal, nums[i]);
            numSet.add(nums[i]);
        }

        if (minVal == maxVal) {
            // All elements are the same, which is an arithmetic sequence with diff 0.
            return true;
        }

        if ((maxVal - minVal) % (len - 1) != 0) {
            // The difference between max and min must be divisible by (len - 1)
            return false;
        }

        int diff = (maxVal - minVal) / (len - 1);

        // Check if all expected elements of the arithmetic sequence are present.
        for (int i = 0; i < len; i++) {
            if (!numSet.contains(minVal + i * diff)) {
                return false;
            }
        }

        return true;
    }
}
```
### Algorithm
- Initialize an empty list `answer`.
- Loop through each query `i` from `0` to `m-1`.
- For each query subarray `nums[l[i]...r[i]]`:
  - Find the minimum (`minVal`) and maximum (`maxVal`) elements in the subarray.
  - If `minVal == maxVal`, all elements are equal, so it's an arithmetic sequence. Add `true` to `answer` and continue.
  - Calculate the length `k` of the subarray.
  - Check if `(maxVal - minVal)` is divisible by `(k - 1)`. If not, it cannot be an arithmetic sequence. Add `false` to `answer` and continue.
  - Calculate the expected common difference `d = (maxVal - minVal) / (k - 1)`.
  - Create a `HashSet` and add all elements of the subarray to it.
  - Iterate `j` from `0` to `k-1`. Check if `minVal + j * d` is present in the `HashSet`.
  - If any element is missing, add `false` to `answer` and break the inner loop.
  - If the loop completes, all elements are present. Add `true` to `answer`.
- Return the `answer` list.

# Solutions
### CSharp

```csharp
class Solution { public bool Check ( int [] arr ) { Array . Sort ( arr ); int diff = arr [ 1 ] - arr [ 0 ]; for ( int i = 2 ; i < arr . Length ; i ++) { if ( arr [ i ] - arr [ i - 1 ] != diff ) { return false ; } } return true ; } public IList < bool > CheckArithmeticSubarrays ( int [] nums , int [] l , int [] r ) { List < bool > ans = new List < bool >(); for ( int i = 0 ; i < l . Length ; i ++) { int [] arr = new int [ r [ i ] - l [ i ] + 1 ]; for ( int j = 0 ; j < arr . Length ; j ++) { arr [ j ] = nums [ l [ i ] + j ]; } ans . Add ( Check ( arr )); } return ans ; } }
```

### Java

```java
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 ) { ans . add ( check ( nums , l [ i ], r [ i ])); } return ans ; } private boolean check ( int [] nums , int l , int r ) { Set < Integer > s = new HashSet <>(); int n = r - l + 1 ; int a1 = 1 << 30 , an = - a1 ; for ( int i = l ; i <= r ; ++ i ) { s . add ( nums [ i ]); a1 = Math . min ( a1 , nums [ i ]); an = Math . max ( an , nums [ i ]); } if (( an - a1 ) % ( n - 1 ) != 0 ) { return false ; } int d = ( an - a1 ) / ( n - 1 ); for ( int i = 1 ; i < n ; ++ i ) { if (! s . contains ( a1 + ( i - 1 ) * d )) { return false ; } } return true ; } }
```

### CPP

```cpp
class Solution { public: vector < bool > checkArithmeticSubarrays ( vector < int >& nums , vector < int >& l , vector < int >& r ) { vector < bool > ans ; auto check = []( vector < int >& nums , int l , int r ) { unordered_set < int > s ; int n = r - l + 1 ; int a1 = 1 << 30 , an = - a1 ; for ( int i = l ; i <= r ; ++ i ) { s . insert ( nums [ i ]); a1 = min ( a1 , nums [ i ]); an = max ( an , nums [ i ]); } if (( an - a1 ) % ( n - 1 )) { return false ; } int d = ( an - a1 ) / ( n - 1 ); for ( int i = 1 ; i < n ; ++ i ) { if ( ! s . count ( a1 + ( i - 1 ) * d )) { return false ; } } return true ; }; for ( int i = 0 ; i < l . size (); ++ i ) { ans . push_back ( check ( nums , l [ i ], r [ i ])); } return ans ; } };
```

### Python

```python
class Solution : def checkArithmeticSubarrays ( self , nums : List [ int ], l : List [ int ], r : List [ int ] ) -> List [ bool ]: def check ( nums , l , r ): n = r - l + 1 s = set ( nums [ l : l + n ]) a1 , an = min ( nums [ l : l + n ]), max ( nums [ l : l + n ]) d , mod = divmod ( an - a1 , n - 1 ) return mod == 0 and all (( a1 + ( i - 1 ) * d ) in s for i in range ( 1 , n )) return [ check ( nums , left , right ) for left , right in zip ( l , r )]
```