Arithmetic Subarrays: Checking Subarrays for Arithmetic Sequences
You are given an array of integers nums and two arrays l and r of equal length. For each query i, you need to determine whether the subarray nums[l[i]..r[i]] can be rearranged into an arithmetic sequence. An arithmetic sequence is one where the difference between consecutive elements is constant.
This is LeetCode 1630: Arithmetic Subarrays, a medium problem that tests your ability to process range queries by extracting, sorting, and validating subarrays.
The problem
Given an array nums and query arrays l and r, return a list of booleans. For the i-th query, check if the subarray from index l[i] to r[i] (inclusive) can be rearranged to form an arithmetic sequence. A sequence of length 1 or 2 is always arithmetic.
Example: nums = [4,6,5,9,3,7], l = [0,0,2], r = [2,3,5] produces [true, false, true].
The first query extracts [4,6,5], which sorts to [4,5,6] with a constant difference of 1. The second query extracts [4,6,5,9], which sorts to [4,5,6,9] with differences 1, 1, 3. Not constant, so false. The third query extracts [5,9,3,7], which sorts to [3,5,7,9] with a constant difference of 2.
The brute force approach
The most natural approach is to handle each query independently: extract the subarray, sort it, and check if every consecutive pair has the same difference.
def checkArithmeticSubarrays(nums, l, r):
result = []
for i in range(len(l)):
sub = sorted(nums[l[i]:r[i] + 1])
if len(sub) <= 2:
result.append(True)
continue
diff = sub[1] - sub[0]
is_arith = all(sub[j] - sub[j - 1] == diff for j in range(2, len(sub)))
result.append(is_arith)
return result
This is actually the clean solution. For each query you copy and sort a subarray of length k, which takes O(k log k). Across all queries, the total work depends on the sum of subarray lengths.
The key insight
Sorting each subarray and checking for a constant difference is the cleanest approach and runs well within the problem's constraints. If you want to avoid sorting, you can use a set-based O(k) check per query: find the min, max, and length, verify that (max - min) is divisible by (length - 1), compute the expected common difference, then confirm every expected value exists in the set. Both approaches work. The sorting approach is easier to implement correctly under pressure.
Step-by-step walkthrough
Let's trace through nums = [4,6,5,9,3,7], l = [0,0,2], r = [2,3,5].
Step 1: Query 0, l=0, r=2. Extract nums[0..2] = [4,6,5].
Sorted: [4,5,6]. Differences: 5-4=1, 6-5=1. Constant difference, so true.
Step 2: Query 1, l=0, r=3. Extract nums[0..3] = [4,6,5,9].
Sorted: [4,5,6,9]. Differences: 1, 1, 3. Not constant, so false.
Step 3: Query 2, l=2, r=5. Extract nums[2..5] = [5,9,3,7].
Sorted: [3,5,7,9]. Differences: 2, 2, 2. Constant difference, so true.
Final result: [true, false, true].
For each query, we extracted the subarray, sorted it, and checked whether all consecutive differences were equal.
Each query follows the same pattern: extract the range, sort it, and check if the differences between consecutive elements are all the same. If the subarray has two or fewer elements, it is automatically arithmetic.
The code
class Solution:
def checkArithmeticSubarrays(self, nums, l, r):
result = []
for i in range(len(l)):
sub = sorted(nums[l[i]:r[i] + 1])
if len(sub) <= 2:
result.append(True)
continue
diff = sub[1] - sub[0]
is_arith = all(sub[j] - sub[j - 1] == diff for j in range(2, len(sub)))
result.append(is_arith)
return result
The outer loop processes each query independently. For each one, sorted(nums[l[i]:r[i] + 1]) creates a sorted copy of the subarray. If the subarray has two or fewer elements, it is always arithmetic. Otherwise, compute the expected common difference from the first two elements, then verify every consecutive pair matches.
The slice nums[l[i]:r[i] + 1] uses r[i] + 1 because Python slices are exclusive on the right. The problem defines the range as inclusive on both ends, so you need the + 1 to include the element at index r[i].
Complexity analysis
| Metric | Value |
|---|---|
| Time | O(q * k log k), where q is the number of queries and k is the average subarray length |
| Space | O(k), for the sorted copy of each subarray |
Each query copies and sorts a subarray of length k, taking O(k log k). The all() check is O(k). Across all queries, the total work is proportional to the sum of all subarray lengths times their logarithms. The space is O(k) for the largest subarray copy at any one time (plus O(q) for the result list).
The building blocks
This problem combines two patterns that CodeBricks drills independently.
Sort and verify a property
Many problems ask you to check whether a collection satisfies some ordering condition. The general pattern: sort the elements, then scan once to verify the property. This same skeleton appears in problems like checking if an array can form an arithmetic progression, validating sorted order, or detecting duplicates.
def sort_and_check(arr, condition):
arr = sorted(arr)
return all(condition(arr[i], arr[i - 1]) for i in range(1, len(arr)))
In Arithmetic Subarrays, the condition is that every consecutive difference equals the first difference. In other problems, the condition might be uniqueness, non-decreasing order, or bounded gaps.
Subarray extraction from range queries
When a problem gives you l and r arrays defining ranges, you process each query by slicing and operating on the subarray:
for i in range(len(l)):
sub = data[l[i]:r[i] + 1]
result.append(process(sub))
This pattern appears in range sum queries, range min/max queries, and any problem where multiple independent ranges need to be evaluated. The key detail is getting the slice boundaries right, especially the inclusive-to-exclusive conversion.
The set-based alternative avoids sorting: put all elements in a set, compute expected_diff = (max_val - min_val) / (length - 1), then check that every expected value min_val + j * expected_diff exists in the set. This runs in O(k) per query but requires careful handling of the case where expected_diff is not an integer (which means the answer is false).
Edge cases
- Subarray of length 1 or 2. Any single element or pair of elements forms an arithmetic sequence. Return true without sorting.
- All elements equal.
[5,5,5,5]has a common difference of 0. The sorting and difference check handles this naturally. - Negative numbers.
[-3,-1,1,3]has a common difference of 2. Sorting and subtraction work correctly with negatives. - Two elements with large gap.
[1, 1000000]is arithmetic with difference 999999. No special handling needed. - Nearly arithmetic.
[1,3,5,8]has differences 2, 2, 3. The check correctly returns false on the last pair. - Single query spanning the entire array.
l=[0],r=[n-1]is just one large subarray to sort and check.
From understanding to recall
The sort-and-check approach for arithmetic subarrays is simple to understand: extract, sort, verify constant differences. Three steps. But under interview pressure, small mistakes creep in. You might forget the + 1 on the slice, skip the length check for short subarrays, or compute the difference from the wrong pair of elements.
Spaced repetition helps you internalize these details. You practice writing the loop from scratch at increasing intervals until the slice boundaries, the base case for short subarrays, and the difference-check loop all come out correctly without hesitation.
The sort-and-verify pattern and the range-query extraction pattern are two of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Learning them individually and drilling them with spaced repetition is far more effective than solving random problems and hoping they stick.
Related posts
- Arithmetic Slices - Counting contiguous arithmetic subarrays in a single pass
- Sort an Array - The sorting foundation that this problem relies on
- Can Make Arithmetic Progression From Sequence - Checking a single array for arithmetic progression
CodeBricks breaks the arithmetic subarrays problem into its sort-and-verify and range-query building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a range query problem shows up in your interview, you do not think about it. You just write it.