Length of largest substring adds up to S

Question

I was asked the following question in an interview and I couldn't give the optimal answer to this.

Problem: Write a program that can find the length of the largest contiguous sub-array that sums up to S. Given an array of variable size and an Integer.

Input: 1. An array of variable size, which can have only {-1, 0, 1} elements.

Example: A[] = {1, 0, 0, 1, -1, 1, 1, 1, 1}

2. An integer S,

Example: S = 4

Output: 8

Explanation: Largest contiguous sub-array of A that adds up to S=4: {1, 0, 0, 1, -1, 1, 1, 1} or {0, 0, 1, -1, 1, 1, 1, 1}

Constraint: Should complete in O(N)

I have solved the problem, but couldn't meet the time complexity. Can anyone help with a solution that can solve this in O(N).

PS: No Copyright issues with the question that I have asked.

Answer 1

Iterate though the array storing the total sum up to the current element in a variable. For each sum value, put it in a hash table in O(1) (if it isn't already there), mapping to which index it appeared.

But, before each insert, check if the hash table already contains current_sum - S. If it contains, that means that the subarray [previous_index+1..current_index] has sum S.

That works even if the array contains elements other than {-1, 0, 1}.

Here's an example Python code:

def solve(A, S):
    table = {0: 0}
    answer = None
    total = 0
    for i, x in enumerate(A):
        total += x
        if total - S in table:
            candidate = (table[total-S], i)
            if answer is None or candidate[1] - candidate[0] > answer[1] - answer[0]:
                answer = candidate
        if total not in table: 
            table[total] = i+1

    return answer

print solve([-1, 0, 1, 1, 1, 1, 1, 0, 0, 1], 4)