CODEWITHSUNDEEP
pythonzigzag
VINEET KUMAR
VINEET KUMAR

Reputation: 31

Longest zig-zag subsequence in a string

How can I optimize the below code that I have written for this problem? Can I get some suggestions?

Given an array of integer elements, find the length of the longest subsequence such that all elements are alternating. If a sequence {x1, x2, .. xn} is alternating sequence then its element satisfies one of the following relations:

x1 < x2 > x3 < x4 > x5 < …. xn

or

x1 > x2 < x3 > x4 < x5 > …. xn

Input:

8
10 22 9 33 49 50 31 60

where: First line represents the number of elements in the array. Second line represents the array elements.

Output:

6

Explanation:

The subsequence {10, 22, 9, 33, 31, 60} is in the format x1 < x2 > x3 < x4 > x5 < x6 i.e. { 10 < 22 > 9 < 33 > 31 < 60 } and it is the largest of this form and the length of this subsequence is 6, hence the output 6.

n = int(input())
L = []
for e in input().split():
    L.append(int(e))
count, i = 0, 0
flag = None
while i < (len(L) - 1):
    for j in range(i+1, len(L)):
        if count == 0 and flag is None:
            if (L[i] < L[j]):
                count+=1
                flag = 1
                i = j
                break
            elif (L[i] > L[j]):
                count+=1
                flag = 0
                i = j
                break
            else:
                i = j
        else:
            if (flag == 0) and (L[i] < L[j]):
                count+=1
                flag = 1
                i = j
                break
            elif (flag == 1) and (L[i] > L[j]):
                count+=1
                flag = 0
                i = j
                break
            else:
                i = j

print(count+1)

Upvotes: 0

Views: 386

Answers (2)

Timmy Chan
Timmy Chan

Reputation: 985

You can iterate the list while keeping a reference to the previous node that did not contribute to the alternating pattern.

We start at setting the prev_node as the first element in the list. The loop starts at index 1 and iterates till the end. For each value, it compares the value with prev_node. If it is of an alternating pattern, increment the max_lenght, and update prev_node.

LT = -1     # Less than
GT = 1      # Greater than

max_length = 1
prev_node = L[0]       # Begin at 0
prev_compare = 0
found = 0
for i in range(1, len(L)):
    if L[i] < prev_node:
        if prev_compare != LT:
            prev_compare = LT
            found = True
    elif L[i] > prev_node:
        if prev_compare != GT:
            prev_compare = GT
            found = True
    # If an alternating node is found
    if found:
        max_length += 1
        prev_node = L[i]
        found = False

print(max_length)
  • Time complexity: O(n), as it traverse the list only once.
  • Space complexity: O(1), as (additional) memory usage does not depend on input size.

EDIT #1

From your comments, I assume you don't really care much about readability of code.

I have a short version (in terms of character count) of the same algorithm as above. The logic is basically the same, thus the performance is the same.

nodes = [L[0]]
prev_compare = -1
for e in L[1:]:
    if e != nodes[-1] and (e > nodes[-1]) != prev_compare:
        prev_compare = e > nodes[-1]
        nodes += [e]

print(len(nodes))

Upvotes: 2

a_guest
a_guest

Reputation: 36289

You can use generators to perform the following checks:

  • whether for two consecutive numbers x and y it holds that x < y,
  • whether two consecutive < comparisons, c1 and c2, are alternating, i.e. c1 != c2.

Then you can find the longest sub-sequence for which the second check is True. Here we need to take into account that both checks consume one "length unit" from the original sequence, i.e. if we find that two consecutive < comparisons are alternating this will be indicated by a single True however it was generated by two comparisons. And these two comparisons in turn were generated by three consecutive numbers. So we can account for this by adding 2 to the final result.

Here's a code example:

import itertools as it
from more_itertools import pairwise

numbers = [...]  # input goes here

less_than = (x < y for x, y in pairwise(numbers))
alternating = (x != y for x, y in pairwise(less_than))
lengths = (
    sum(1 for _ in g)  # length of sub-sequence
    for k, g in it.groupby(alternating)
    if k  # check if it's an alternating sub-sequence
)
result = max(lengths, default=-1) + 2

Upvotes: 1

Related Questions