Print array elements in alternatively increasing and decreasing order

0 0 8 minutes read

Given an array of N elements. The task is to print the array elements in such a way that first two elements are in increasing order, next 3 in decreasing order, next 4 in increasing order and so on.

Examples:

Input : arr = {2, 6, 2, 4, 0, 1, 4, 8, 2, 0, 0, 5,2,2}
Output : 0 0 8 6 5 0 1 2 2 4 4 2 2 2

Input : arr = {1, 2, 3, 4, 5, 6}
Output : 1 2 6 5 4 3

Source :Oracle Interview experience set 52
The idea is to use 2 pointer technique. First sort the array in increasing order and maintain two pointers $l$ and $r$ where $l$ is to print the array in increasing order and $r$ to print the array in decreasing order. Keep a variable $K$ to specify the number of elements to be printed in an iteration and a variable flag to switch between printing in increasing order and decreasing order alternatively.

Below is the implementation of above approach:

C++

// C++ program to print array elements in
// alternative increasing and decreasing
// order
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to print array elements in
// alternative increasing and decreasing
// order
void printArray(int arr[], int n)
{
    // First sort the array in increasing order
    sort(arr, arr + n);
 
    int l = 0, r = n - 1, flag = 0, i;
 
    // start with 2 elements in
    // increasing order
    int k = 2;
 
    // till all the elements are not printed
    while (l <= r) {
        // printing the elements in
        // increasing order
        if (flag == 0) {
            for (i = l; i < l + k && i <= r; i++)
                cout << arr[i] << " ";
 
            flag = 1;
            l = i;
        }
        else // printing the elements in
        // decreasing order
        {
            for (i = r; i > r - k && i >= l; i--)
                cout << arr[i] << " ";
 
            flag = 0;
            r = i;
        }
 
        // increasing the number of elements
        // to printed in next iteration
        k++;
    }
}
 
// Driver Code
int main()
{
    int n = 6;
 
    int arr[] = { 1, 2, 3, 4, 5, 6 };
 
    printArray(arr, n);
 
    return 0;
}

Java

// Java program to print array elements in
// alternative increasing and decreasing
// order
import java.util.*;
class Solution
{
  
// Function to print array elements in
// alternative increasing and decreasing
// order
static void printArray(int arr[], int n)
{
    // First sort the array in increasing order
    Arrays.sort(arr);
  
    int l = 0, r = n - 1, flag = 0, i;
  
    // start with 2 elements in
    // increasing order
    int k = 2;
  
    // till all the elements are not printed
    while (l <= r) {
        // printing the elements in
        // increasing order
        if (flag == 0) {
            for (i = l; i < l + k && i <= r; i++)
                System.out.print(arr[i] + " ");
  
            flag = 1;
            l = i;
        }
        else // printing the elements in
        // decreasing order
        {
            for (i = r; i > r - k && i >= l; i--)
                System.out.print(arr[i] + " ");
  
            flag = 0;
            r = i;
        }
  
        // increasing the number of elements
        // to printed in next iteration
        k++;
    }
}
  
// Driver Code
public static void main(String args[])
{
    int n = 6;
  
    int arr[] = { 1, 2, 3, 4, 5, 6 };
  
    printArray(arr, n);
  
 
}
 
}
//contributed by Arnab Kundu

Python3

# Python 3 program to print array elements 
# in alternative increasing and decreasing
# order
 
# Function to print array elements in
# alternative increasing and decreasing
# order
def printArray(arr, n):
 
    # First sort the array in
    # increasing order
    arr.sort()
 
    l = 0
    r = n - 1
    flag = 0
     
    # start with 2 elements in
    # increasing order
    k = 2
 
    # till all the elements are not printed
    while (l <= r) :
         
        # printing the elements in
        # increasing order
        if (flag == 0):
            i = l
            while i < l + k and i <= r:
                print(arr[i], end = " ")
                i += 1
 
            flag = 1
            l = i
         
        else:     # printing the elements in
                 # decreasing order
            i = r
            while i > r - k and i >= l:
                print(arr[i], end = " ")
                i -= 1
 
            flag = 0
            r = i
 
        # increasing the number of elements
        # to printed in next iteration
        k += 1
 
