Arithmetic Sequence Queries ☃️ - Google Top Interview Questions

                        Solution in C++ :

int dp[100005];
int solve(vector<int>& nums, vector<vector<int>>& queries) {
    int n = nums.size();
    for (int i = 0; i + 1 < n;) {
        int j = i + 1;
        while (j + 1 < n && nums[j + 1] - nums[j] == nums[i + 1] - nums[i]) j++;
        for (int k = i; k < j; k++) dp[k] = j - k;
        i = j;
    }
    int ret = 0;
    for (auto& q : queries) {
        if (dp[q[0]] >= q[1] - q[0]) ret++;
    }
    return ret;
}
                    

                        Solution in Java :

import java.util.*;

class Solution {
    public int solve(int[] nums, int[][] queries) {
        HashMap<Integer, Integer> hm = new HashMap();

        // length of arithmetic subsequence dp

        int n = nums.length;

        hm.put(n - 1, 1);
        hm.put(n - 2, 2);

        for (int i = n - 3; i >= 0; i--) {
            int this_diff = nums[i] - nums[i + 1];
            int next_diff = nums[i + 1] - nums[i + 2];

            if (this_diff == next_diff) {
                hm.put(i, 1 + hm.get(i + 1));
            } else {
                hm.put(i, 2);
            }
        }

        int res = 0;
        for (int[] q : queries) {
            int left = q[0];
            int right = q[1];
            if (hm.get(left) >= (right - left + 1)) {
                res++;
            }
        }
        return res;
    }
}
                    

                        Solution in Python : 
                            
class Solution:
    def solve(self, nums, queries):
        if not nums:
            return 0

        # preprocessing

        n = len(nums)
        # compute pairwise differences
        diff = [nums[i + 1] - nums[i] for i in range(n - 1)]
        # "run-length encoding": `rle[i]` is length of the longest constant sublist
        # of `diff` ending at (and including) `i`)
        rle = [0] * (n - 1)
        for i in range(n - 1):
            if i > 0 and diff[i] == diff[i - 1]:
                rle[i] = rle[i - 1] + 1
            else:
                rle[i] = 1

        # answer queries

        ans = 0
        for i, j in queries:
            # `nums[i:j+1]` is an arithmetic sequence iff `diff[i:j]` is constant
            if i == j:
                ans += 1
            else:
                ans += rle[j - 1] >= (j - i)
        return ans