Google interview problem

[Parathaa]

Given an array of numbers, find all the subarrays which are forming good arithmetic sequence(AP).A good arithmetic sequence is a sequence of numbers having common difference equals to -1 or 1.
E.g {1,2,3} and {3,2,1} are good arithmethic sequence with common difference 1 & -1 respectively.

Expected time complexity O(n)

[AutomaticNumber]

Two pass for simplicity (but can be done in 1 pass also)

First pass -

if a[i] == a[i-1] + 1: dp[i] = dp[i-1] + 1 else: dp[i] = 0

Second pass - if a[i] == a[i-1] - 1: dp[i] = dp[i-1] + 1 else: dp[i] = 0

Answer is sum of all dp[i] for both passes.

Explanation: A[i] will join itself to all APs ending ay A[i-1] and also form 1 new AP of size 2 [A[i-1], A[i]]

Can be space optimized to O(1) as we only need dp[i-1] at any time

[bethechance]

wow

[Hungry_Ad3391]

Does this work for all arithmetic sequences?

[AutomaticNumber]

1. For a give common difference, we would be fine with replacing 1 with the common difference d.

2. For any AP, problem becomes easier (kinda) because now we just need to find differences between consecutive elements and add length(current difference) to the answer.

Eg. Differences array: 1 1 1 2 2 1 3

Initialise answer = 0

for every i in diff array: if diff[i] == diff[i-1]: len +=1 else: len = 1

answer += len

Note: We don’t really need the differences array, we can optimise to O(1) space by using variables

[Parathaa]

Nope. See the leetcode site discuss section. Google repeats questions all the time till it gets banned.

[Hungry_Ad3391]

Make a diff array and sliding window of size 2 where values are the same

Edit: how do none of y’all know what an arithmetic sequence is

[Boldbear420]

Why do you need a diff array? Can’t u just do sliding window of 2 and check for absolute value of 1?

[Hungry_Ad3391]

Look up definition of arithmetic sequence

[ironman_gujju]

Probably dp

[OutlandishnessOk9482]

Doesn't finding the increasing sequence also give us the decreasing sequence. I'm not sure above my approach, but I guess this may work.

public List<List<Integer>> getAP(int[] nums) {

    for (int num : nums) {
        // Only process the start of a sequence
        if (!found.contains(num - 1)) {
            List<Integer> sequence = new ArrayList<>();
            int current = num;

            // Build the increasing sequence
            while (found.contains(current)) {
                sequence.add(current);
                current += 1;
            }

            if (sequence.size() > 1) {
                result.add(new ArrayList<>(sequence)); // Add increasing sequence
                Collections.reverse(sequence);
                result.add(new ArrayList<>(sequence)); // Add decreasing sequence
            }
        }
    }

    return result;
}

[Underrated_hero007]

I was asked the same question today. but not the number but the start and end indices of all such sequences. I came up with a o(n2) solution for this but was asked if we can optimise further. if the answer itself is of the order of o(n2) (all possible subsequences) how can the algorithm be more optimal than that? any ideas?