# Driver Code
if __name__ == "__main__":
     
    n = 6
    arr = [ 1, 2, 3, 4, 5, 6 ] 
    printArray(arr, n)
 
# This code is contributed by ita_c

C#

// C# program to print array elements in 
// alternative increasing and decreasing 
// order 
using System;
  
class GFG{
      
// Function to print array elements in 
// alternative increasing and decreasing 
// order 
static void printArray(int []arr, int n) 
{ 
     
    // First sort the array
    // in increasing order 
    Array.Sort(arr); 
  
    int l = 0, r = n - 1, flag = 0, i; 
  
    // start with 2 elements in 
    // increasing order 
    int k = 2; 
  
    // till all the elements
    // are not printed 
    while (l <= r) { 
         
        // printing the elements in 
        // increasing order 
        if (flag == 0) {
             
            for (i = l; i < l + k && i <= r; i++) 
                    Console.Write(arr[i] + " "); 
  
            flag = 1; 
            l = i; 
        } 
        else
         
        // printing the elements in 
        // decreasing order 
        { 
            for (i = r; i > r - k && i >= l; i--) 
                Console.Write(arr[i] + " "); 
  
            flag = 0; 
            r = i; 
        } 
  
        // increasing the number of elements 
        // to printed in next iteration 
        k++; 
    } 
} 
  
// Driver Code 
static public void Main ()
{
          
    int n = 6; 
    int []arr = { 1, 2, 3, 4, 5, 6 }; 
    printArray(arr, n); 
 
} 
} 
 
// This code is contributed by Sach_Code

PHP

<?php
// PHP program to print array elements in 
// alternative increasing and decreasing 
// order 
 
// Function to print array elements in 
// alternative increasing and decreasing 
// order 
function printArray($arr, $n) 
{ 
    // First sort the array in 
    // increasing order 
    sort($arr); 
 
    $l = 0;
    $r = $n - 1;
    $flag = 0;
 
    // start with 2 elements in 
    // increasing order 
    $k = 2; 
 
    // till all the elements are
    // not printed 
    while ($l <= $r) 
    { 
        // printing the elements in 
        // increasing order 
        if ($flag == 0) 
        { 
            for ($i = $l; 
                 $i < $l + $k && 
                 $i <= $r; $i++) 
                echo $arr[$i] , " "; 
 
            $flag = 1; 
            $l = $i; 
        } 
        else // printing the elements in 
             // decreasing order 
        { 
            for ($i = $r;
                 $i > $r - $k && 
                 $i >= $l; $i--) 
                echo $arr[$i] , " "; 
 
            $flag = 0; 
            $r = $i; 
        } 
 
        // increasing the number of elements 
        // to printed in next iteration 
        $k++; 
    } 
} 
 
// Driver Code 
$n = 6; 
$arr = array( 1, 2, 3, 4, 5, 6 ); 
 
printArray($arr, $n); 
 
// This code is contributed by jit_t
?>

Javascript

<script>
 
// Javascript program to print array elements in 
// alternative increasing and decreasing 
// order 
 
// Function to print array elements in 
// alternative increasing and decreasing 
// order 
function printArray(arr, n) 
{ 
     
    // First sort the array
    // in increasing order 
    arr.sort(); 
 
    let l = 0, r = n - 1, flag = 0, i; 
 
    // start with 2 elements in 
    // increasing order 
    let k = 2; 
 
    // till all the elements
    // are not printed 
    while (l <= r)
    { 
         
        // printing the elements in 
        // increasing order 
        if (flag == 0)
        {
            for(i = l; i < l + k && i <= r; i++) 
                document.write(arr[i] + " "); 
 
            flag = 1; 
            l = i; 
        } 
        else
 
        // Printing the elements in 
        // decreasing order 
        { 
            for(i = r; i > r - k && i >= l; i--) 
                document.write(arr[i] + " "); 
 
            flag = 0; 
            r = i; 
        } 
 
        // Increasing the number of elements 
        // to printed in next iteration 
        k++; 
    } 
} 
 
