LeetCode 1630 - Arithmetic Subarrays

LeetCode Problem 1630

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Sorting

Solution

Problem Understanding

The problem asks us to determine whether subarrays of a given array can be rearranged to form an arithmetic sequence. An arithmetic sequence is one where the difference between consecutive elements is constant. The input consists of an array nums of integers and two arrays l and r representing the start and end indices of multiple subarrays. For each query, we are to check if the elements of the subarray nums[l[i]:r[i]+1] can be reordered to become arithmetic.

The expected output is a list of boolean values, one per query, indicating whether each subarray can form an arithmetic sequence. The constraints indicate that the array lengths are relatively small (n <= 500), which allows us to consider sorting each subarray directly as part of a feasible solution. Negative numbers are possible, so the solution must handle general integer values, not just positive ones.

Important edge cases include subarrays with only two elements (always arithmetic), subarrays with repeated elements (can form an arithmetic sequence with difference zero), and subarrays that have irregular gaps that prevent forming a constant difference.

Approaches

Brute Force

The brute-force approach is straightforward: for each query, extract the subarray, sort it, and then check the differences between consecutive elements. If all differences are equal, mark it as true; otherwise, mark it as false. This is correct because sorting puts the subarray in the only order where consecutive differences can be compared consistently, and the property of arithmetic sequences depends only on these differences. However, sorting each subarray individually has a time complexity of O(k log k) per query, leading to O(m * k log k) overall, which may become inefficient for the maximum constraints.

Optimal Approach

The key observation for optimization is that we can avoid sorting by calculating the expected difference using the minimum and maximum of the subarray. If a subarray of length k is arithmetic, the difference d must satisfy d = (max - min) / (k - 1) and all elements should fit into this evenly spaced sequence. By checking whether each element aligns with this expected difference without duplicates, we can determine if the subarray can form an arithmetic sequence. This avoids the O(k log k) sorting step, replacing it with a linear scan O(k).

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(m * k log k)	O(k)	Sort each subarray and check differences
Optimal	O(m * k)	O(k)	Use min, max, and a set to check arithmetic property without sorting

Algorithm Walkthrough

1. Initialize an empty result list answer.
2. Iterate over each query (l[i], r[i]).
3. Extract the subarray sub = nums[l[i]:r[i]+1].
4. Compute min_val and max_val of the subarray.
5. Compute the expected difference d = (max_val - min_val) / (length - 1). If this is not an integer, the subarray cannot form an arithmetic sequence.
6. Use a set to track elements seen. For each element x in the subarray, check if (x - min_val) % d == 0. If not, mark false. If duplicates occur in the expected positions, mark false.
7. If all elements fit the expected positions without conflicts, mark true.
8. Append the boolean result to answer.
9. Return answer.

Why it works: By deriving the difference from the min and max values and checking positions, we guarantee that the sequence can only be arithmetic if every element matches a slot in the expected evenly spaced sequence. This preserves correctness without sorting.

Python Solution

from typing import List

class Solution:
    def checkArithmeticSubarrays(self, nums: List[int], l: List[int], r: List[int]) -> List[bool]:
        answer = []
        for start, end in zip(l, r):
            sub = nums[start:end+1]
            length = end - start + 1
            min_val, max_val = min(sub), max(sub)
            if length == 2:
                answer.append(True)
                continue
            if (max_val - min_val) % (length - 1) != 0:
                answer.append(False)
                continue
            d = (max_val - min_val) // (length - 1)
            seen = set()
            valid = True
            for x in sub:
                if (x - min_val) % d != 0 or x in seen:
                    valid = False
                    break
                seen.add(x)
            answer.append(valid)
        return answer

The code first handles trivial subarrays of length 2, which are always arithmetic. For longer subarrays, it computes the expected difference d and uses a set to check that all elements can be placed correctly in the arithmetic sequence without duplicates. If any check fails, the subarray cannot form an arithmetic sequence.

Go Solution

func checkArithmeticSubarrays(nums []int, l []int, r []int) []bool {
    answer := make([]bool, len(l))
    for i := 0; i < len(l); i++ {
        start, end := l[i], r[i]
        sub := nums[start : end+1]
        length := end - start + 1
        if length == 2 {
            answer[i] = true
            continue
        }
        minVal, maxVal := sub[0], sub[0]
        for _, v := range sub {
            if v < minVal {
                minVal = v
            }
            if v > maxVal {
                maxVal = v
            }
        }
        if (maxVal - minVal) % (length - 1) != 0 {
            answer[i] = false
            continue
        }
        d := (maxVal - minVal) / (length - 1)
        seen := make(map[int]bool)
        valid := true
        for _, v := range sub {
            if (v - minVal) % d != 0 || seen[v] {
                valid = false
                break
            }
            seen[v] = true
        }
        answer[i] = valid
    }
    return answer
}

In Go, we handle slices and maps explicitly. The main difference from Python is the use of map[int]bool instead of a set, and slicing syntax for subarrays. Edge cases are handled identically.

Worked Examples

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

Query	Subarray	Sorted	Arithmetic?	Output
0	[4,6,5]	[4,5,6]	Yes, diff = 1	True
1	[4,6,5,9]	[4,5,6,9]	No, diffs = 1,1,3	False
2	[5,9,3,7]	[3,5,7,9]	Yes, diff = 2	True

Example 2: 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]

Query	Subarray	Arithmetic?	Output
0	[-12,-9,-3,-12,-6]	No	False
1	[-9,-3,-12,-6]	Yes	True
2	[15,20,-25,-20,-15,-10]	No	False
3	[-12,-6,15,20]	No	False
4	[-20,-15,-10]	Yes	True
5	[-25,-20,-15,-10]	Yes	True

Complexity Analysis

Measure	Complexity	Explanation
Time	O(m * k)	For each of the m queries, scan k elements to compute min, max, and validate sequence
Space	O(k)	A set/map is used to store elements of each subarray during validation

The approach is efficient given the problem constraints (n, m <= 500), and avoids the O(k log k) sorting step in the brute-force approach.

Test Cases

sol = Solution()
# Provided examples
assert sol.checkArithmeticSubarrays([4,6,5,9,3,7], [0,0,2], [2,3,5]) == [True, False, True]  # Example 1
assert sol.checkArithmeticSubarrays([-12,-9,-3,-12,-6,15,20,-25,-20,-15,-10], [0,1,6,4,8,7], [4,4,9,7,9,10]) == [False, True, False, False, True, True]  # Example 2
# Edge case: length 2 subarray
assert sol.checkArithmeticSubarrays([1,2,3], [0], [1]) == [True]  # Two elements always arithmetic
# Repeated elements
assert sol.checkArithmetic