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.
1using System;
2
3public class Solution {
4 public bool[] CheckArithmeticSubarrays(int[] nums, int[] l, int[] r) {
5 bool[] result = new bool[l.Length];
6 for (int i = 0; i < l.Length; i++) {
7 int start = l[i], end = r[i];
8 int[] subarray = new int[end - start + 1];
9 Array.Copy(nums, start, subarray, 0, end - start + 1);
10 Array.Sort(subarray);
11 result[i] = IsArithmetic(subarray);
12 }
13 return result;
14 }
15
16 private bool IsArithmetic(int[] arr) {
17 int diff = arr[1] - arr[0];
18 for (int i = 2; i < arr.Length; i++) {
19 if (arr[i] - arr[i - 1] != diff) return false;
20 }
21 return true;
22 }
23}This C# solution uses the built-in Array methods to copy and sort subarrays extracted according to the query. It uses the method IsArithmetic to determine if the sorted subarray is arithmetic.
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.
1using 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;
}
}In C#, we use hash sets to manage the unique propositions necessary for validating sequences without direct sorting, ensuring operational integrity through arithmetically-consistent projections.