educative.io

Shorter variant

Courses
,
#1

Proposal:

def maxMin(lst):
  for i in range(0, len(lst), 2):
    lst.insert(i, lst.pop())
  return lst
1 Like
#2

Hi Dennis,

Thank you for you feedback.

We’ll review your proposal and get back to you as soon as possible.

Regards,
Arqam Rehan

#3

Hey Dennis,

This is a great solution as it is very Pythonic and takes constant space. However, the only reservation I have is that it seems that insert() takes O(n) in the average case. and since insert occurs n/2 times, the time complexity comes out to be O(n^2) which isn’t optimal. A caveat though: Python has not officially declared the time complexity of the insert() function, the wiki page says that it is in O(n). So you might be able to use this fact to get away with this solution in an interview!

Best Regards,
Ayesha Basit | Technical Content Developer

2 Likes
#4

I have a similar solution:

def max_min(lst):
    # Write your code here
    ln = len(lst)
    popped = 0
    for i in range(ln):
        if (i + popped) == ln:
            break
        last = lst.pop()
        lst = lst[:i+popped]+[last]+lst[i+popped:]
        popped += 1
    return lst
1 Like
#5

You can also use two pointers to build the output (using an extra list):

def max_min(lst):
    # sorted list
    n=len(lst)
    
    res = []
    left =0
    right=n-1
    isOdd = False
    while left <= right:
        if not isOdd:
            res.append(lst[right])
            right -= 1
        else:
            res.append(lst[left])
            left += 1
        isOdd = not isOdd
    return res
1 Like