less than 1 minute read

Computing an Alternation - Elements of Programming Interviews (EPI)

Problem:

Write a program that takes an array \(A\) of \(n\) numbers and rearranges it such that: \(A[0] \leq A[1] \geq A[2] \leq A[3] \geq A[4] ...\)

Solution:

Brute force solution would be to sort \(A\) and then separate it into 2 halves and interleave them. Another approach would be to rearrange around the median (?). Our approach is to only look at 2 elements at a time and swap if they don’t fulfill the criteria.

def rearrange(A: List[int]) -> None:
    """Function to rearrange elements in an array
    such that they are in an alternating order:
    A[i]>=A[i+1]<=A[i+2]>=A[i+3]<=..."""
    for i, element in enumerate(A[:-1]):
        if i % 2:
            A[i], A[i + 1] = (A[i + 1], A[i]) if A[i] < A[i + 1] else (A[i], A[i + 1])
        else:
            A[i], A[i + 1] = (A[i + 1], A[i]) if A[i] > A[i + 1] else (A[i], A[i + 1])
    return

The book’s solution compacts this into a line by using python’s sorted():

def rearrange(A: List[int]) -> None:

    for i in range(len(A)):
        A[i:i + 2] = sorted(A[i:i + 2], reverse=bool(i % 2))