Arithmetic Subarrays

medium array sorting hash set

Problem

A sequence is arithmetic if it has at least two elements and the difference between every two consecutive elements is the same. You are given an array nums and two arrays l and r describing range queries. For the i-th query, return whether the subarray nums[l[i]..r[i]] can be rearranged to form an arithmetic sequence.

Inputnums = [4,6,5,9,3,7], l = [0,0,2], r = [2,3,5]

Output[true, false, true]

Query 0 → [4,6,5] sorts to [4,5,6] (step 1) ✓. Query 1 → [4,6,5,9] cannot be made arithmetic ✗. Query 2 → [5,9,3,7] sorts to [3,5,7,9] (step 2) ✓.

nums (comma-separated)

l (left indices, comma-separated)

r (right indices, comma-separated)

def check_arithmetic_subarrays(nums, l, r):
    ans = []
    for li, ri in zip(l, r):
        sub = sorted(nums[li:ri + 1])
        diff = sub[1] - sub[0]
        ok = True
        for i in range(2, len(sub)):
            if sub[i] - sub[i - 1] != diff:
                ok = False
                break
        ans.append(ok)
    return ans

function checkArithmeticSubarrays(nums, l, r) {
  const ans = [];
  for (let q = 0; q < l.length; q++) {
    const sub = nums.slice(l[q], r[q] + 1).sort((a, b) => a - b);
    const diff = sub[1] - sub[0];
    let ok = true;
    for (let i = 2; i < sub.length; i++) {
      if (sub[i] - sub[i - 1] !== diff) {
        ok = false;
        break;
      }
    }
    ans.push(ok);
  }
  return ans;
}

List<Boolean> checkArithmeticSubarrays(int[] nums, int[] l, int[] r) {
    List<Boolean> ans = new ArrayList<>();
    for (int q = 0; q < l.length; q++) {
        int[] sub = Arrays.copyOfRange(nums, l[q], r[q] + 1);
        Arrays.sort(sub);
        int diff = sub[1] - sub[0];
        boolean ok = true;
        for (int i = 2; i < sub.length; i++) {
            if (sub[i] - sub[i - 1] != diff) {
                ok = false;
                break;
            }
        }
        ans.add(ok);
    }
    return ans;
}

vector<bool> checkArithmeticSubarrays(vector<int>& nums, vector<int>& l, vector<int>& r) {
    vector<bool> ans;
    for (int q = 0; q < (int)l.size(); q++) {
        vector<int> sub(nums.begin() + l[q], nums.begin() + r[q] + 1);
        sort(sub.begin(), sub.end());
        int diff = sub[1] - sub[0];
        bool ok = true;
        for (int i = 2; i < (int)sub.size(); i++) {
            if (sub[i] - sub[i - 1] != diff) {
                ok = false;
                break;
            }
        }
        ans.push_back(ok);
    }
    return ans;
}

Explanation

A set of numbers can be reordered into an arithmetic sequence exactly when its sorted order is arithmetic. Sorting puts the values in increasing order, and an arithmetic sequence is monotone, so if any arrangement works the sorted one does too.

So for each query we slice out the subarray nums[l[i]..r[i]], sort it, and compute the target common difference diff = sub[1] - sub[0] between the two smallest values.

We then scan the rest of the sorted subarray. If every consecutive pair has the same difference diff, the subarray is arithmetic and we record true; the moment one pair disagrees we record false and stop early.

Each query is independent, so we just repeat this slice-sort-check routine and append the boolean answer for every query. Sorting dominates the cost of each query.

Example: query [5,9,3,7] sorts to [3,5,7,9]; the gaps are 2, 2, 2 — all equal — so the answer is true.

Time: O(m · k log k) Space: O(k)