In this guide, you will get 1630. Arithmetic Subarrays LeetCode Solution with the best time and space complexity. The solution to Arithmetic Subarrays problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
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]. This can 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.length
m == l.length
m == r.length
2 <= n <= 500
1 <= m <= 500
0 <= l[i] < r[i] < n
-105 <= nums[i] <= 105
Complexity Analysis
Time Complexity: O(mn)
Space Complexity: O(n)
1630. Arithmetic Subarrays LeetCode Solution in C++
class Solution {
public:
vector<bool> checkArithmeticSubarrays(vector<int>& nums, vector<int>& l,
vector<int>& r) {
vector<bool> ans;
for (int i = 0; i < l.size(); ++i)
ans.push_back(isArithmetic(nums, l[i], r[i]));
return ans;
}
private:
bool isArithmetic(vector<int>& nums, int l, int r) {
if (r - l < 2)
return true;
unordered_set<int> numsSet;
int mn = INT_MAX;
int mx = INT_MIN;
for (int i = l; i <= r; ++i) {
mn = min(mn, nums[i]);
mx = max(mx, nums[i]);
numsSet.insert(nums[i]);
}
if ((mx - mn) % (r - l) != 0)
return false;
const int interval = (mx - mn) / (r - l);
for (int k = 1; k <= r - l; ++k)
if (!numsSet.contains(mn + k * interval))
return false;
return true;
}
}; /* code provided by PROGIEZ */
1630. Arithmetic Subarrays LeetCode Solution in Java
class Solution {
public List<Boolean> checkArithmeticSubarrays(int[] nums, int[] l, int[] r) {
List<Boolean> ans = new ArrayList<>();
for (int i = 0; i < l.length; ++i)
ans.add(isArithmetic(nums, l[i], r[i]));
return ans;
}
private boolean isArithmetic(int[] nums, int l, int r) {
if (r - l < 2)
return true;
int mn = Integer.MAX_VALUE;
int mx = Integer.MIN_VALUE;
Set<Integer> numsSet = new HashSet<>();
for (int i = l; i <= r; ++i) {
mn = Math.min(mn, nums[i]);
mx = Math.max(mx, nums[i]);
numsSet.add(nums[i]);
}
if ((mx - mn) % (r - l) != 0)
return false;
final int interval = (mx - mn) / (r - l);
for (int k = 1; k <= r - l; ++k)
if (!numsSet.contains(mn + k * interval))
return false;
return true;
}
} // code provided by PROGIEZ
1630. Arithmetic Subarrays LeetCode Solution in Python
class Solution:
def checkArithmeticSubarrays(
self,
nums: list[int],
l: list[int],
r: list[int],
) -> list[bool]:
return [self._isArithmetic(nums, a, b) for a, b in zip(l, r)]
def _isArithmetic(self, nums: list[int], l: int, r: int) -> bool:
if r - l < 2:
return True
numsSet = set()
mn = math.inf
mx = -math.inf
for i in range(l, r+1):
mn = min(mn, nums[i])
mx = max(mx, nums[i])
numsSet.add(nums[i])
if (mx - mn) % (r - l) != 0:
return False
interval = (mx - mn) // (r - l)
return all(mn + k * interval in numsSet
for k in range(1, r - l + 1)) # code by PROGIEZ
