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++
#include <bits/stdc++.h>
using namespace std;
void alternateSort(list<int>& inp)
{
inp.sort();
list<int>::iterator it = inp.begin();
it++;
for (int i=1; i<(inp.size() + 1)/2; i++)
{
int val = inp.back();
inp.pop_back();
inp.insert(it, val);
++it;
}
}
int main()
{
list<int> inp({ 1, 3, 8, 2, 7, 5, 6, 4 });
alternateSort(inp);
for (int i : inp)
cout << i << " ";
return 0;
}
|
Java
import java.util.*;
class AlternateSort
{
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
{
Integer arr[] = {1, 3, 8, 2, 7, 5, 6, 4};
LinkedList<Integer> ll = new LinkedList<Integer>(Arrays.asList(arr));
alternateSort(ll);
}
}
|
Python
inp = []
def alternateSort():
global inp
inp.sort()
it = 0
it = it + 1
i = 1
while ( i < (len(inp) + 1)/2 ):
i = i + 1
val = inp[-1]
inp.pop()
inp.insert(it, val)
it = it + 2
inp=[ 1, 3, 8, 2, 7, 5, 6, 4 ]
alternateSort()
print (inp)
|
C#
using System;
using System.Collections.Generic;
class GFG
{
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+" ");
}
}
public static void Main (String[] args)
{
int []arr = {1, 3, 8, 2, 7, 5, 6, 4};
List<int> ll = new List<int>(arr);
alternateSort(ll);
}
}
|
Javascript
<script>
let inp = []
function alternateSort(){
inp.sort()
let it = 0
it = it + 1
let i = 1
while ( i < (inp.length + 1)/2 ){
i = i + 1
let val = inp[inp.length-1]
inp.pop()
inp.splice(it,0, val)
it = it + 2
}
}
inp=[ 1, 3, 8, 2, 7, 5, 6, 4 ]
alternateSort()
for(let x of inp){
document.write(x," ")
}
</script>
|
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 {
public static String alternateMinMax(List<Integer> lst) {
Collections.sort(lst);
List<Integer> res = new ArrayList<>();
for (int i = 0; i < lst.size() / 2; i++) {
res.add(lst.get(i));
res.add(lst.get(lst.size() - i - 1));
}
if (lst.size() % 2 == 1) {
res.add(lst.get(lst.size() / 2));
}
StringBuilder result = new StringBuilder();
for (int i = 0; i < res.size(); i++) {
result.append(res.get(i)).append(" ");
}
return result.toString();
}
public static void main(String[] args) {
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);
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)
{
lst.Sort();
List<int> res = new List<int>();
int n = lst.Count;
for (int i = 0; i < n / 2; i++)
{
res.Add(lst[i]);
res.Add(lst[n - i - 1]);
}
if (n % 2 == 1)
{
res.Add(lst[n / 2]);
}
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);
const res = [];
for (let i = 0; i < Math.floor(lst.length / 2); i++) {
res.push(lst[i]);
res.push(lst[lst.length - i - 1]);
}
if (lst.length % 2 === 1) {
res.push(lst[Math.floor(lst.length / 2)]);
}
const result = res.join(" ");
return result;
}
const lst = [1, 3, 8, 2, 7, 5, 6, 4];
console.log(alternateMinMax(lst));
|
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!
