Problem Description

You are given an array nums and need to check if specific subarrays can be rearranged to form arithmetic sequences.

An arithmetic sequence is a sequence of at least two numbers where the difference between every two consecutive elements is the same. For example:

• 1, 3, 5, 7, 9 is arithmetic (difference = 2)
• 7, 7, 7, 7 is arithmetic (difference = 0)
• 3, -1, -5, -9 is arithmetic (difference = -4)
• 1, 1, 2, 5, 7 is NOT arithmetic (differences vary)

You receive:

• An array nums of n integers
• Two arrays l and r, each containing m integers, representing m queries
• Each query i asks about the subarray from index l[i] to index r[i] (inclusive)

For each query, you need to determine if the elements in the subarray nums[l[i]] to nums[r[i]] can be rearranged (reordered in any way) to form an arithmetic sequence.

Return a list of boolean values where answer[i] is true if the i-th query's subarray can form an arithmetic sequence after rearrangement, and false otherwise.

The key insight is that a set of numbers can form an arithmetic sequence if and only if:

1. When sorted, they form an arithmetic sequence
2. The common difference d can be calculated as (max - min) / (count - 1)
3. All intermediate values with this common difference must exist in the set

The solution checks this by:

• Finding the minimum and maximum values in the subarray
• Calculating what the common difference would need to be
• Verifying that all expected values in the arithmetic sequence exist in the subarray

Intuition

When we need to check if a set of numbers can be rearranged into an arithmetic sequence, we don't actually need to sort them. Instead, we can think about what properties an arithmetic sequence must have.

If we have numbers that form an arithmetic sequence, they must be evenly spaced. Imagine plotting them on a number line - they would appear at regular intervals. This means:

1. The smallest and largest numbers determine the "endpoints" of our sequence
2. The common difference between consecutive terms must be (max - min) / (number_of_terms - 1)
3. Every intermediate value must exist - there can't be any "gaps"

For example, if we have the subarray [3, 9, 5, 7]:

• Minimum = 3, Maximum = 9
• We have 4 numbers, so we need 3 gaps between them
• Common difference must be (9 - 3) / 3 = 2
• The arithmetic sequence would be: 3, 5, 7, 9
• We check: do we have 3? Yes. Do we have 5? Yes. Do we have 7? Yes. Do we have 9? Yes.
• Therefore, this can form an arithmetic sequence

The clever part is using a set for O(1) lookup time. We don't need to sort the array; we just need to verify that all the expected values exist. If the common difference doesn't divide evenly (mod != 0), or if any expected value is missing from our set, then we can't form an arithmetic sequence.

This approach is efficient because we only need to:

• Find min and max (O(n) time)
• Calculate the expected common difference
• Check if all required values exist (O(n) checks with O(1) lookup each)

Learn more about Sorting patterns.

Solution Approach

The solution implements a helper function check that verifies if a subarray can form an arithmetic sequence:

1. Extract the subarray and calculate its length:

   • n = r - l + 1 gives us the number of elements in the subarray
   • We slice the array from index l to l + n to get our working subarray

2. Create a set for O(1) lookups:

   • s = set(nums[l : l + n]) converts the subarray into a set
   • This allows us to quickly check if a value exists in our subarray

3. Find the minimum and maximum values:

   • a1 = min(nums[l : l + n]) - the smallest value (first term if sorted)
   • an = max(nums[l : l + n]) - the largest value (last term if sorted)

4. Calculate the common difference:

   • Use divmod(an - a1, n - 1) to get both quotient and remainder
   • d is the common difference (quotient)
   • mod is the remainder - if it's not 0, we can't form an arithmetic sequence

5. Verify all required values exist:

   • If mod == 0, we check if all values in the arithmetic sequence are present
   • The arithmetic sequence would be: a1, a1 + d, a1 + 2d, ..., a1 + (n-1)d
   • We verify each term using: (a1 + (i - 1) * d) in s for i from 1 to n-1
   • The all() function returns True only if every expected value exists in the set

6. Process all queries:

   • Use list comprehension to apply the check function to each query
   • zip(l, r) pairs up corresponding left and right indices
   • Return a list of boolean results

The time complexity for each query is O(n) where n is the length of the subarray (for creating the set and finding min/max). The space complexity is O(n) for storing the set.

Example Walkthrough

Let's walk through the solution with a concrete example:

Input:

• nums = [4, 6, 5, 9, 3, 7, 2]
• l = [0, 2, 1]
• r = [2, 5, 4]

We need to check 3 queries about different subarrays.

Query 1: Check subarray from index 0 to 2

• Subarray: nums[0:3] = [4, 6, 5]
• Create set: s = {4, 5, 6}
• Find min and max: a1 = 4, an = 6
• Calculate common difference:
  • divmod(6 - 4, 3 - 1) = divmod(2, 2) = (1, 0)
  • d = 1, mod = 0 (remainder is 0, good!)
• Check if all values exist:
  • Need: 4 (a1) → ✓ in set
  • Need: 5 (a1 + d) → ✓ in set
  • Need: 6 (a1 + 2d) → ✓ in set
• Result: True (can form arithmetic sequence: 4, 5, 6)

Query 2: Check subarray from index 2 to 5

• Subarray: nums[2:6] = [5, 9, 3, 7]
• Create set: s = {3, 5, 7, 9}
• Find min and max: a1 = 3, an = 9
• Calculate common difference:
  • divmod(9 - 3, 4 - 1) = divmod(6, 3) = (2, 0)
  • d = 2, mod = 0 (remainder is 0, good!)
• Check if all values exist:
  • Need: 3 (a1) → ✓ in set
  • Need: 5 (a1 + d) → ✓ in set
  • Need: 7 (a1 + 2d) → ✓ in set
  • Need: 9 (a1 + 3d) → ✓ in set
