Finding the balancing point of a subsequence

Question

This is a little tricky to explain, so bear with me.

Suppose you have an integer X and a list of integers A. Let A` be a copy of A where all values A[i] != X are replaced by -X. For example,

X = 5
A = [1, 3, 5, 5, 1, 5, 4, 1, 8]

would result in

A` = [-5, -5, 5, 5, -5, 5, -5, -5, -5]

The task is to find a subsequence B of A` that sums to 0 when the middle item of B is removed from the summation. With the previous example we would have

B = [-5, 5, 5, -5, 5, -5, -5]

where the middle item is -5 at index 4 (of A`). Splitting that into two lists generates

[-5, 5, 5] | [5, -5, -5]

which clearly sum to 0. If such a subsequence B exists then the program should return the index of that middle value, plus 1. In this case the return value would be 5.

I have a working solution, however it has pretty bad time complexity:

4.64179955720276e-05 for 15 elements

0.003033149677870525 for 115 elements

0.15060318663344355 for 1015 elements

13.662074328908023 for 10015 elements

It is supposed to scale up to 100,000 elements, and I think that would take about 19 minutes in the current state. I'd greatly appreciate any suggestions on how I could simplify, improve, and speed up my algorithm.

from collections import deque
def equi ( trim_list ):
 popped_total = sum(trim_list)
 j = popped_total
 k = 0
 center = 0
 for elem in trim_list:
 j = j - elem
 if j+k == 0:
 return center + 1 # list index of sequence middle index
 k = k + elem
 center += 1
 return -1 # no match found
def solution(X, A):
 # Break from function because list too small
 if not len(A) > 5:
 return -1
 # zero out non X values into reciprocal for equality approach
 # use deque for efficient 0 index removal Lifo queue also works
 equi_deque = deque(X if elem is X else 0 for elem in A)
 # iterate through deque and pop values if they fail an equality check
 while len(equi_deque) > 4:
 # is_sequence = equality_point(X, equi_deque)
 is_sequence = equi(list(equi_deque))
 # if value did not fail return index
 if is_sequence != -1:
 # use offset to account for prior elements popped
 return len(A) - len(equi_deque) + 1
 equi_deque.popleft()
 return -1

• alexwlchan: Does B have to be a particular length? (And why are you breaking if len(A) <= 5? Must it be a strict subsequence?)
• user2916286: @alexwlchan I have the length >= 5 because you can't achieve equality on lists that have an even numbered length and a list can't achieve equality when it is <= 3.
• Curt F.: Is len(A) % 2 always True? I.e. does A always have an odd number of elements?
• user2916286: @CurtF. The length of List A, the provided argument can be of any size however the sequence that you find will always be odd because you have to split the sequence into 2 distinct lists down the center, dropping the middle index.
• smac89: Why can't you achieve equality on lists with length = 3? What is the sum of this list when I remove the middle value [-1, 1, 1]?

Answer 1

Without messing with your actual algorithm, right now it's effectively \$O(n^2)\$.

• Creating the initial deque is \$O(n)\$
• The while loop is essentially \$O(n)\$ (worst case)
• Within the while loop you call equi with successively smaller lists \$k=(n, n-1, n-2, \dots, n-5)\$ and equi is \$O(k)\$ (worst case).

So the loop is \$O(n^2)\$ and dominates.

You can get some improvement in running time vs complexity though (maybe 20%) by fixing this line:

is_sequence = equi(list(equi_deque))

to be

is_sequence = equi(equi_deque)

The conversion to a list is unnecessary, and is an \$O(k)\$ operation.