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.
For each query, extract the subarray defined by the given l and r indices. Sort this subarray to determine if it can be rearranged into an arithmetic sequence. Once sorted, check if the difference between consecutive elements is constant throughout the subarray.
If the difference is consistent, then the subarray can be rearranged to form an arithmetic sequence, otherwise it cannot.
This solution defines a helper function canBeArithmetic which takes an array and checks if it can form an arithmetic sequence after sorting. The main function checkArithmeticSubarrays prepares a subarray for each query, uses the helper function to analyze it, and stores the results.
Time Complexity is O(m * n log n) because for each query, we may sort the subarray (n log n). The space complexity is O(n) for the auxiliary array created for each query.
Rather than sorting, we can try to compute the minimum and maximum of the subarray to figure out the common difference, because in an arithmetic series, the difference between consecutive terms should be consistent. For each candidate difference, check manually if the subarray can be transformed into a complete arithmetic sequence by verifying all expected elements.
This implementation determines if an arithmetic sequence can exist without sorting. It uses the maximum and minimum to calculate the step difference, creates an array to track positions within the expected arithmetic sequence, and checks if all positions are filled correctly. If any position is missing or repeated, it cannot be organized into an arithmetic sequence.
Time Complexity: O(n) per query, where n is the length of the subarray due to linear scans. Space Complexity: O(n) for the boolean array used for tracking.
| Approach | Complexity |
|---|---|
| Sorting and Validating Arithmetic Sequence | Time Complexity is O(m * n log n) because for each query, we may sort the subarray (n log n). The space complexity is O(n) for the auxiliary array created for each query. |
| Mathematical Check Without Sorting | Time Complexity: O(n) per query, where n is the length of the subarray due to linear scans. Space Complexity: O(n) for the boolean array used for tracking. |
| Default Approach | — |
| 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 |
Arithmetic Subarrays | 2 Approaches | Sorting | Without Sorting | Leetcode-1630 • codestorywithMIK • 4,654 views views
Watch 9 more video solutions →Practice Arithmetic Subarrays with our built-in code editor and test cases.
Practice on FleetCode