Sponsored
Sponsored
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.
Time Complexity is O(m * n log n) because for each query, we may sort the subarray (n log n). The space complexity is O(n) for the auxiliary array created for each query.
1#include <stdbool.h>
2#include <stdlib.h>
3
4int compare(const void* a, const void* b) {
5 return (*(int*)a - *(int*)b);
6}
7
8bool canBeArithmetic(int* nums, int size) {
9 if (size <= 1) return true;
10 qsort(nums, size, sizeof(int), compare);
11 int diff = nums[1] - nums[0];
12 for (int i = 2; i < size; i++) {
13 if (nums[i] - nums[i - 1] != diff) return false;
14 }
15 return true;
16}
17
18bool* checkArithmeticSubarrays(int* nums, int numsSize, int* l, int* r, int queriesSize, int* returnSize) {
19 *returnSize = queriesSize;
20 bool* result = (bool*)malloc(queriesSize * sizeof(bool));
21 for (int i = 0; i < queriesSize; i++) {
22 int start = l[i], end = r[i];
23 int* subarray = (int*)malloc((end - start + 1) * sizeof(int));
24 for (int j = start; j <= end; j++) {
25 subarray[j - start] = nums[j];
26 }
27 result[i] = canBeArithmetic(subarray, end - start + 1);
28 free(subarray);
29 }
30 return result;
31}This solution defines a helper function canBeArithmetic which takes an array and checks if it can form an arithmetic sequence after sorting. The main function checkArithmeticSubarrays prepares a subarray for each query, uses the helper function to analyze it, and stores the results.
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.
Time Complexity: O(n) per query, where n is the length of the subarray due to linear scans. Space Complexity: O(n) for the boolean array used for tracking.
1#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;
}C++ approaches this problem by leveraging STL algorithms and unordered sets to detect discrepancies in arithmetic sequences in the candidate subarrays. The use of a set ensures unique terms before confirming an arithmetic pattern.