4
\$\begingroup\$

Codeforces problem 831A says:

Array of integers is unimodal, if:

  • it is strictly increasing in the beginning;
  • after that it is constant;
  • after that it is strictly decreasing.

The first block (increasing) and the last block (decreasing) may be absent. It is allowed that both of this blocks are absent.

For example, the following three arrays are unimodal: [5, 7, 11, 11, 2, 1], [4, 4, 2], [7], but the following three are not unimodal: [5, 5, 6, 6, 1], [1, 2, 1, 2], [4, 5, 5, 6].

Write a program that checks if an array is unimodal.

I solved this using two methods in python3.5. I was expecting method 2 to be faster than method 1 but auto-grader showed the opposite. So, I wanted to know the reason that what makes the difference here?

Method 1

a, lst = int(input()), input().split()

lst = [int(ch) for ch in lst]

def f(m, n, flag):
    if flag == 1:
        return m < n
    elif flag == 2:
        return m == n
    else:
        return m > n


def is_modal(a, lst):
    flag = 1
    for i in range(1, a):
        if f(lst[i - 1], lst[i], flag):
            continue
        else:
            if flag == 3:
                return "NO"
            flag += 1
            if f(lst[i - 1], lst[i], flag):
                continue
            else:
                if flag == 3:
                    return "NO"
                flag += 1
                if f(lst[i - 1], lst[i], flag):
                    continue
                else:
                    return "NO"
    return "YES"

print(is_modal(a, lst))

It seems to be overly complicated to me, at first I solved it in this way but I did not like it so I tried another way, hence came at method 2.

Method 2

a, lst = int(input()), input().split()
lst = [int(ch) for ch in lst]


def is_modal(a, lst):
    i = 1
    for i in range(i, a):
        if not (lst[i - 1] < lst[i]):
            break
    else:
        return "YES"

    for i in range(i, a):
        if not (lst[i - 1] == lst[i]):
            break
    else:
        return "YES"

    for i in range(i, a):
        if not (lst[i - 1] > lst[i]):
            return "NO"
    else:
        return "YES"

print(is_modal(a, lst))

It looks cleaner and simpler but still, it came out to be slower one.

And apart from comparing these codes, any other suggestions are also welcome.

\$\endgroup\$

1 Answer 1

5
\$\begingroup\$

The following code is similar to your method 2:

def is_unimodal(seq):
    i = 1
    end = len(seq)
    while i < end and seq[i - 1] < seq[i]:
        i += 1
    while i < end and seq[i - 1] == seq[i]:
        i += 1
    while i < end and seq[i - 1] > seq[i]:
        i += 1
    return i == end

This code probably looks more like C than Python, but I expect it to be fast and readable.

\$\endgroup\$
1
  • \$\begingroup\$ @GarethRees It looks much better than method 2, why is it slower? \$\endgroup\$ Jul 15, 2017 at 17:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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