Data Modelling & AI Data Structure & Algorithm

Rearrange a given list such that it consists of alternating minimum maximum elements

21 June 2025

0

Given a list of integers, rearrange the list such that it consists of alternating minimum maximum elements using only list operations. The first element of the list should be minimum and second element should be maximum of all elements present in the list. Similarly, third element will be next minimum element and fourth element is next maximum element and so on. Use of extra space is not permitted. Examples:

Input:  [1 3 8 2 7 5 6 4]
Output: [1 8 2 7 3 6 4 5]
Input:  [1 2 3 4 5 6 7]
Output: [1 7 2 6 3 5 4]
Input:  [1 6 2 5 3 4]
Output: [1 6 2 5 3 4]

The idea is to sort the list in ascending order first. Then we start popping elements from the end of the list and insert them into their correct position in the list. Below is the implementation of above idea –

C++

// C++ program to rearrange a given list such that it 
// consists of alternating minimum maximum elements 
#include <bits/stdc++.h> 
using namespace std; 
 
// Function to rearrange a given list such that it 
// consists of alternating minimum maximum elements 
void alternateSort(list<int>& inp) 
{ 
    // sort the list in ascending order 
    inp.sort(); 
 
    // get iterator to first element of the list 
    list<int>::iterator it = inp.begin(); 
    it++; 
 
    for (int i=1; i<(inp.size() + 1)/2; i++) 
    { 
        // pop last element (next greatest) 
        int val = inp.back(); 
        inp.pop_back(); 
 
        // insert it after next minimum element 
        inp.insert(it, val); 
 
        // increment the pointer for next pair 
        ++it; 
    } 
} 
 
// Driver code 
int main() 
{ 
    // input list 
    list<int> inp({ 1, 3, 8, 2, 7, 5, 6, 4 }); 
 
    // rearrange the given list 
    alternateSort(inp); 
 
    // print the modified list 
    for (int i : inp) 
        cout << i << " "; 
 
    return 0; 
} 

Java

// Java program to rearrange a given list such that it
// consists of alternating minimum maximum elements
import java.util.*;
 
class AlternateSort
{
    // Function to rearrange a given list such that it
    // consists of alternating minimum maximum elements
    // using LinkedList
    public static void alternateSort(LinkedList<Integer> ll) 
    {
        Collections.sort(ll);
         
        for (int i = 1; i < (ll.size() + 1)/2; i++)
        {
            Integer x = ll.getLast();
            ll.removeLast();
            ll.add(2*i - 1, x);
        }
         
        System.out.println(ll);
    }
     
    public static void main (String[] args) throws java.lang.Exception
    {
        // input list
        Integer arr[] = {1, 3, 8, 2, 7, 5, 6, 4};
         
        // convert array to LinkedList
        LinkedList<Integer> ll = new LinkedList<Integer>(Arrays.asList(arr));
         
        // rearrange the given list
        alternateSort(ll);
    }
}

Python

# Python program to rearrange a given list such that it
# consists of alternating minimum maximum elements
inp = []
 
# Function to rearrange a given list such that it
# consists of alternating minimum maximum elements
def alternateSort():
 
    global inp
     
    # sort the list in ascending order
    inp.sort()
 
    # get index to first element of the list
    it = 0
    it = it + 1
     
    i = 1
     
    while ( i < (len(inp) + 1)/2 ):
     
        i = i + 1
         
        # pop last element (next greatest)
        val = inp[-1]
        inp.pop()
 
        # insert it after next minimum element
        inp.insert(it, val)
 
        # increment the pointer for next pair
        it = it + 2
     
# Driver code
 
# input list
inp=[ 1, 3, 8, 2, 7, 5, 6, 4 ]
 
# rearrange the given list
alternateSort()
 
# print the modified list
print (inp) 
 
# This code is contributed by Arnab Kundu

C#

// C# program to rearrange a given list such that it
// consists of alternating minimum maximum elements 
using System; 
using System.Collections.Generic;
 
