Finding the balancing point of a subsequence

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

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.

StackExchange Code Review Q#99031, answer score: 2