Hello Everyone,
Given a sorted array of positive integers, rearrange the array alternately i.e first element should be maximum value, second minimum value, third second max, fourth second min and so on.
Examples:
Input : arr = {1, 2, 3, 4, 5, 6, 7}
Output : arr = {7, 1, 6, 2, 5, 3, 4}Input : arr = {1, 2, 3, 4, 5, 6}
Output : arr = {6, 1, 5, 2, 4, 3}
Expected time complexity: O(n).
The idea is to use an auxiliary array. We maintain two pointers one to leftmost or smallest element and other to rightmost or largest element. We move both pointers toward each other and alternatively copy elements at these pointers to an auxiliary array. Finally, we copy the auxiliary array back to the original array.
Below is the implementation of the above approach:
// C++ program to rearrange an array in minimum
// maximum form
#include <bits/stdc++.h>
using
namespace
std;
// Prints max at first position, min at second position
// second max at third position, second min at fourth
// position and so on.
void
rearrange(
int
arr[],
int
n)
{
// Auxiliary array to hold modified array
int
temp[n];
// Indexes of smallest and largest elements
// from remaining array.
int
small = 0, large = n - 1;
// To indicate whether we need to copy rmaining
// largest or remaining smallest at next position
int
flag =
true
;
// Store result in temp[]
for
(
int
i = 0; i < n; i++) {
if
(flag)
temp[i] = arr[large--];
else
temp[i] = arr[small++];
flag = !flag;
}
// Copy temp[] to arr[]
for
(
int
i = 0; i < n; i++)
arr[i] = temp[i];
}
// Driver code
int
main()
{
int
arr[] = { 1, 2, 3, 4, 5, 6 };
int
n =
sizeof
(arr) /
sizeof
(arr[0]);
cout <<
"Original Array\n"
;
for
(
int
i = 0; i < n; i++)
cout << arr[i] <<
" "
;
rearrange(arr, n);
cout <<
"\nModified Array\n"
;
for
(
int
i = 0; i < n; i++)
cout << arr[i] <<
" "
;
return
0;
}
Output
Original Array 1 2 3 4 5 6 Modified Array 6 1 5 2 4 3
Time Complexity: O(n)
Auxiliary Space: O(n)