// Driver code
let n = 6; 
let arr = [ 1, 2, 3, 4, 5, 6 ]; 
printArray(arr, n); 
 
// This code is contributed by suresh07
 
</script>

Output:

1 2 6 5 4 3

Time Complexity : O(nlogn)
Auxiliary Space: O(1)

Approach#2: Using deque

This approach uses a deque from the collections module to implement a queue. It then iterates through the queue in a while loop, using a boolean flag to determine whether to pop from the left or the right of the queue, and print the element. Finally, the flag is toggled for the next iteration.

Algorithm

1. Initialize a queue and enqueue all the elements of the array.
2. Initialize a flag variable as True.
3. While the queue is not empty, do the following:
a. If the flag is True, print the element at the front of the queue and dequeue it.
b. If the flag is False, print the element at the rear of the queue and dequeue it.
c. Toggle the flag variable.
4. Repeat step 3 until the queue is empty.

C++

#include <iostream>
#include <deque>
#include <vector>
 
using namespace std;
 
void print_alternate(vector<int> arr)
{
   
    // convert the vector to a deque using the constructor
    deque<int> q(arr.begin(), arr.end());
     
    // set a flag to keep track of whether to print the front or back element of the deque
    bool flag = true;
     
    // continue printing until the deque is empty
    while (!q.empty()) {
        // if flag is true, print the front element and remove it from the deque
        if (flag) {
            cout << q.front() << " ";
            q.pop_front();
        }
        // if flag is false, print the back element and remove it from the deque
        else {
            cout << q.back() << " ";
            q.pop_back();
        }
         
        // switch the flag value to alternate between printing the front and back elements
        flag = !flag;
    }
}
 
int main() 
{
   
    // create a vector of integers
    vector<int> arr = {2, 6, 2, 4, 0, 1, 4, 8, 2, 0, 0, 5, 2, 2};
     
    // call the print_alternate function with the vector as input
    print_alternate(arr);
     
    // return 0 to indicate successful program execution
    return 0;
}

Java

import java.util.*;
 
public class Main 
{
 
  // define a function that prints the elements of 
  // an ArrayList in an alternating pattern
  public static void printAlternate(ArrayList<Integer> arr)
  {
 
    // convert the ArrayList to a LinkedList using the constructor
    Deque<Integer> q = new LinkedList<>(arr);
 
    // set a flag to keep track of whether to
    // print the first or last element of the LinkedList
    boolean flag = true;
 
    // continue printing until the LinkedList is empty
    while (!q.isEmpty()) 
    {
 
      // if flag is true, print the first element and 
      // remove it from the LinkedList
      if (flag) {
        System.out.print(q.removeFirst() + " ");
      }
      // if flag is false, print the last element and
      // remove it from the LinkedList
      else {
        System.out.print(q.removeLast() + " ");
      }
 
      // switch the flag value to alternate between
      // printing the first and last elements
      flag = !flag;
    }
  }
 
  public static void main(String[] args)
  {
 
    // create an ArrayList of Integer objects
    ArrayList<Integer> arr = new ArrayList<>(Arrays.asList(2, 6, 2, 4, 0, 1, 4, 8, 2, 0, 0, 5, 2, 2));
 
    // call the printAlternate function with the ArrayList as input
    printAlternate(arr);
  }
}

Python3

from collections import deque
 
def print_alternate(arr):
    q = deque(arr)
    flag = True
    while q:
        if flag:
            print(q.popleft(), end=" ")
        else:
            print(q.pop(), end=" ")
        flag = not flag
 
arr = [2, 6, 2, 4, 0, 1, 4, 8, 2, 0, 0, 5, 2, 2]
print_alternate(arr)

Output

2 2 6 2 2 5 4 0 0 0 1 2 4 8

Time Complexity: O(n) for traversing the array and enqueueing/dequeueing elements
Auxiliary Space: O(n) for the queue

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 zambiatek!