Find the longest zigzag sequence in a array of integers

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])


3 Answers

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

• wow thanks for the detailed answer. I'm going to need some time to digest all this info! – Bobloblawlawblogs May 27 '17 at 21:38
• @Peilonrayz and @Bobloblawlawblogs I like the yield keyword, but at three different indentation levels in one function? I get confused, what would you tell rubber duck. – Jan Kuiken May 27 '17 at 23:03
• @JanKuiken What do you mean by 'three different indentation levels'? I'd also tell them the two different descriptions in my answer, :) It's not the prettiest, and I'm somewhat thinking on posting it as a question, :) – Peilonrayz May 27 '17 at 23:07

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]))

• Just to note, the question also outputs the sublist, which yours doesn't. "print current_longest, longest_subset" – Peilonrayz May 28 '17 at 1:25
• <gd&r> print(test_array) will output the sublist... – Jan Kuiken May 28 '17 at 15:57
• Huh, test_array = [9, 8, 8, 5, 3, 5, 3, 2, 8, 6]; print(zigzag(test_array)); print(test_array) outputs 2 and [9, 8, 8, 5, 3, 5, 3, 2, 8, 6], both which are wrong. – Peilonrayz May 28 '17 at 18:37

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