C++ Two Approaches (140 vs 28ms)
My initial thought was that we could do some smart precomputing, so our queries are O(1) or O(log n). But then it felt too hard, so I looked at the problem cons
My initial thought was that we could do some smart precomputing, so our queries are O(1) or O(log n). But then it felt too hard, so I looked at the problem constraints and realized that O(n) (or even quadratic) for each query should do.\n\n#### Approach 1: Sort\nThe first approach is to copy numbers into an aux array, sort that array, and then check if it forms a sequence.\n\n**C++**\n```cpp\nvector<bool> checkArithmeticSubarrays(vector<int>& nums, vector<int>& l, vector<int>& r) {\n    vector<bool> res;\n    for (auto i = 0, j = 0; i < l.size(); ++i) {\n        vector<int> n(begin(nums) + l[i], begin(nums) + r[i] + 1);\n        sort(begin(n), end(n));\n        for (j = 2; j < n.size(); ++j)\n            if (n[j] - n[j - 1] != n[1] - n[0])\n                break;\n        res.push_back(j == n.size());\n    }\n    return res;\n}\n```\n**Complexity Analysis**\n- Time: O(m * n * log n), where m is the number of queries. 140 ms runtime in OJ.\n- Memory: O(n) to make a copy of an array.\n#### Approach 2: Count Patterns\nThis is a bit more complicated, but helps avoid sorting the array. For each subarray, we determine the min and max elements. This will allow us to determine the pattern: `pat = (max - min) / (len - 1)`. Then, for the arithmetic sequence, `(nums[j] - min_e) / pat` will be the position of that number in the sequence. So, we can go through our subarray again, and check that all positions are filled. We can use a boolean array to do so; if we try to fill a position that has been already filled, we can terminate - the subarray does not form the sequence.\n\n**C++**\n```cpp\nvector<bool> checkArithmeticSubarrays(vector<int>& nums, vector<int>& l, vector<int>& r) {\n    vector<bool> res;\n    for (auto i = 0, j = 0; i < l.size(); ++i) {\n        auto [p_min, p_max] = minmax_element(begin(nums) + l[i], begin(nums) + r[i] + 1);\n        int len = r[i] - l[i] + 1, d = (*p_max - *p_min) / (len - 1);\n        if (*p_max == *p_min)\n             res.push_back(true);\n        else if ((*p_max - *p_min) % (len - 1))\n             res.push_back(false);\n        else {\n            vector<bool> n(len);\n            for (j = l[i]; j <= r[i]; ++j) {\n                if ((nums[j] - *p_min) % d || n[(nums[j] - *p_min) / d])\n                    break;\n                n[(nums[j] - *p_min) / d] = true;\n            }\n            res.push_back(j > r[i]);\n        }\n    }\n    return res;\n}\n```\n**Complexity Analysis**\n- Time: O(m * n), 28 ms runtime in OJ.\n- Memory: O(n / 32) for the boolean array.
[]