Rearrange Array in Zigzag Order

Title: Rearrange Array in Zigzag Order

In this guide, we will explore how to rearrange an array in Java so its elements alternate between smaller and larger values, a pattern known as a zigzag sequence. This is a popular interview question because it tests whether you can reason about an element in relation to its neighbors instead of sorting the whole array.

By the end of this article, you will understand a single-pass swapping technique that produces a zigzag array in linear time, see a complete working Java program, and walk through a step-by-step trace so the logic is easy to follow.

Understanding the Problem

Given an array of integers, we need to rearrange its elements so they follow a zigzag pattern. In a zigzag array, the element at every even index is smaller than its neighbors, and the element at every odd index is larger than its neighbors. In other words, the array should satisfy arr[0] < arr[1] > arr[2] < arr[3] > arr[4] and so on.

For example, one valid zigzag rearrangement of [4, 3, 7, 8, 6, 2, 1] is [3, 7, 4, 8, 2, 6, 1], where every valley is followed by a peak. Most inputs have more than one correct answer; any arrangement that alternates correctly is accepted.

Approach

The key insight is that we only ever need to compare two neighboring elements at a time and swap them if they violate the expected relation. Here are the steps:

1. Start with a boolean flag such as less = true, since arr[0] is expected to be smaller than arr[1].
2. Walk through the array from index 0 to the second-to-last index.
3. If the flag expects arr[i] < arr[i + 1] but arr[i] > arr[i + 1] instead, swap the two elements.
4. If the flag expects arr[i] > arr[i + 1] but arr[i] < arr[i + 1] instead, swap the two elements.
5. If neither violation occurs, leave the pair untouched.
6. Flip the flag after every comparison, so the next pair is checked against the opposite relation.
7. Continue until the loop reaches the last pair of elements.
8. The array is now rearranged in zigzag order, in place, with no extra storage.

Java Program

Here is the complete Java program that implements the zigzag rearrangement using the single-pass swapping technique described above:

import java.util.Arrays;

public class ZigzagArray {

    public static void rearrangeZigzag(int[] arr) {
        boolean less = true;

        for (int i = 0; i < arr.length - 1; i++) {
            if (less) {
                if (arr[i] > arr[i + 1]) {
                    swap(arr, i, i + 1);
                }
            } else {
                if (arr[i] < arr[i + 1]) {
                    swap(arr, i, i + 1);
                }
            }
            less = !less;
        }
    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        int[] arr = {4, 3, 7, 8, 6, 2, 1};

        rearrangeZigzag(arr);

        System.out.println(Arrays.toString(arr));
    }
}

Explanation of the Program

The rearrangeZigzag method does all the work. It loops through the array once, using the boolean less to track whether the current pair should satisfy < or >.

• The flag less starts as true, meaning arr[0] is expected to be smaller than arr[1].
• Inside the loop, when less is true and arr[i] > arr[i + 1], the pair is out of order, so the helper method swap exchanges them.
• When less is false and arr[i] < arr[i + 1], the pair is also out of order for a peak position, so swap is called again.
• After every comparison, less is flipped with less = !less, so the expected relation alternates for the next pair.
• The private swap method performs a standard three-step exchange using a temporary variable, which keeps the rearrangement in place without allocating a new array.

Step-by-Step Trace

Let’s trace the algorithm on a fresh input, [10, 5, 6, 3, 2, 20, 2], to see exactly when a swap happens and when a pair is already in the right shape.

At the end of iteration i, the subarray arr[0..i + 1] already satisfies the zigzag pattern, so every later swap only ever touches the newest pair being examined.

Examples

The following examples show how the same rearrangeZigzag method behaves on inputs that are already zigzag, inputs with duplicate values, and the smallest possible array that can be rearranged.

Example 1: Already Zigzag-Ordered Array

When the input is already a valid zigzag sequence, the comparisons never find a violation, so the array comes back unchanged.

int[] arr = {1, 4, 2, 5, 3};
rearrangeZigzag(arr);
System.out.println(Arrays.toString(arr));
// Output: [1, 4, 2, 5, 3]

Example 2: Array With Duplicate Elements

Strict inequalities mean equal neighbors never count as a violation, so an array of identical elements is left untouched as well.

int[] arr = {5, 5, 5, 5, 5};
rearrangeZigzag(arr);
System.out.println(Arrays.toString(arr));
// Output: [5, 5, 5, 5, 5]

Example 3: Smallest Possible Input

With only two elements, the loop runs exactly once. If the first element is larger than the second, a single swap is enough to satisfy the zigzag rule.

int[] arr = {9, 1};
rearrangeZigzag(arr);
System.out.println(Arrays.toString(arr));
// Output: [1, 9]

Common Mistakes to Avoid

A few mistakes come up often when learners implement this pattern for the first time:

• Flipping the flag only inside the swap branch. If less = !less only runs when a swap happens, the same relation keeps getting checked on every unmodified pair, and the output stops alternating partway through the array. Flip the flag unconditionally after every comparison, inside or outside the if.
• Using >= or <= instead of strict comparisons. On an array like [5, 5, 5], non-strict operators force needless swaps that never change the final pattern. Keep the comparisons strict so equal neighbors are left alone.
• Looping to arr.length instead of arr.length - 1. Reading arr[i + 1] on the last index throws ArrayIndexOutOfBoundsException. Stop the loop one index early.
• Assuming the flag must start as true. Starting with less = false produces an equally valid zigzag pattern that begins with a peak instead of a valley; forgetting this makes a correct alternate output look like a bug.

Edge Cases to Test

Before you consider the implementation complete, make sure it behaves correctly on these inputs:

• Empty array
• Single-element array
• Two-element array
• All identical elements
• Already zigzag-ordered array
• Strictly increasing array
• Strictly decreasing array
• Integer.MIN_VALUE and Integer.MAX_VALUE present

Additional Considerations

The algorithm runs in O(n) time because it makes exactly one pass over the array, comparing and possibly swapping each adjacent pair once. It uses O(1) extra space, since the rearrangement happens in place with only a temporary variable inside swap.

Because Integer.MIN_VALUE and Integer.MAX_VALUE are only ever compared, never added or subtracted, they do not introduce the overflow risk that expressions like a - b would. That makes this approach safe to use even when extreme boundary values are present in the array.

Interview Follow-up Questions

Once you can explain the base solution, be ready for interviewers to push further with questions like these:

• What if the array is already sorted? The same single pass still produces a valid zigzag arrangement; no special-casing is needed because the algorithm only ever looks at adjacent pairs.
• What if duplicate values must never sit adjacent in the result? Detect equal neighbors before applying the swap rule and resolve the tie with a fixed direction, such as always treating an equal pair as satisfying the current expectation.
• What if the input is read-only and you cannot mutate it in place? Copy the array first, then run the same swap logic on the copy, since any in-place rearrangement by definition needs writable storage.
• What if the array arrives as a stream of unknown length? Buffer only the two most recently seen elements and apply the same flag-toggle comparison as each new value streams in, emitting a swap decision immediately instead of waiting for the whole array.

Conclusion

Rearranging an array into zigzag order is a great example of how a single pass with a toggling condition can replace a more complex sorting-based approach. By comparing only adjacent elements and flipping an expectation flag, the rearrangeZigzag method produces a valid zigzag pattern in linear time and constant extra space.

Try adapting this pattern to the follow-up questions above, especially the streaming variant, since it is a natural extension interviewers like to probe. You can learn more Java array programs in the Arrays category.