Find the longest zigzag sequence in a array of integers

Question

I think I have a brute force solution to the problem but I can't think of a more optimal solution

A sequence of integers is called a zigzag sequence if each of its elements is either strictly less than both neighbors or strictly greater than both neighbors. For example, the sequence 4 2 3 1 5 3 is a zigzag, but 7 3 5 5 2 and 3 8 6 4 5 aren't. For a given array of integers return the length of its longest contiguous sub-array that is a zigzag sequence.

Example

For a = [9, 8, 8, 5, 3, 5, 3, 2, 8, 6], the output should be zigzag(a) = 4.

The longest zigzag sub-arrays are [5, 3, 5, 3] and [3, 2, 8, 6] and they both have length 4.

Input/Output
[input] array.integer a

constraints:
2 ≤ a.length ≤ 25,
0 ≤ a[i] ≤ 100.

Here is my brute force solution

def zigzag(input):
    current_longest = 0
    longest_subset  = []
    input_length    = len(input)

    for x in range(input_length):
        current_list = input[x:]

        for pos_a, num_a in enumerate(current_list):
            subset      = [num_a, ]
            prev_trend  = None

            for pos_b, num_b in enumerate(current_list[pos_a + 1:]):
                last_number = subset[-1]

                if last_number == num_b:
                    # print "[DUPE] current subset state", subset, "comparing ->", subset[-1], num_b
                    break

                if last_number > num_b:
                    cur_trending = "down"
                else:
                    cur_trending = "up"

                if prev_trend:
                    # compare trends
                    if prev_trend == cur_trending:
                        # print "[TREND] current subset state", subset, "comparing ->", subset[-1], num_b
                        break
                    else:
                        prev_trend = cur_trending
                else:
                    # initial trend set
                    prev_trend = cur_trending

                subset.append(num_b)

                if len(subset) > current_longest:
                    current_longest = len(subset)
                    longest_subset = subset

    print current_longest, longest_subset

zigzag([9, 8, 8, 5, 3, 5, 3, 2, 8, 6])
zigzag([4, 2, 3, 1, 5, 3])

Answer 1

You can do this in \$O(n)\$ rather than \$O(n^3)\$. To force this, change input to an iterator. I'd also make a function that returns all the zigzags, so for [9, 8, 8, 5, 3, 5, 3, 2, 8, 6] it'd return [(9, 8), (8,), (8, 5), (5, 3, 5, 3), (3, 2, 8, 6)].

The reason you'd want to do this, is as you can then make zigzag a three line function, and you know that you're building actual zigzags of the maximum size.

There's a fairly simple algorithm that you can follow to build the zigzags:

1. Go through the input.
2. If two adjacent items are the same, yield the current zigzag, and a new zigzag only containing that duplicate item.
3. If three adjacent items don't zigzag, yield the current zigzag, and start a new zigzag starting at the second item.

In more depth, I achieved this by doing:

1. Build a stack, and add the first number to it.
2. Loop until you run out of items in input:
   1. Force the stack to be a size of two. If it contains three items, only keep the last two. If it has one item, add an item from the input to it.
   2. If the first item in the stack, is the same as the second item in the stack, yield the first item, and make a stack that only contains the second item. Restart the loop.
   3. Store the direction of the zigzag. (find if item 1 > item 2 for example.)
   4. Infinitely do:
      1. Copy the previous item from the stack.
      2. Get a new item from the input.
      3. If the previous or current item are the same, or they are the same direction as the previous zigzag, then stop looping.
      4. Add the current item to the stack.
      5. Store the current state of the zigzag.
   5. yield the stack as a tuple. (Don't want people mutating the data.)
   6. Add the current item to the stack.
3. If the stack has been initialized and contains items, yield the stack as a tuple.

Which can be implemented as:

def zigzags(input):
    input = iter(input)
    stack = None
    try:
        stack = [next(input)]
        while True:
            if len(stack) < 2:
                stack.append(next(input))
            else:
                stack = stack[-2:]
            a, b = stack
            if a == b:
                yield (a,)
                stack = [b]
                continue
            zig = a > b
            while True:
                prev = stack[-1]
                this = next(input)
                if prev == this or zig == (prev > this):
                    break
                stack.append(this)
                zig = not zig
            yield tuple(stack)
            stack.append(this)
    except StopIteration:
        pass
    if stack:
        yield tuple(stack)

def zigzag(input):
    item = max(zigzags(input), key=len)
    print len(item), item

Answer 2

I think your program is needlessly complicated with three nested loops. I think the function zigzag can do with one loop from 1 to len(input)-1 and another function like is_zigzag(prev, current, next) or something like that might be useful... and some careful administration of current and max zigzag lengths...

Try something before looking at my quick solution:

def is_zigzag(prev, current, next):
    '''
    returns true if both prev and next are either bigger or smaller
    than current
    '''
    return ((prev < current and next < current)  or
            (prev > current and next > current))

def zigzag(test_array):
    '''
    For a given array of integers return the length of its longest 
    contiguous sub-array that is a zigzag sequence.
    '''
    max_zigzag_length = 0
    current_zigzag_length = 0

    for i in range(1, len(test_array)-1):

        if is_zigzag(test_array[i-1], 
                     test_array[i  ], 
                     test_array[i+1]):

            current_zigzag_length += 1
            max_zigzag_length = max(current_zigzag_length, max_zigzag_length)

        else:

            current_zigzag_length = 0

    return max_zigzag_length


print(zigzag([9, 8, 8, 5, 3, 5, 3, 2, 8, 6]))
print(zigzag([4, 2, 3, 1, 5, 3]))

Answer 3

As already noted, your code suffers from unnecessary computational complexity. I'd like to propose a compact alternative solution.

pairwise from Itertools recipes comes in very handy here for comparing adjacent items:

>>> [cmp(a, b) for a, b in pairwise([9, 8, 8, 5, 3, 5, 3, 2, 8, 6])]
[1, 0, 1, 1, -1, 1, 1, -1, 1]

This would result in alternating 1 and -1 for a complete zigzag sequence. Zeros and repeating values mark positions between zigzags. To detect repeating values, we can again make use of pairwise to process the result.

Solution:

def pairwise_cmp(iterable):
    yield 0
    for a, b in pairwise(iterable):
        yield cmp(a, b)
    yield 0

def zigzags(seq):
    start = 0
    for i, (a, b) in enumerate(pairwise(pairwise_cmp(seq))):
        if b == 0 or a == b:
            yield seq[start:i + 1]
            start = i if b else i + 1 

def zigzag(input):
    longest = max(zigzags(input), key=len)
    print len(longest), longest

N.B. Python 3 users must roll their own cmp