Arithmetic Subarrays - Practice Coding Problems

Arithmetic Subarrays - 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] (difference = 2)
[7, 7, 7, 7] (difference = 0)
[3, -1, -5, -9] (difference = -4)

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.

Input & Output

Example 1 — Basic Queries

$ Input: nums = [4,6,5,9,3,7], l = [0,0,2], r = [2,3,5]

› Output: [true,false,true]

💡 Note: Query 1: [4,6,5] → sorted [4,5,6] with diff=1 (arithmetic). Query 2: [4,6,5,9] → sorted [4,5,6,9] with diffs [1,1,3] (not arithmetic). Query 3: [5,9,3,7] → sorted [3,5,7,9] with diff=2 (arithmetic).

Example 2 — Single Element

$ 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,true,false,true,true]

💡 Note: Single elements or properly spaced sequences return true. Query [0,4]: [-12,-9,-3,-12,-6] cannot form arithmetic sequence due to duplicate -12.

Example 3 — Edge Case

$ Input: nums = [1,1,1], l = [0,1], r = [2,2]

› Output: [true,true]

💡 Note: Query 1: [1,1,1] with diff=0 forms arithmetic sequence. Query 2: [1] single element is trivially arithmetic.

Constraints

n == nums.length
m == l.length
m == r.length
2 ≤ n ≤ 500
1 ≤ m ≤ 500
0 ≤ l[i] < r[i] < n
-10⁵ ≤ nums[i] ≤ 10⁵

Visualization

Tap to expand

Understanding the Visualization

Input

Array nums and query ranges [l[i], r[i]]

Process

For each query, check if subarray can form arithmetic sequence

Output

Boolean array indicating which queries are arithmetic

Key Takeaway

🎯 Key Insight: After sorting, arithmetic sequences have constant differences between all consecutive elements

Asked in

G Google 15 f Facebook 12 a Amazon 8

The key insight is that any arithmetic sequence, when sorted, has equal differences between consecutive elements. The sort-and-check approach extracts each query range, sorts it, and verifies constant differences. Best approach is sorting with Time: O(m × k × log k), Space: O(k).

Common Approaches

Approach	Time	Space	Notes
✓ Sort and Check Each Query	O(m × k × log k)	O(k)	For each query, extract subarray, sort it, and verify arithmetic progression
Hash Set Validation	O(m × k)	O(k)	Use hash set to validate if elements can form arithmetic sequence efficiently

Sort and Check Each Query — Algorithm Steps

Step 1: For each query, extract subarray nums[l[i]...r[i]]
Step 2: Sort the extracted elements
Step 3: Check if all consecutive differences are equal

Visualization

Tap to expand

Step-by-Step Walkthrough

Extract Range

Get subarray for current query

Sort Elements

Sort the extracted elements

Check Differences

Verify all consecutive differences are equal

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

int compare(const void* a, const void* b) {
    return (*(int*)a - *(int*)b);
}

bool* solution(int* nums, int numsSize, int* l, int lSize, int* r, int rSize, int* returnSize) {
    bool* result = (bool*)malloc(lSize * sizeof(bool));
    *returnSize = lSize;
    
    for (int i = 0; i < lSize; i++) {
        // Extract subarray
        int subarraySize = r[i] - l[i] + 1;
        int* subarray = (int*)malloc(subarraySize * sizeof(int));
        for (int j = 0; j < subarraySize; j++) {
            subarray[j] = nums[l[i] + j];
        }
        
        // Sort the subarray
        qsort(subarray, subarraySize, sizeof(int), compare);
        
        // Check if it forms arithmetic sequence
        if (subarraySize <= 1) {
            result[i] = true;
        } else {
            bool isArithmetic = true;
            int diff = subarray[1] - subarray[0];
            
            for (int j = 2; j < subarraySize; j++) {
                if (subarray[j] - subarray[j-1] != diff) {
                    isArithmetic = false;
                    break;
                }
            }
            
            result[i] = isArithmetic;
        }
        
        free(subarray);
    }
    
    return result;
}

int main() {
    // Simple parsing for demonstration
    int nums[] = {4,6,5,9,3,7};
    int l[] = {0,0,2};
    int r[] = {2,3,5};
    int returnSize;
    
    bool* result = solution(nums, 6, l, 3, r, 3, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("%s", result[i] ? "true" : "false");
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(m × k × log k)

m queries, each with k elements requiring O(k log k) sort plus O(k) difference check

⚡ Linearithmic

Space Complexity

O(k)

Temporary array to store subarray elements for sorting

✓ Linear Space

89.2K Views

Medium Frequency

~25 min Avg. Time

1.5K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Sort and Check Each Query — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler