Problem 1630

Abstract / Summary

Check if each given subarray forms an arithmetic sequence by comparing differences between consecutive elements.

Note

The full problem description, including helpful examples, can be found on LeetCode.

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
16 lines | 533 bytes | submitted November 14, 2023 | GitHub   tab size 4 | low complexity

Difficulty

This problem is ranked as
easy medium hard

and has an acceptance rate of about 84% (100k+ submissions).

Typical patterns to solve this problem:
  • Array
  • Hash Table
  • Sorting
I solved 663 easy, 1250 medium and 309 hard problems

AI Disclaimer

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
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.
LeetCode profile | GitHub repo

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.

written by openai gpt

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.

written by google gemini

Code Quality

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):
n = 27 | median = 7 | μ = 6.26 | σ = 1.48

Complexity Analysis

Time: loglinear
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
generated automatically

Other Solutions

I wrote a basic crawler to find other solutions to that problem.
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
27 links | 14 authors | 9 languages

Videos

7 videos   did my crawler come up with invalid videos ? drop me a line.

Similar Problems

1 similar problem

Solved On The Same Day

6 solutions   November 14, 2023

Extra

There are a few extra pages giving you some insights into my setup:
  • 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