Function to Create a Zigzag Array in Python

Question

I'm trying to create an array of positive and negative integers, representing distances north and south of a location - I need to see the elements of the array in zigzag order.

This means that the largest member appears first, the smallest member appears second, and the remaining elements alternate between the larger members decreasing from the largest and the smaller members increasing from the smallest.

I.e. the array [1, 3, 6, 9, -3] becomes [9, -3, 6, 1, 3].

I'm trying to complete the function wiggleArrangeArray, which takes one argument, an integer array of n integers.

Required Input Format, Constraints, and Output Format

I'm not sure how to say

"if the item in the array is larger than the other items in the array, display it first."

"if the item is smaller than the other items in the array, display it second."

"then alternate between the next largest numbers, and the next smallest numbers"

def wiggleArrangeArray(intArr):
    for i in intArr
        #if i > other items in intArr
        #display that i at index value 0
        #if i < other items in intArr
        #display that i at index value 1
        #if i < i at index value 0 and > other items in intArr, display it next
        #if i > i at index value 1 and < other items in intArr, display it next
        #repeat last two lines for continuing values

Please help if possible. Here's a link to the solution in C++ but I need it in Python. Thanks.

Edit: The function needs to work with the following tests:

f = open(os.environ["OUTPUT_PATH"], "w")

_intArr_cnt = int(raw_input())
_intArr_i=0
_intARR = []
while _intArr_i < _intArr_cnt:
    _intArr_item = int(raw_input());
    _intArr.append(_intArr_item)
    _intArr_i+=1

res = wiggleArrangeArray(_intArr);
for res_cur in res:
    f.write( str(res_cur) + "\n" )

f.close()

Answer 1

The altered C++ code

Note the algorithm you provided does calculate some sort of zigzag, but it is not the zigzag you are looking for. For future reference I will leave it here.

In the C++ code you provided, they only look for a sequences that satisfies a < b > c < d > e < f, you are looking however for a sequence with the 1-max, 1-min, 2-max, 2-min,...

Your link provides you a solution which you can copy nearly verbatim in Python. You only define a swap function:

def swap(arr,i,j):
    t = arr[i]
    arr[i] = arr[j]
    arr[j] = t

Next you can simply modify the code:

def zigZag(arr):
    n = len(arr)
    # Flag true indicates relation "<" is expected,
    # else ">" is expected.  The first expected relation
    # is "<"
    flag = True

    i = 0
    while i<= n-2:
        if (flag):  # "<" relation expected
            # If we have a situation like A > B > C,
            # we get A > B < C by swapping B and C
            if arr[i] > arr[i+1]:
                swap(arr,i,i+1)
        else: # ">" relation expected
            # If we have a situation like A < B < C,
            #  we get A < C > B by swapping B and C
            if arr[i] < arr[i+1]:
                swap(arr,i,i+1)
        flag = not flag # flip flag
        i += 1

Mind that this is rather un-Pythonic, so you can simply improve it like:

def swap(arr,i,j):
    arr[i],arr[j] = arr[j],arr[i]

def zigZag(arr):
    n = len(arr)
    for i in range(len(arr)-1):
        if not i&1:
            if arr[i] > arr[i+1]:
                swap(arr,i,i+1)
        elif arr[i] < arr[i+1]:
            swap(arr,i,i+1)
    return arr

Here tuple assignment is used to swap elements in the list, a range is used to iterate over the indices, we can furthermore use an elif instead of an if in an else, and for I've abandoned the flag by using a modulo check.

Your zigzag function

You can simply solve the problem by sorting the list, and using two pointers that each time emit the most left, the most right and walk towards each other. In other words something like:

def zigZag(arr):
    srt = sorted(arr)
    left = 0
    right = len(srt)-1
    result = []
    while left < right:
        result.append(srt[right])
        right -= 1
        if left < right:
            result.append(srt[left])
            left += 1
    return result

Answer 2

Here Python implementation example.

1. Sort your data in reversed order (9, 6, 3, 1, -3)
2. Split by two lists (9, 6) (3, 1, -3)
3. Iterate over both (using zip_longest) first one from start, second in reverse order (9, -3), (6, 1) (None, 3)
4. Unpack tuples created by zip_longest (chain(*zip...)) so you get iterable data (9, -3, 6, 1, None, 3)
5. Remove None value in case if the list has an odd number of elements (if x is not None)

Example:

from itertools import zip_longest, chain


def zig_zag_array(data):
    data = sorted(data)
    mid = len(data) // 2
    return [
        x for x in chain(*zip_longest(data[mid:][::-1], data[:mid])) if x is not None
    ]

Test:

if __name__ == "__main__":
    data = [1, 3, 6, 9, -3]
    expected = [9, -3, 6, 1, 3]
    output = zig_zag_array(data)
    assert output == expected, f"Odd length: {output=}"

    data = [1, 3, 6, 9, -3, 0]
    expected = [9, -3, 6, 0, 3, 1]
    output = zig_zag_array(data)
    assert output == expected, f"Even length: {output=}"
    print("PASSED")