Print array elements in alternatively increasing and decreasing order
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 2Input : 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 and where is to print the array in increasing order and to print the array in decreasing order. Keep a variable 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 |
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> |
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 ?> |
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) |
C#
using System; using System.Collections.Generic; class Program { static void PrintAlternate(List< int > arr) { // Convert the List to a LinkedList using the constructor LinkedList< int > deque = new LinkedList< int >(arr); // 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 (deque.Count > 0) { // If the flag is true, print the front element and remove it from the deque if (flag) { Console.Write(deque.First.Value + " " ); deque.RemoveFirst(); } // If the flag is false, print the back element and remove it from the deque else { Console.Write(deque.Last.Value + " " ); deque.RemoveLast(); } // Switch the flag value to alternate between printing the front and back elements flag = !flag; } } static void Main( string [] args) { // Create a list of integers List< int > arr = new List< int > { 2, 6, 2, 4, 0, 1, 4, 8, 2, 0, 0, 5, 2, 2 }; // Call the PrintAlternate function with the list as input PrintAlternate(arr); // Return 0 to indicate successful program execution } } |
Javascript
function printAlternate(arr) { // Convert the input array to a deque (linked list) const deque = arr.slice(); // Create a copy of the array // Set a flag to keep track of whether to print the first or last element of the deque let flag = true ; // Continue printing until the deque is empty while (deque.length > 0) { // If flag is true, print and remove the first element if (flag) { process.stdout.write(deque.shift() + ' ' ); } // If flag is false, print and remove the last element else { process.stdout.write(deque.pop() + ' ' ); } // Switch the flag value to alternate between printing the first and last elements flag = !flag; } } // Main function function main() { // Create an array of integers const arr = [2, 6, 2, 4, 0, 1, 4, 8, 2, 0, 0, 5, 2, 2]; // Call the printAlternate function with the array as input printAlternate(arr); console.log(); // Print a newline for formatting } // Call the main function to execute the code main(); |
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