Alternative Sorting

JavaView on GFG

Problem Overview

Sort such that first element is max, second is min, third is second max, etc.

Intuition

Sort such that first element is max, second is min, third is second max, etc. Sort then interleave.

Algorithm

1Sort ascending. Two pointers: left=0 (min side), right=n-1 (max side). Alternately pick from right then left.

Common Pitfalls

• Pick largest first at odd positions, smallest at even positions (or vice versa per problem spec).

Alternative Sorting.java

Java

// Approach: Sort the array, then interleave: pick from the largest end and smallest end alternately.
// Time: O(n log n) Space: O(n)
import java.util.*;

class Solution {
    public static ArrayList<Integer> alternateSort(int[] arr) {
        ArrayList<Integer> list = new ArrayList<>();
        int n = arr.length;
        Arrays.sort(arr);
        int left = 0;
        int right = n - 1;
        while (left <= right) {
            if (left == right) {
                list.add(arr[left++]);
                return list;
            }
            list.add(arr[right--]);
            list.add(arr[left++]);
        }
        return list;
    }
}

Was this solution helpful?