Python 1630.py
class Solution:
def checkArithmeticSubarrays(self, nums: List[int], l: List[int], r: List[int]) -> List[bool]:
for left, right in zip(l, r):
if right - left < 1:
yield False
continue
ok = True
sub = sorted(nums[left : right + 1])
diff = sub[1] - sub[0]
for i in range(2, len(sub)):
if sub[i] - sub[i - 1] != diff:
ok = False
break
yield ok
Difficulty
and has an acceptance rate of about 84% (100k+ submissions).
Typical patterns to solve this problem:
- Array
- Hash Table
- Sorting
AI Disclaimer
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.
See this dedicated page for more details.
Code Walkthrough
Overview
The provided implementation defines a Solution class with a method checkArithmeticSubarrays. The method receives three lists: nums, the source array of integers, and two parallel lists l and r that specify the left and right boundaries of sub-arrays to be examined. For each pair of boundaries the method determines whether the elements in the corresponding slice of nums can be reordered to form an arithmetic sequence. The result for each query is produced as a boolean value using a generator pattern (yield).
Core Logic
The method iterates over the paired boundaries using zip(l, r). For each (left, right) pair the first conditional checks whether the slice contains fewer than two elements:
if right - left < 1:
yield False
continue
When the slice length is insufficient to define a difference, the method immediately yields False and proceeds to the next query.
If the slice contains at least two elements, the algorithm proceeds to sort the relevant portion of nums:
sub = sorted(nums[left : right + 1])
Sorting guarantees that any potential arithmetic progression will appear in order, allowing a simple difference comparison. The common difference is captured from the first two sorted elements:
diff = sub[1] - sub[0]
A flag ok is initialized to True. The method then walks through the sorted slice starting at index 2, comparing each adjacent difference to the previously computed diff:
for i in range(2, len(sub)):
if sub[i] - sub[i - 1] != diff:
ok = False
break
If any pair deviates from the expected difference, ok is set to False and the loop terminates early. Finally, the boolean outcome for the current query is yielded:
yield ok
Edge Cases Handled
The early length check (right - left < 1) explicitly handles sub-arrays of length zero or one. In such cases an arithmetic progression cannot be defined, and the method returns False without performing unnecessary work.
The slicing operation nums[left : right + 1] correctly includes the element at index right. This ensures that queries where left equals right (a single-element slice) are still processed by the length check and not mistakenly omitted.
Sorting an empty slice would produce an empty list, but the preceding length guard prevents the subsequent indexing (sub[1]) from raising an exception. Similarly, slices of exactly two elements bypass the inner loop because range(2, len(sub)) yields no iterations, and the method correctly returns True as any two numbers trivially form an arithmetic sequence.
Performance Optimizations
The algorithm leverages early exits to avoid unnecessary computation. The length guard eliminates sorting and difference checks for slices that cannot satisfy the arithmetic condition, saving both time and memory for trivial queries.
Sorting is performed only on the minimal required slice (nums[left : right + 1]) rather than on the entire nums array. This localized sorting reduces the amount of data processed per query, especially when the query ranges are small relative to the size of nums.
The inner loop includes a break statement that stops the iteration as soon as a mismatch is detected. This prevents the method from scanning the entire sorted slice when the arithmetic property fails early, providing a best-case speed advantage for non-arithmetic sub-arrays.
Using a generator (yield) instead of building a list of results allows the caller to consume boolean outcomes lazily. This can reduce peak memory usage when the number of queries is large, as results are produced one at a time rather than stored all at once.
ELI5 - Simplified Explanation
Imagine you have a long row of numbered toy blocks. This code is like a little robot that looks at different groups of those blocks to see if they follow a special pattern. A pattern happens when the gap between every single block is exactly the same, just like when you count by twos like two, four, six, and eight.
The robot starts by picking a slice of the blocks using two markers. It marks the start and the end of the group it wants to check. Once it has that group, it lines all those blocks up in order from the smallest number to the biggest number so that it is easy to compare them. After the blocks are lined up, the robot looks at the difference between the first two blocks to see how much the numbers jump. Then, it walks down the line of blocks one by one. It checks the gap between each pair of neighbors to make sure the jump stays the same throughout the whole group. If the robot finds even one gap that does not match the first jump, it knows the pattern is broken. If all the gaps stay the same, the robot knows the group is a perfect match.
Code Quality
Complexity Analysis
As a rule of thumb, the maximum input size for one second execution time is
- factorial: up to 10 elements
- exponential: up to 20 elements
- polynomial: a few thousand elements
- loglinear: up to 100,000 elements
- linear: a few million elements
- logarithmic: a billion elements
- constant: practically unlimited
Other Solutions
Obviously, I did that after I solved the problem myself.
In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.
And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.
(click on a column header to sort the table)
| author | ||||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| author | solutions | |||||||||
| www | AlgoMonster | C++ | Python | Java | TS | |||||
| WalkCCC | C++ | Python | Java | |||||||
| leetcode.ca | C++ | Python | Java | C# | Go | Rust | TS | |||
| Progiez | C++ | Python | Java | |||||||
| github | black-shadows | C++ | ||||||||
| charles-wangkai | Java | |||||||||
| everthis | JS | |||||||||
| fartem | Ruby | |||||||||
| fsq | C++ | |||||||||
| JoshCrozier | JS | |||||||||
| lkwq007 | Python | |||||||||
| suxrobGM | C# | |||||||||
| varunu28 | Java | |||||||||
| YuriSpiridonov | Python | |||||||||
| AlgoMonster | C++, Python, Java, TypeScript | |||||||||
| WalkCCC | C++, Python, Java | |||||||||
| leetcode.ca | C++, C#, Go, Java, Python, Rust, TypeScript | |||||||||
| Progiez | C++, Java, Python | |||||||||
| black-shadows | C++, C++ | |||||||||
| charles-wangkai | Java | |||||||||
| everthis | JavaScript | |||||||||
| fartem | Ruby | |||||||||
| fsq | C++ | |||||||||
| JoshCrozier | JavaScript | |||||||||
| lkwq007 | Python | |||||||||
| suxrobGM | C# | |||||||||
| varunu28 | Java | |||||||||
| YuriSpiridonov | Python |
Videos
Similar Problems
- problem 1502: Can Make Arithmetic Progression From Sequence
Solved On The Same Day
- problem 1550: Three Consecutive Odds
- problem 1629: Slowest Key
- problem 1637: Widest Vertical Area Between Two Points Containing No Points
- problem 1684: Count the Number of Consistent Strings
- problem 1663: Smallest String With A Given Numeric Value
Extra
- Tech Stack - my development environment and tools
- AI - how AI helped me create this website (NOT solving the problems)
- Progress - progression over time
- Quality - code quality