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] <= 105For 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.
C++
Java
Python
C#
JavaScript
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.
C++
Java
Python
C#
JavaScript
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. |
Count Number of Nice Subarrays - Leetcode 1248 - Python • NeetCodeIO • 18,197 views views
Watch 9 more video solutions →Practice Arithmetic Subarrays with our built-in code editor and test cases.
Practice on FleetCode