class GFG
{
    // Function to rearrange a given list such that it
    // consists of alternating minimum maximum elements
    // using List
    public static void alternateSort(List<int> ll) 
    {
        ll.Sort();
         
        for (int i = 1; i < (ll.Count + 1)/2; i++)
        {
            int x = ll[ll.Count-1];
            ll.RemoveAt(ll.Count-1);
            ll.Insert(2*i - 1, x);
        }
        foreach(int a in ll)
        {
            Console.Write(a+" ");
        }
         
    }
     
    // Driver code
    public static void Main (String[] args)
    {
        // input list
        int []arr = {1, 3, 8, 2, 7, 5, 6, 4};
         
        // convert array to List
        List<int> ll = new List<int>(arr);
         
        // rearrange the given list
        alternateSort(ll);
    }
}
 
/* This code contributed by PrinciRaj1992 */

Javascript

<script>
 
// JavaScript program to rearrange a given list such that it
// consists of alternating minimum maximum elements
let inp = []
 
// Function to rearrange a given list such that it
// consists of alternating minimum maximum elements
function alternateSort(){
 
    // sort the list in ascending order
    inp.sort()
 
    // get index to first element of the list
    let it = 0
    it = it + 1
     
    let i = 1
     
    while ( i < (inp.length + 1)/2 ){
     
        i = i + 1
         
        // pop last element (next greatest)
        let val = inp[inp.length-1]
        inp.pop()
 
        // insert it after next minimum element
        inp.splice(it,0, val)
 
        // increment the pointer for next pair
        it = it + 2
    }
}
     
// Driver code
 
// input list
inp=[ 1, 3, 8, 2, 7, 5, 6, 4 ]
 
// rearrange the given list
alternateSort()
 
// print the modified list
for(let x of inp){
    document.write(x," ")
}
 
// This code is contributed by shinjanpatra
 
</script>

Output

1 8 2 7 3 6 4 5

Time Complexity: O(N*logN), as we are using a sort function.
Auxiliary Space: O(1), as we are not using extra space.

This article is contributed by Aditya Goel. If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.

Approach#2: Using sort()

Sort the given list in ascending order Initialize an empty result list Iterate over half of the sorted list indices: Append the element from the current index and the corresponding element from the end of the list If the length of the original list is odd, append the middle element to the result list Convert the result list to a string with space-separated integers

Algorithm

1. Sort the list using the sort() function
2. Initialize an empty result list
3. Loop through the range of the first half of the list
4. Append the i-th element of the sorted list
5. Append the (-i-1)-th element of the sorted list
6. If the length of the original list is odd, append the middle element to the result list
7. Convert the result list to a string using the join() function

C++

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
 
string alternateMinMax(vector<int> lst) {
    sort(lst.begin(), lst.end());
    vector<int> res;
    for (int i = 0; i < lst.size() / 2; i++) {
        res.push_back(lst[i]);
        res.push_back(lst[lst.size() - i - 1]);
    }
    if (lst.size() % 2 == 1) {
        res.push_back(lst[lst.size() / 2]);
    }
    string result = "";
    for (int i = 0; i < res.size(); i++) {
        result += to_string(res[i]) + " ";
    }
    return result;
}
 
int main() {
    vector<int> lst = {1, 3, 8, 2, 7, 5, 6, 4};
    cout << alternateMinMax(lst) << endl;
    return 0;
}

Java

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
 
public class AlternateMinMax {
    // Function to rearrange a list of integers in alternating min-max order
    public static String alternateMinMax(List<Integer> lst) {
        // Sort the input list in ascending order
        Collections.sort(lst);
         
          
        List<Integer> res = new ArrayList<>();
         
        // Iterate through the first half of the sorted list
        for (int i = 0; i < lst.size() / 2; i++) {
              
            res.add(lst.get(i));
            res.add(lst.get(lst.size() - i - 1));
        }
         
        // If the input list has an odd number of elements, add the middle element
        if (lst.size() % 2 == 1) {
            res.add(lst.get(lst.size() / 2));
        }
         
        // Create a StringBuilder to build the result string
        StringBuilder result = new StringBuilder();
         
        // Append each element from the rearranged list to the result string
        for (int i = 0; i < res.size(); i++) {
            result.append(res.get(i)).append(" ");
        }
         
          
        return result.toString();
    }
 
