Determine the length of the largest contiguous segment

Question

Problem Link- https://www.hackerearth.com/challenges/competitive/october-circuits-19/algorithm/ap-1-f43562f4/

Problem Statement :

You are given an integer array of size A. You are also given queries Q. In each query, you are given three integers L, R, and D respectively.

You are required to determine the length of the largest contiguous segment in the indices range [L, R] of A that forms an arithmetic progression with a common difference of D

Note: The segment whose length is 1 always forms an arithmetic progression of a common difference D

Input format

  First line: Two space-separated integers N and Q respectively
  Second line: N space-separated integers denoting elements of A
  Next Q lines: Three space-separated integers L, R, and D (1<= L <= R <= N)       respectively

Output format

Print Q lines representing the answer such as the ith line denotes the answer for the ith query.

Constraints

1 <= N <= 200000
1 <= Ai <= 200000
-200000 <= D <= 200000

Sample Input

5 2
1 2 3 5 5
1 5 1
4 4 3

Sample Output
3
1

Explanation

For the first query, [1,2,3] forms an AP with difference 1.

For the second query, [5] forms an AP.

---

I was attempting to solve this problem on hacker earth, however for large size N and Q the following code exceeds the time limit. Is there any way I can make this code run faster, other than changing the algorithm?

N, Q = [int(x) for x in input().split()]

A = list(map(int, input().split()))

for testcase in range(Q):
    L, R, D = [int(x) for x in input().split()]

    if L == R:
        print("1")
        continue

    count_length = 0
    count_temp = 0

    for index in range(L, R):
        if A[index] == A[index-1] + D:
            count_temp += 1
            if index == R-1:
                count_temp += 1
                count_length = max(count_length, count_temp)

        else:
            count_temp += 1 # to include the first element of AP
            count_length = max(count_length, count_temp)
            count_temp = 0

    print(count_length)

Answer 1

Code Review

PEP 8

PEP 8 recommends snake_case for variable names, so N, Q, A, L, R, and D all violate the guidelines.

A space should be used around operators: index - 1 and R - 1

Unused variables

N and testcase are never used, so should be replaced with the throwaway _ variable.

Variable naming

N, Q, A, L, R, and D are all "almost meaningless". Yes, they are directly from the problem description, but you could do better naming them array_size, num_queries, array, left, right and difference.

Is count_length a count of lengths? Doesn't seem to be; it is more like a max_length.

Is count_temp a count of temporaries? Or is it more like a segment_length?

_, num_queries = [int(x) for x in input().split()]

array = list(map(int, input().split()))

for _ in range(num_queries):
    left, right, difference = [int(x) for x in input().split()]

    if left == right:
        print("1")
        continue

    max_length = 0
    segment_length = 0

    for index in range(left, right):
        if array[index] == array[index - 1] + difference:
            segment_length += 1
            if index == right - 1:
                segment_length += 1
                max_length = max(max_length, segment_length)

        else:
            segment_length += 1 # to include the first element of AP
            max_length = max(max_length, segment_length)
            segment_length = 0

    print(max_length)

Optimization

Without changing the Algorithm???

Ok, you're looking for just key-hole level optimizations. Let's see what we can do.

    for index in range(left, right):
        if array[index] == array[index - 1] + difference:
            ...
        else:
            ...

The above is inefficient code. Indexing into a list takes time, and you are doing it twice. Moreover, subtraction by 1 takes time, and it was to get the value which was looked up on the previous iteration!

Compare the above code with:

    prev = array[left - 1]
    for curr in array[left:right]:
        if curr == prev + difference:
            ...
        else:
            ...
        prev = curr

The indexing has been replaced with iteration over an array slice, and the current value from one iteration is carried forward to as the previous value in the next iteration. That should be a win, performance wise.

    segment_length = 0

    for ...:
        if ...:
            ...
            if ...:
                segment_length += 1
                max_length = max(max_length, segment_length)

        else:
            segment_length += 1 # to include the first element of AP
            max_length = ...
            segment_length = 0

Why are you starting the count from 0? That means you need this segment_length += 1 to account for that first element all the time. If you initialized segment_length = 1, you can skip that adjustment statement every time you reach the end of an arithmetic progression, saving another wee bit of time:

    segment_length = 1

    for ...:
        if ...:
            ...
            if ...:
                max_length = max(max_length, segment_length)

        else:
            max_length = ...
            segment_length = 1

Finally, the code I hate the most:

    for index in range(left, right):
        if ...:
            ...
            if index == right - 1:
                ...

        else:
            ...
        ...

When does the for loop end? After index loops the final time with index = right - 1, of course. So the only time this if condition will be true is during the last iteration of the loop. During all of the remaining loop iterations, you are wasting time, subtraction 1 from right and comparing the result to index, when it can't possibly ever be true. Simply move the code to follow the loop.

_, num_queries = [int(x) for x in input().split()]

array = list(map(int, input().split()))

for _ in range(num_queries):
    left, right, difference = [int(x) for x in input().split()]

    if left == right:
        print("1")
        continue

    max_length = 0
    segment_length = 1

    prev = array[left - 1]
    for curr in array[left:right]:
        if curr == prev + difference:
            segment_length += 1

        else:
            max_length = max(max_length, segment_length)
            segment_length = 1

        prev = curr

    max_length = max(max_length, segment_length)

    print(max_length)

With changing the Algorithm

You explicitly requested optimization without changing the algorithm, so I'll leave you to discover where there is an algorithmic improvement to be made.

Answer 2

Just for fun I tried implementing this using just generators and the itertools. Using this has the advantage that you don't have to pay the price for indexing multiple times (like in your code), but also not the price for copying the slices (like in @AJNeufeld's solution). It also means that instead of using an array, this function can deal with A being a generator (but of course in that case you could not make multiple queries on the same array).

• To get the range from the array, we can use itertools.islice, which works similarly to normal slicing (but without indexing from the end, because generators can be infinite).

• Finding the difference between elements is straight-forward when iterating over pairs of elements, which you can get with itertools.tee and advancing one of the resulting iterators.

• Finally, we need to run-length-encode the result and find the largest one where the chain of differences is the given difference. For this we can use itertools.groupby.

def graipher(array, left, right, difference):
    if left == right:
        return 1
    it = islice(iter(array), left - 1, right + 1)
    it1, it2 = tee(it)
    next(it1)
    differences = (a - b for a, b in zip(it1, it2))
    rle = (len(list(g)) for d, g in groupby(differences) if d == difference)
    try:
        return max(rle) + 1
    except ValueError:
        # empty sequence, none of the differences is correct
        return 1

Note that I put this code into a function that returns the result, instead of printing it. This makes it reusable, and testable. When doing the same to the other solutions, we can even compare the performance using some random test data:

For small slices (R - L small) this generator approach is the slowest of the three approaches, whereas for larger slices it is the second fastest. AJNeufeld's approach is consistently the fastest, tested up to \$10^6\$ in slice length, which is a magnitude larger than the constraints given in the problem description.

Nevertheless, all three solutions use inherently the same algorithm, iterating through all elements in the slice, and therefore have the same asymptotic behavior.