Watch 10 video solutions for Arithmetic Subarrays, a medium level problem involving Array, Hash Table, Sorting. This walkthrough by codestorywithMIK has 4,654 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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]. Thiscan 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.lengthm == l.lengthm == r.length2 <= n <= 5001 <= m <= 5000 <= l[i] < r[i] < n-105 <= nums[i] <= 105Problem Overview: You receive an integer array nums and two arrays l and r describing multiple queries. Each query asks whether the subarray nums[l[i]...r[i]] can be rearranged to form an arithmetic sequence. An arithmetic sequence has a constant difference between consecutive elements.
Approach 1: Sorting and Validating Arithmetic Sequence (O(m * k log k) time, O(k) space)
The most direct solution extracts each queried subarray, sorts it, and checks whether adjacent elements share the same difference. After sorting, compute the difference d = arr[1] - arr[0]. Then iterate through the sorted list and verify that arr[i] - arr[i-1] == d for every index. If any difference breaks the pattern, the subarray cannot form an arithmetic progression.
This approach relies on sorting to normalize the order of elements. Without sorting, the numbers may appear in arbitrary order even if they could form a valid sequence when rearranged. Sorting guarantees that valid arithmetic sequences appear with equal adjacent gaps. The method is simple to implement and easy to reason about during interviews. For m queries with average subarray length k, the complexity becomes O(m * k log k).
Approach 2: Mathematical Check Without Sorting (O(m * k) time, O(k) space)
A faster strategy avoids sorting by using arithmetic properties of the sequence. For a valid arithmetic sequence of length k, the difference must be (max - min) / (k - 1). First scan the subarray to compute the minimum and maximum values. If (max - min) is not divisible by (k - 1), forming an arithmetic sequence is impossible.
If the difference is valid, iterate through the elements and check whether each value fits the expected positions: min + i * diff. A hash set or boolean set tracks numbers already seen to detect duplicates. Each element must map exactly to one valid position in the progression. If all positions are filled without conflicts, the subarray forms an arithmetic sequence.
This technique eliminates the sorting step and reduces each query to linear time. It relies on properties of arithmetic sequences rather than ordering. The algorithm mainly uses array scans and constant-time membership checks, making it an efficient approach for multiple queries over the same array.
Recommended for interviews: Start with the sorting solution since it clearly demonstrates the arithmetic progression condition and is easy to implement correctly. After discussing complexity, mention the mathematical check optimization. Interviewers typically expect candidates to recognize that sorting is unnecessary and derive the difference using min and max. Showing both approaches demonstrates solid algorithmic reasoning and optimization skills.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sorting and Validating Arithmetic Sequence | O(m * k log k) | O(k) | Best for clarity and quick implementation during interviews |
| Mathematical Check Without Sorting | O(m * k) | O(k) | Optimal when many queries exist and sorting overhead should be avoided |