    public static void main(String[] args) {
        // Create a list of integers
        List<Integer> lst = new ArrayList<>();
        lst.add(1);
        lst.add(3);
        lst.add(8);
        lst.add(2);
        lst.add(7);
        lst.add(5);
        lst.add(6);
        lst.add(4);
         
        // Call the alternateMinMax function and print the result
        System.out.println(alternateMinMax(lst));
    }
}

Python3

def alternate_min_max(lst):
    lst.sort()
    res = []
    for i in range(len(lst) // 2):
        res.append(lst[i])
        res.append(lst[-i-1])
    if len(lst) % 2 == 1:
        res.append(lst[len(lst) // 2])
    return ' '.join(map(str, res))
 
lst = [1, 3, 8, 2, 7, 5, 6, 4]
print(alternate_min_max(lst))  

C#

using System;
using System.Collections.Generic;
using System.Linq;
 
public class GFG
{
    public static string GetAlternateMinMax(List<int> lst)
    {
        // Sort the list in ascending order
        lst.Sort();
 
        List<int> res = new List<int>();
        int n = lst.Count;
 
        // Create the alternating min-max list
        for (int i = 0; i < n / 2; i++)
        {
            res.Add(lst[i]);
            res.Add(lst[n - i - 1]);
        }
 
        // If the list has an odd number of elements, add the middle element
        if (n % 2 == 1)
        {
            res.Add(lst[n / 2]);
        }
 
        // Convert the result list to a string
        string result = string.Join(" ", res);
 
        return result;
    }
 
    public static void Main(string[] args)
    {
        List<int> lst = new List<int> { 1, 3, 8, 2, 7, 5, 6, 4 };
        string result = GetAlternateMinMax(lst);
        Console.WriteLine(result);
    }
}

Javascript

function alternateMinMax(lst) {
    lst.sort((a, b) => a - b);
    // Initialize an empty array to 
    // store the result
    const res = [];
    for (let i = 0; i < Math.floor(lst.length / 2); i++) {
        // Push the minimum element from the beginning
        res.push(lst[i]);
        res.push(lst[lst.length - i - 1]);
    }
    // If the length of the list is odd
    // push the middle element
    if (lst.length % 2 === 1) {
        res.push(lst[Math.floor(lst.length / 2)]);
    }
    // Convert the result array to a 
    // space-separated string
    const result = res.join(" ");
    return result;
}
 
// Input list
const lst = [1, 3, 8, 2, 7, 5, 6, 4];
console.log(alternateMinMax(lst));

Output

1 8 2 7 3 6 4 5

Time Complexity: O(nlogn) because of the sorting operation. The for loop iterates over half of the list which takes O(n/2) time. The conversion of the result list to a string takes O(n) time. Since O(nlogn) is larger than O(n), the overall time complexity is O(n*logn).

Auxiliary Space: O(n) because the sorted list and result list both take O(n) space. The space used by the variables used in the function is constant and does not depend on the size of the input list.

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!

Rearrange a given list such that it consists of alternating minimum maximum elements

C++

Java

Python

C#

Javascript

Approach#2: Using sort()

Algorithm

C++

Java

Python3

C#

Javascript

From Word2Vec to LLM2Vec: How to Choose the Right Embedding Model for RAG

How to Debug Slow Search Requests in Milvus

When Context Engineering Is Done Right, Hallucinations Can Be the Spark of AI Creativity

LEAVE A REPLY Cancel reply

Most Popular

The Amazon Echo Show’s full-screen ads are destroying the experience

The Google Pixel Buds 2a look great, but I wanted more out of them

Samsung’s Galaxy S26 Pro is gearing up for the big Exynos comeback

The Chromecast is still king, here’s why I won’t give it up

EDITOR PICKS

The Amazon Echo Show’s full-screen ads are destroying the experience

The Google Pixel Buds 2a look great, but I wanted more out of them

Samsung’s Galaxy S26 Pro is gearing up for the big Exynos comeback

POPULAR POSTS

The Amazon Echo Show’s full-screen ads are destroying the experience

The Google Pixel Buds 2a look great, but I wanted more out of them

Samsung’s Galaxy S26 Pro is gearing up for the big Exynos comeback

POPULAR CATEGORY

ABOUT US

FOLLOW US