• Result: True (can form arithmetic sequence: 3, 5, 7, 9)

Query 3: Check subarray from index 1 to 4

• Subarray: nums[1:5] = [6, 5, 9, 3]
• Create set: s = {3, 5, 6, 9}
• Find min and max: a1 = 3, an = 9
• Calculate common difference:
  • divmod(9 - 3, 4 - 1) = divmod(6, 3) = (2, 0)
  • d = 2, mod = 0 (remainder is 0, good!)
• Check if all values exist:
  • Need: 3 (a1) → ✓ in set
  • Need: 5 (a1 + d) → ✓ in set
  • Need: 7 (a1 + 2d) → ✗ NOT in set!
  • Need: 9 (a1 + 3d) → ✓ in set
• Result: False (missing value 7, cannot form arithmetic sequence)

Final Output: [True, True, False]

The key insight is that we never actually rearrange the arrays - we just check if the required values for an arithmetic sequence exist in our subarray. If they do, we know a valid rearrangement is possible.

Solution Implementation

Time and Space Complexity

Time Complexity: O(m * n) where m is the length of arrays l and r (number of queries), and n is the average length of subarrays being checked.

Breaking down the analysis:

• The outer list comprehension iterates through m queries (zip of l and r)
• For each query, the check function is called:
  • Slicing nums[l : l + n] takes O(n) time
  • Creating a set from the slice takes O(n) time
  • Finding min and max of the slice takes O(n) time each
  • The all() function with generator expression iterates through n elements, each with O(1) set lookup
  • Total per query: O(n) + O(n) + O(n) + O(n) + O(n) = O(n)
• Overall: O(m * n)

In the worst case where each subarray spans the entire array, n could be up to N (the length of the original nums array), making the complexity O(m * N).

Space Complexity: O(n) where n is the maximum length of any subarray being checked.

Breaking down the analysis:

• For each query, the check function creates:
  • A slice nums[l : l + n] which takes O(n) space
  • A set s containing up to n elements, taking O(n) space
• The output list storing m boolean values takes O(m) space
• Since subarrays are processed one at a time, only one set and slice exist at any moment
• Total: O(n) + O(m) = O(n + m)

Since typically n ≤ N and in many practical cases m is smaller than the maximum subarray length, the space complexity is dominated by O(n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Not Handling Duplicate Elements Correctly

One of the most common mistakes is assuming all elements in the subarray are unique. When duplicates exist, the set conversion s = set(subarray) will remove duplicates, which can lead to incorrect validation.

Problem Example:

• Subarray: [4, 4, 4, 4] (length = 4)
• After set conversion: {4} (only 1 unique element)
• The code calculates d = (4 - 4) / (4 - 1) = 0
• It then checks if 4, 4, 4, 4 exist in the set, which passes
• However, the set only contains one 4, not four!

Solution: Check if the arithmetic sequence would require duplicate values and verify they actually exist:

def is_arithmetic_sequence(arr: List[int], start: int, end: int) -> bool:
    length = end - start + 1
    subarray = arr[start : start + length]
    unique_elements = set(subarray)
  
    min_val = min(subarray)
    max_val = max(subarray)
  
    # Special case: if all elements should be the same
    if min_val == max_val:
        # All elements must be identical
        return len(unique_elements) == 1 and len(subarray) == length
  
    difference, remainder = divmod(max_val - min_val, length - 1)
  
    if remainder != 0:
        return False
  
    # If difference is 0 but min != max, it's impossible
    if difference == 0:
        return False
  
    # Check if we have exactly the right number of unique elements
    expected_unique_count = length
    if len(unique_elements) != expected_unique_count:
        return False
  
    # Verify all expected terms exist
    for i in range(length):
        expected_term = min_val + i * difference
        if expected_term not in unique_elements:
            return False
  
    return True

2. Integer Overflow in Arithmetic Operations

When calculating max_val - min_val or min_val + i * difference, integer overflow might occur with very large numbers.

Solution: Use appropriate data types or add overflow checks:

# Python handles big integers automatically, but in other languages:
# Check if the multiplication would overflow before performing it
if i > 0 and difference > (sys.maxsize - min_val) // i:
    return False  # Would overflow

3. Edge Case: Subarray of Length 1 or 2

Some implementations might incorrectly handle these special cases:

• Length 1: Any single element forms an arithmetic sequence
• Length 2: Any two elements form an arithmetic sequence

Solution: Add explicit checks for these cases:

def is_arithmetic_sequence(arr: List[int], start: int, end: int) -> bool:
    length = end - start + 1
  
    # Special cases
    if length == 1:
        return True  # Single element is always arithmetic
    if length == 2:
        return True  # Any two elements form an arithmetic sequence
  
    # Continue with regular logic for length >= 3
    ...

4. Performance Issue: Recreating Sets and Finding Min/Max Multiple Times

The current implementation recalculates min/max and creates a new set for each query, even when subarrays overlap.

Solution for Better Performance: Use preprocessing or caching when queries have overlapping ranges:

class Solution:
    def checkArithmeticSubarrays(self, nums: List[int], l: List[int], r: List[int]) -> List[bool]:
        # Cache for storing results of previously computed subarrays
        cache = {}
      
        def is_arithmetic_sequence(start: int, end: int) -> bool:
            # Check cache first
            if (start, end) in cache:
                return cache[(start, end)]
          
            # Compute result
            result = compute_arithmetic_check(start, end)
          
            # Store in cache
            cache[(start, end)] = result
            return result
      
        # ... rest of the implementation

The most critical pitfall is #1 (duplicate handling), as it can cause the algorithm to incorrectly validate sequences that aren't actually arithmetic when rearranged.