Arithmetic Subarrays solution and explanation
Google
9 more videos on this problem
Arithmetic Subarrays | 2 Approaches | Sorting | Without Sorting | Leetcode-1630codestorywithMIK · 21:45 · 4K views
1630. Arithmetic Subarrays | LeetCode | Weekly Contest 212 | Arrays | SortingCoding Gist · 9:24 · 2K views
1630. Arithmetic Subarrays | Maths | AP | 2 WaysAryan Mittal · 17:03 · 1K views
1630. Arithmetic Subarrays (Leetcode Medium)Programming Live with Larry · 6:58 · 991 views
1630. Arithmetic Subarrays/ Explanation and C++ codeCoding with U · 7:57 · 752 views
Leetcode 1630. Arithmetic SubarraysFraz · 18:30 · 747 views
LeetCode 1630. Arithmetic SubarraysAbrar & Software Engineering · 4:32 · 738 views
✅ Arithmetic Subarrays - Simple Interview Solution - 1630 LeetCode Medium - Explained and VisualizedLeet Logics · 10:22 · 736 views
LeetCode 1630 : Java Solution | Arithmetic SubarraysAmit Manjarly · 9:48 · 416 views
Solving LeetCode 1630 Arithmetic Subarrays | Array | Detailed ExplanationCode Harmony · 16:30 · 403 views
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.
For example, these are arithmetic sequences:
1, 3, 5, 7, 9 7, 7, 7, 7 3, -1, -5, -9
The following sequence is not arithmetic:
1, 1, 2, 5, 7
You are given an array of n integers, nums, and two arrays of m integers each, l and r, representing the m range queries, where the ith query is the range [l[i], r[i]]. All the arrays are 0-indexed.
Return a list of boolean elements answer, where answer[i] is true if the subarray nums[l[i]], nums[l[i]+1], ... , nums[r[i]] can be rearranged to form an arithmetic sequence, and false otherwise.
Example 1:
Input: nums =[4,6,5,9,3,7], l =[0,0,2], r =[2,3,5]Output:[true,false,true]Explanation: 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]. Thiscan be rearranged as[3,5,7,9], which is an arithmetic sequence.
Example 2:
Input: 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] Output: [false,true,false,false,true,true]
Constraints:
n == nums.lengthm == l.lengthm == r.length2 <= n <= 5001 <= m <= 5000 <= l[i] < r[i] < n-105 <= nums[i] <= 105
Approach overview
Problem Overview: You receive an integer array nums and two arrays l and r describing multiple queries. Each query asks whether the subarray nums[l[i]...r[i]] can be rearranged to form an arithmetic sequence. An arithmetic sequence has a constant difference between consecutive elements.
Approach 1: Sorting and Validating Arithmetic Sequence (O(m * k log k) time, O(k) space)
The most direct solution extracts each queried subarray, sorts it, and checks whether adjacent elements share the same difference. After sorting, compute the difference d = arr[1] - arr[0]. Then iterate through the sorted list and verify that arr[i] - arr[i-1] == d for every index. If any difference breaks the pattern, the subarray cannot form an arithmetic progression.
This approach relies on sorting to normalize the order of elements. Without sorting, the numbers may appear in arbitrary order even if they could form a valid sequence when rearranged. Sorting guarantees that valid arithmetic sequences appear with equal adjacent gaps. The method is simple to implement and easy to reason about during interviews. For m queries with average subarray length k, the complexity becomes O(m * k log k).
Approach 2: Mathematical Check Without Sorting (O(m * k) time, O(k) space)
A faster strategy avoids sorting by using arithmetic properties of the sequence. For a valid arithmetic sequence of length k, the difference must be (max - min) / (k - 1). First scan the subarray to compute the minimum and maximum values. If (max - min) is not divisible by (k - 1), forming an arithmetic sequence is impossible.
If the difference is valid, iterate through the elements and check whether each value fits the expected positions: min + i * diff. A hash set or boolean set tracks numbers already seen to detect duplicates. Each element must map exactly to one valid position in the progression. If all positions are filled without conflicts, the subarray forms an arithmetic sequence.
This technique eliminates the sorting step and reduces each query to linear time. It relies on properties of arithmetic sequences rather than ordering. The algorithm mainly uses array scans and constant-time membership checks, making it an efficient approach for multiple queries over the same array.
Recommended for interviews: Start with the sorting solution since it clearly demonstrates the arithmetic progression condition and is easy to implement correctly. After discussing complexity, mention the mathematical check optimization. Interviewers typically expect candidates to recognize that sorting is unnecessary and derive the difference using min and max. Showing both approaches demonstrates solid algorithmic reasoning and optimization skills.
Approach 1: Sorting and Validating Arithmetic Sequence
For each query, extract the subarray defined by the given l and r indices. Sort this subarray to determine if it can be rearranged into an arithmetic sequence. Once sorted, check if the difference between consecutive elements is constant throughout the subarray.
If the difference is consistent, then the subarray can be rearranged to form an arithmetic sequence, otherwise it cannot.
from typing import List
class Solution:
def checkArithmeticSubarrays(self, nums: List[int], l: List[int], r: List[int]) -> List[bool]:
def is_arithmetic(subarray: List[int]) -> bool:
subarray.sort()
difference = subarray[1] - subarray[0]
return all(subarray[i] - subarray[i - 1] == difference for i in range(2, len(subarray)))
return [is_arithmetic(nums[start:end + 1]) for start, end in zip(l, r)]import java.util.*;
public class Solution {
public boolean[] checkArithmeticSubarrays(int[] nums, int[] l, int[] r) {
int queriesSize = l.length;
boolean[] result = new boolean[queriesSize];
for (int i = 0; i < queriesSize; i++) {
int start = l[i], end = r[i];
int[] subarray = Arrays.copyOfRange(nums, start, end + 1);
Arrays.sort(subarray);
result[i] = isArithmetic(subarray);
}
return result;
}
private boolean isArithmetic(int[] arr) {
int diff = arr[1] - arr[0];
for (int i = 2; i < arr.length; i++) {
if (arr[i] - arr[i - 1] != diff) return false;
}
return true;
}
}#include <vector>
#include <algorithm>
using namespace std;
bool isArithmetic(vector<int>& arr) {
sort(arr.begin(), arr.end());
int diff = arr[1] - arr[0];
for (int i = 2; i < arr.size(); i++) {
if (arr[i] - arr[i - 1] != diff) return false;
}
return true;
}
vector<bool> checkArithmeticSubarrays(vector<int>& nums, vector<int>& l, vector<int>& r) {
vector<bool> result;
for (int i = 0; i < l.size(); i++) {
vector<int> subarray(nums.begin() + l[i], nums.begin() + r[i] + 1);
result.push_back(isArithmetic(subarray));
}
return result;
}var checkArithmeticSubarrays = function(nums, l, r) {
const result = [];
for (let i = 0; i < l.length; i++) {
const start = l[i];
const end = r[i];
const subarray = nums.slice(start, end + 1);
subarray.sort((a, b) => a - b);
result.push(isArithmetic(subarray));
}
return result;
};
function isArithmetic(arr) {
const diff = arr[1] - arr[0];
for (let i = 2; i < arr.length; i++) {
if (arr[i] - arr[i - 1] !== diff) return false;
}
return true;
}#include <stdbool.h>
#include <stdlib.h>
int compare(const void* a, const void* b) {
return (*(int*)a - *(int*)b);
}
bool canBeArithmetic(int* nums, int size) {
if (size <= 1) return true;
qsort(nums, size, sizeof(int), compare);
int diff = nums[1] - nums[0];
for (int i = 2; i < size; i++) {
if (nums[i] - nums[i - 1] != diff) return false;
}
return true;
}
bool* checkArithmeticSubarrays(int* nums, int numsSize, int* l, int* r, int queriesSize, int* returnSize) {
*returnSize = queriesSize;
bool* result = (bool*)malloc(queriesSize * sizeof(bool));
for (int i = 0; i < queriesSize; i++) {
int start = l[i], end = r[i];
int* subarray = (int*)malloc((end - start + 1) * sizeof(int));
for (int j = start; j <= end; j++) {
subarray[j - start] = nums[j];
}
result[i] = canBeArithmetic(subarray, end - start + 1);
free(subarray);
}
return result;
}using System;
public class Solution {
public bool[] CheckArithmeticSubarrays(int[] nums, int[] l, int[] r) {
bool[] result = new bool[l.Length];
for (int i = 0; i < l.Length; i++) {
int start = l[i], end = r[i];
int[] subarray = new int[end - start + 1];
Array.Copy(nums, start, subarray, 0, end - start + 1);
Array.Sort(subarray);
result[i] = IsArithmetic(subarray);
}
return result;
}
private bool IsArithmetic(int[] arr) {
int diff = arr[1] - arr[0];
for (int i = 2; i < arr.Length; i++) {
if (arr[i] - arr[i - 1] != diff) return false;
}
return true;
}
}The Python solution uses list slices to create subarrays, sorts them in place, and checks for consistent differences using a generator expression within the function is_arithmetic. The list comprehension iterates over every query.
Time Complexity: O(m * n log n) for m queries where the longest possible subarray to sort is of n elements. Space complexity is O(n) for the list slices.
Approach 2: Mathematical Check Without Sorting
Rather than sorting, we can try to compute the minimum and maximum of the subarray to figure out the common difference, because in an arithmetic series, the difference between consecutive terms should be consistent. For each candidate difference, check manually if the subarray can be transformed into a complete arithmetic sequence by verifying all expected elements.
from typing import List
class Solution:
def checkArithmeticSubarrays(self, nums: List[int], l: List[int], r: List[int]) -> List[bool]:
def is_arithmetic_no_sort(start: int, end: int) -> bool:
min_val, max_val = min(nums[start:end+1]), max(nums[start:end+1])
diff = end - start
if (max_val - min_val) % diff != 0:
return False
step = (max_val - min_val) // diff
if step == 0:
return True
expected = set(min_val + n * step for n in range(diff + 1))
return len(expected) == len(set(nums[start:end+1])) and expected == set(nums[start:end+1])
return [is_arithmetic_no_sort(start, end) for start, end in zip(l, r)]import java.util.*;
public class Solution {
public boolean[] checkArithmeticSubarrays(int[] nums, int[] l, int[] r) {
boolean[] result = new boolean[l.length];
for (int i = 0; i < l.length; i++) {
result[i] = canBeArithmeticWithoutSort(nums, l[i], r[i]);
}
return result;
}
private boolean canBeArithmeticWithoutSort(int[] nums, int start, int end) {
int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
for (int i = start; i <= end; i++) {
if (nums[i] < min) min = nums[i];
if (nums[i] > max) max = nums[i];
}
int diff = end - start;
if ((max - min) % diff != 0) return false;
int step = (max - min) / diff;
if (step == 0) return true;
Set<Integer> seen = new HashSet<>();
for (int i = start; i <= end; i++) {
if ((nums[i] - min) % step != 0) return false;
if (!seen.add(nums[i])) return false;
}
return seen.size() == (end - start + 1);
}
}#include <vector>
#include <unordered_set>
#include <algorithm>
using namespace std;
bool canBeArithmeticWithoutSorting(const vector<int>& nums, int start, int end) {
int minVal = *min_element(nums.begin() + start, nums.begin() + end + 1);
int maxVal = *max_element(nums.begin() + start, nums.begin() + end + 1);
int diff = end - start;
if ((maxVal - minVal) % diff != 0) return false;
int step = (maxVal - minVal) / diff;
if (step == 0) return true;
unordered_set<int> seen;
for (int i = start; i <= end; i++) {
if ((nums[i] - minVal) % step != 0) return false;
seen.insert(nums[i]);
}
return seen.size() == diff + 1;
}
vector<bool> checkArithmeticSubarrays(const vector<int>& nums, const vector<int>& l, const vector<int>& r) {
vector<bool> result;
for (int i = 0; i < l.size(); i++) {
result.push_back(canBeArithmeticWithoutSorting(nums, l[i], r[i]));
}
return result;
}var checkArithmeticSubarrays = function(nums, l, r) {
const result = l.map((start, i) => canBeArithmeticWithoutSort(nums, start, r[i]));
return result;
};
function canBeArithmeticWithoutSort(nums, start, end) {
const subNums = nums.slice(start, end + 1);
const minNum = Math.min(...subNums);
const maxNum = Math.max(...subNums);
const n = end - start;
if ((maxNum - minNum) % n !== 0) return false;
const diff = (maxNum - minNum) / n;
if (diff === 0) return true;
const seen = new Set();
for (let number of subNums) {
if ((number - minNum) % diff !== 0 || seen.has(number)) return false;
seen.add(number);
}
return seen.size === n + 1;
}#include <stdbool.h>
#include <limits.h>
bool canBeArithmeticWithoutSort(int* nums, int start, int end) {
int minVal = INT_MAX, maxVal = INT_MIN;
for (int i = start; i <= end; i++) {
if (nums[i] < minVal) minVal = nums[i];
if (nums[i] > maxVal) maxVal = nums[i];
}
int length = end - start + 1;
if ((maxVal - minVal) % (length - 1) != 0) return false;
int diff = (maxVal - minVal) / (length - 1);
if (diff == 0) return true;
bool* seen = (bool*)calloc(length, sizeof(bool));
for (int i = start; i <= end; i++) {
int position = (nums[i] - minVal) / diff;
if (position < 0 || position >= length || seen[position]) {
free(seen);
return false;
}
seen[position] = true;
}
free(seen);
return true;
}
bool* checkArithmeticSubarraysWithoutSort(int* nums, int numsSize, int* l, int* r, int queriesSize, int* returnSize) {
*returnSize = queriesSize;
bool* result = (bool*)malloc(queriesSize * sizeof(bool));
for (int i = 0; i < queriesSize; i++) {
result[i] = canBeArithmeticWithoutSort(nums, l[i], r[i]);
}
return result;
}using System;
using System.Collections.Generic;
public class Solution {
public bool[] CheckArithmeticSubarrays(int[] nums, int[] l, int[] r) {
bool[] result = new bool[l.Length];
for (int i = 0; i < l.Length; i++) {
result[i] = CanBeArithmeticWithoutSort(nums, l[i], r[i]);
}
return result;
}
private bool CanBeArithmeticWithoutSort(int[] nums, int start, int end) {
int min = int.MaxValue, max = int.MinValue;
for (int i = start; i <= end; i++) {
if (nums[i] < min) min = nums[i];
if (nums[i] > max) max = nums[i];
}
int len = end - start;
if ((max - min) % len != 0) return false;
int step = (max - min) / len;
if (step == 0) return true;
HashSet<int> seen = new HashSet<int>();
for (int i = start; i <= end; i++) {
if ((nums[i] - min) % step != 0 || !seen.Add(nums[i])) {
return false;
}
}
return seen.Count == len + 1;
}
}Python benefits from set operations and comprehensions to evaluate necessary elements for an arithmetic sequence with specific differences, avoiding sort operations but ensuring sets comply with arithmetic laws.
A check per subarray runs in O(n) time driven by set operations, with space being similarly O(n) because of element tracking across potentially full subarrays.
Approach 3: Default Approach
function checkArithmeticSubarrays(nums: number[], l: number[], r: number[]): boolean[] {
const check = (nums: number[], l: number, r: number): boolean => {
const s = new Set<number>();
const n = r - l + 1;
let a1 = 1 << 30;
let an = -a1;
for (let i = l; i <= r; ++i) {
s.add(nums[i]);
a1 = Math.min(a1, nums[i]);
an = Math.max(an, nums[i]);
}
if ((an - a1) % (n - 1) !== 0) {
return false;
}
const d = Math.floor((an - a1) / (n - 1));
for (let i = 1; i < n; ++i) {
if (!s.has(a1 + (i - 1) * d)) {
return false;
}
}
return true;
};
const ans: boolean[] = [];
for (let i = 0; i < l.length; ++i) {
ans.push(check(nums, l[i], r[i]));
}
return ans;
}func checkArithmeticSubarrays(nums []int, l []int, r []int) (ans []bool) {
check := func(nums []int, l, r int) bool {
s := map[int]struct{}{}
n := r - l + 1
a1, an := 1<<30, -(1 << 30)
for _, x := range nums[l : r+1] {
s[x] = struct{}{}
if a1 > x {
a1 = x
}
if an < x {
an = x
}
}
if (an-a1)%(n-1) != 0 {
return false
}
d := (an - a1) / (n - 1)
for i := 1; i < n; i++ {
if _, ok := s[a1+(i-1)*d]; !ok {
return false
}
}
return true
}
for i := range l {
ans = append(ans, check(nums, l[i], r[i]))
}
return
}impl Solution {
pub fn check_arithmetic_subarrays(nums: Vec<i32>, l: Vec<i32>, r: Vec<i32>) -> Vec<bool> {
let m = l.len();
let mut res = vec![true; m];
for i in 0..m {
let mut arr = nums[l[i] as usize..=r[i] as usize].to_vec();
arr.sort();
for j in 2..arr.len() {
if arr[j - 2] - arr[j - 1] != arr[j - 1] - arr[j] {
res[i] = false;
break;
}
}
}
res
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Sorting and Validating Arithmetic Sequence | Time Complexity: O(m * n log n) for m queries where the longest possible subarray to sort is of n elements. Space complexity is O(n) for the list slices. |
| Mathematical Check Without Sorting | A check per subarray runs in O(n) time driven by set operations, with space being similarly O(n) because of element tracking across potentially full subarrays. |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sorting and Validating Arithmetic Sequence | O(m * k log k) | O(k) | Best for clarity and quick implementation during interviews |
| Mathematical Check Without Sorting | O(m * k) | O(k) | Optimal when many queries exist and sorting overhead should be avoided |
Frequently asked questions
Is Arithmetic Subarrays easy or hard?
Arithmetic Subarrays is classified as a Medium problem. The basic idea using sorting is straightforward, but recognizing the mathematical property that allows an O(k) check without sorting requires deeper problem-solving insight.
Arithmetic Subarrays Python/Java solution
Python and Java implementations usually follow either the sorting approach or the mathematical set-based check. Python solutions often use sets for quick membership checks, while Java solutions typically use HashSet and loops to verify each expected arithmetic position.
How to solve Arithmetic Subarrays in O(n)?
Each query can be processed in linear time relative to the subarray size. Scan the subarray once to compute min and max, determine the expected difference, and verify positions using a hash set. This avoids sorting and keeps the complexity at O(k) per query.
What is the best approach for Arithmetic Subarrays?
The most efficient approach uses a mathematical check without sorting. Compute the minimum and maximum values of the subarray, derive the expected difference (max - min) / (k - 1), and verify that every element fits a valid position in the arithmetic sequence using a hash set. This reduces each query to O(k) time instead of O(k log k).
Is Arithmetic Subarrays asked at Google/Amazon/Meta?
Arithmetic progression and array query problems frequently appear in interviews at companies like Amazon, Google, and Meta. The question tests array manipulation, mathematical reasoning, and optimization from sorting-based checks to linear-time validation.
What data structure is used in Arithmetic Subarrays?
Arrays are used to process the queries and extract subarrays. The optimized solution also uses a hash set to track visited numbers and ensure each expected arithmetic position appears exactly once.
What is the time complexity of Arithmetic Subarrays?
The sorting-based method runs in O(m * k log k) time where m is the number of queries and k is the subarray length. The optimized mathematical approach removes sorting and runs in O(m * k) time with O(k) extra space for membership checks.