We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Arithmetic Subarrays

Number: 1752

Difficulty: Medium

Paid? No

Companies: Google

Problem Description

Given an array of integers and several range queries defined by two arrays l and r, determine whether the subarray for each query can be rearranged to form an arithmetic sequence. An arithmetic sequence is one in which the difference between consecutive elements is constant.

Key Insights

  • To validate an arithmetic sequence, sorting the subarray helps to easily compare consecutive differences.
  • A subarray with only two elements is inherently arithmetic.
  • For each query, extracting and sorting the subarray followed by checking consecutive differences gives a clear solution.
  • The constraints (n, m up to 500) allow the use of sorting for each query without performance issues.

Space and Time Complexity

Time Complexity: O(m * k log k), where m is the number of queries and k is the average length of the subarray. In the worst case, k can be O(n), so it becomes O(m * n log n).
Space Complexity: O(k) per query for the temporary subarray storage.

Solution

For each query, extract the subarray defined by indices [l[i], r[i]]. If the subarray length is 2, it is automatically arithmetic. Otherwise, sort the subarray and calculate the common difference between the first two elements. Then, iterate through the sorted subarray to check if every consecutive difference matches the common difference. If a mismatch is found, the subarray cannot be rearranged to form an arithmetic sequence. This approach leverages sorting to simplify the verification of consecutive differences.

Code Solutions

# Python solution with detailed comments

def arithmetic_subarrays(nums, l, r):
    # List to store the results for each query
    result = []
    # Iterate through each query
    for i in range(len(l)):
        # Extract the subarray for the current query
        subarray = nums[l[i]:r[i] + 1]
        # Sorting the subarray simplifies checking arithmetic condition
        subarray.sort()
        # If the subarray has only two elements, it is automatically arithmetic
        if len(subarray) == 2:
            result.append(True)
            continue
        # Compute the common difference using the first two elements
        common_diff = subarray[1] - subarray[0]
        # Flag to keep track if current subarray forms an arithmetic sequence
        is_arithmetic = True
        # Check consecutive differences in the sorted subarray
        for j in range(2, len(subarray)):
            if subarray[j] - subarray[j - 1] != common_diff:
                is_arithmetic = False
                break
        result.append(is_arithmetic)
    return result

# Example usage:
nums = [4, 6, 5, 9, 3, 7]
l = [0, 0, 2]
r = [2, 3, 5]
print(arithmetic_subarrays(nums, l, r))  # Output: [True, False, True]
← Back to All Questions