MediumNo. 1630
Arithmetic Subarrays — LeetCode 1630 Python Solution
- Pattern
- Sorting
- Topics
- Array, Hash Table, Sorting
- Reading time
- 2 min
- Source
- leetcode.com
The problem
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.
Example
1, 3, 5, 7, 9 7, 7, 7, 7 3, -1, -5, -9
Python solution
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)]Complexity
- Time
- O(n)
- Space · auxiliary
- O(n)
Pattern: Sorting
Spend O(n log n) once to buy an ordering that makes the rest of the problem trivial. LeetCode 1630. Arithmetic Subarrays is filed here because LeetCode tags it Sorting, which is the vocabulary this hub collects.
The sorting guide has the Python template for the pattern and the 401 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 1636 | Sort Array by Increasing Frequency | Easy |
| 0049 | Group Anagrams | Medium |
| 0169 | Majority Element | Easy |
| 0217 | Contains Duplicate | Easy |
| 0229 | Majority Element II | Medium |
| 0268 | Missing Number | Easy |
Frequently asked questions
- How hard is LeetCode 1630. Arithmetic Subarrays?
LeetCode 1630. Arithmetic Subarrays is rated Medium on LeetCode.
- What is the time complexity of LeetCode 1630. Arithmetic Subarrays?
The Python solution on this page runs in O(n).
- What is the space complexity of LeetCode 1630. Arithmetic Subarrays?
The Python solution on this page uses O(n) auxiliary space.
- What topics does LeetCode 1630. Arithmetic Subarrays cover?
LeetCode 1630. Arithmetic Subarrays is tagged Array, Hash Table and Sorting on LeetCode.