12
\$\begingroup\$

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
\$\endgroup\$
  • 1
    \$\begingroup\$ Does B have to be a particular length? (And why are you breaking if len(A) <= 5? Must it be a strict subsequence?) \$\endgroup\$ – alexwlchan Aug 5 '15 at 6:32
  • \$\begingroup\$ @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. \$\endgroup\$ – user2916286 Aug 5 '15 at 13:55
  • \$\begingroup\$ Is len(A) % 2 always True? I.e. does A always have an odd number of elements? \$\endgroup\$ – Curt F. Aug 5 '15 at 14:15
  • \$\begingroup\$ @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. \$\endgroup\$ – user2916286 Aug 5 '15 at 14:26
  • \$\begingroup\$ 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]? \$\endgroup\$ – smac89 Aug 6 '15 at 1:31
2
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.