Scale Engineer

Arithmetic Subarrays

Med
#1498Time: 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).
Algorithms
Sorting
Data structures
ArrayHash Table

Prompt

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:

[4,6,5,9,3,7]

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

2 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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.
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;    }}

Complexity

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).

Trade-offs

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.

Solutions

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 ; } }

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem