#1630

Medium

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Arithmetic Subarrays

Determine whether subarrays of a given array can be rearranged to form arithmetic sequences using array scanning and hash lookup.

array hash table sorting

Problem Statement

Given an integer array nums and two integer arrays l and r of equal length, each query is defined by l[i] and r[i]. For each query, determine whether the subarray nums[l[i]..r[i]] can be rearranged to form an arithmetic sequence. A sequence is arithmetic if it has at least two elements and the difference between consecutive elements is constant.

Return a list of boolean values corresponding to each query. Constraints include array sizes up to 500 elements, values between -10^5 and 10^5, and query indices satisfying 0 <= l[i] < r[i] < n. Optimize by scanning subarrays and leveraging hash sets to quickly check for consistent differences without unnecessary sorting.

Examples

Example 1

Input: See original problem statement.

Output: See original problem statement.

1, 3, 5, 7, 9 7, 7, 7, 7 3, -1, -5, -9

Example 2

Input: See original problem statement.

Output: See original problem statement.

1, 1, 2, 5, 7

Example 3

Input: nums = [4,6,5,9,3,7], l = [0,0,2], r = [2,3,5]

Output: [true,false,true]

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]. This can be rearranged as [3,5,7,9], which is an arithmetic sequence.

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

Solution Approach

Scan and Find Min/Max

For each subarray, first determine the minimum and maximum values. Calculate the expected difference between consecutive elements if the subarray were arithmetic. This helps identify early if the subarray cannot form an arithmetic sequence due to uneven spacing.

Use Hash Lookup for Presence Check

Store all subarray elements in a hash set to quickly check whether each expected element exists. This avoids repeatedly sorting the subarray and allows O(1) verification for each candidate value based on the computed difference.

Validate Differences Efficiently

Iterate over the expected arithmetic sequence values using the calculated difference. If any value is missing from the hash set, mark the query as false. Otherwise, confirm true. This approach combines scanning and hash lookup for fast validation across multiple queries.

Complexity Analysis

Metric	Value
Time	O(m \cdot n)
Space	O(n)

Time complexity is O(m * n) since each of the m queries may scan up to n elements. Space complexity is O(n) to store the elements of the current subarray in a hash set for quick lookup.

What Interviewers Usually Probe

Check whether subarray differences are uniform rather than sorting all elements immediately.
Expect O(n) scanning per query using hash sets instead of naive O(n log n) sorting.
Clarify constraints on l[i] and r[i] to avoid off-by-one errors when slicing subarrays.

Common Pitfalls or Variants

Common pitfalls

Assuming subarrays are already sorted and directly checking differences.
Neglecting to handle negative or zero differences when validating arithmetic property.
Failing to account for subarrays of length two, which are trivially arithmetic.

Follow-up variants

Instead of checking all subarrays, determine the maximum length arithmetic subarray in a single scan.
Allow for at most one missing element that can be added to form an arithmetic sequence.
Modify the problem to check subarrays in a circular array, requiring modular index handling.

FAQ

What is an arithmetic sequence in this problem?

A sequence is arithmetic if it contains at least two elements and the difference between every two consecutive elements is the same.

How does array scanning help in checking subarrays?

Scanning allows you to find min and max values and calculate expected differences, quickly identifying non-arithmetic subarrays.

Why use a hash set in this solution?

A hash set lets you verify the presence of each expected element efficiently, avoiding repeated sorting of the subarray.

What is the time complexity for checking all queries?

The total time complexity is O(m * n), since each of the m queries may scan up to n elements.

Can GhostInterview handle large arrays for Arithmetic Subarrays?

Yes, it uses optimized scanning and hash lookup to efficiently handle arrays up to the maximum constraint of 500 elements.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

class Solution:
    def checkArithmeticSubarrays(
        self, nums: List[int], l: List[int], r: List[int]
    ) -> List[bool]:
        def check(nums, l, r):
            n = r - l + 1
            s = set(nums[l : l + n])
            a1, an = min(nums[l : l + n]), max(nums[l : l + n])
            d, mod = divmod(an - a1, n - 1)
            return mod == 0 and all((a1 + (i - 1) * d) in s for i in range(1, n))

        return [check(nums, left, right) for left, right in zip(l, r)]

Continue Practicing

#1636 sort array by increasing frequency #1604 alert using same key card three or more times in a one hour period #1679 max number of k sum pairs