1. Problem Statement

Given a sorted array in ascending order, rearrange it in an alternating max/min form.

Input:
arr = [1, 2, 3, 4, 5, 6, 7]

Output:
[7, 1, 6, 2, 5, 3, 4]

Explanation:

• First element: maximum → 7
• Second element: minimum → 1
• Third element: second max → 6
• Fourth element: second min → 2
• and so on…

2. Approach

Step 1: Choose a multiplier (maxElem)

We need to store two values at each index:

• The current value (to retain)
• The new value (that will be placed there)

We choose:

maxElem = arr[n - 1] + 1 = 7 + 1 = 8

This ensures:

• All values in the array are < 8
• We can safely encode two numbers at the same index using a formula.

Step 2: Initialization

minIndex = 0
maxIndex = n - 1 = 6

Step 3: Encode values one by one

We use:

arr[i] = arr[i] + (valueToPut % maxElem) * maxElem

Then, at the end:

arr[i] = arr[i] / maxElem

This stores the new value inside the original using modular arithmetic.

Step 4: Pass-by-pass Breakdown

We go index-by-index:

i = 0 (even → take max element)

• value to put = arr[maxIndex] = 7
• arr[0] = arr[0] + (7 % 8) * 8 = 1 + 56 = 57
• Decrease maxIndex to 5

i = 1 (odd → take min element)

• value to put = arr[minIndex] = 1
• arr[1] = arr[1] + (1 % 8) * 8 = 2 + 8 = 10
• Increase minIndex to 1

i = 2 (even → max)

• value to put = arr[maxIndex] = 6
• arr[2] = 3 + (6 % 8) * 8 = 3 + 48 = 51
• maxIndex → 4

i = 3 (odd → min)

• value to put = arr[minIndex] = 2
• arr[3] = 4 + (2 % 8) * 8 = 4 + 16 = 20
• minIndex → 2

i = 4 (even → max)

• value to put = arr[maxIndex] = 5
• arr[4] = 5 + (5 % 8) * 8 = 5 + 40 = 45
• maxIndex → 3

i = 5 (odd → min)

• value to put = arr[minIndex] = 3
• arr[5] = 6 + (3 % 8) * 8 = 6 + 24 = 30
• minIndex → 3

i = 6 (even → max)

• value to put = arr[maxIndex] = 4
• arr[6] = 7 + (4 % 8) * 8 = 7 + 32 = 39
• maxIndex → 2

Now array looks like:

arr = [57, 10, 51, 20, 45, 30, 39]

Each element now encodes:

• The original number (mod 8 gives it)
• The desired rearranged number (divide by 8 gives it)

Step 5: Decode Final Values

Now divide each element by 8 to extract the final result:

Index	Value	Decoded = value / 8
0	57	57 / 8 = 7
1	10	10 / 8 = 1
2	51	51 / 8 = 6
3	20	20 / 8 = 2
4	45	45 / 8 = 5
5	30	30 / 8 = 3
6	39	39 / 8 = 4

Final Array:

[7, 1, 6, 2, 5, 3, 4]

3. Implementation

public class RearrangeInPlace {
    public static void rearrange(int[] arr) {
        int n = arr.length;
        int maxIndex = n - 1;
        int minIndex = 0;
        int maxElem = arr[n - 1] + 1; // any number > maximum element

        for (int i = 0; i < n; i++) {
            if (i % 2 == 0) {
                arr[i] += (arr[maxIndex] % maxElem) * maxElem;
                maxIndex--;
            } else {
                arr[i] += (arr[minIndex] % maxElem) * maxElem;
                minIndex++;
            }
        }

        // Final transformation
        for (int i = 0; i < n; i++) {
            arr[i] = arr[i] / maxElem;
        }
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5, 6, 7};
        rearrange(arr);
        for (int i : arr) {
            System.out.print(i + " ");
        }
    }
}