Given an array arr[] containing N integers, the task is to rearrange all the elements of array such that absolute difference between consecutive elements of the array are sorted in increasing order.
Examples
Input: arr[] = { 5, -2, 4, 8, 6, 5 }
Output: 5 5 6 4 8 -2
Explanation:
|5 – 5| = 0
|5 – 6| = 1
|6 – 4| = 2
|4 – 8| = 4
|8 – (-2)| = 10
Hence, the differences between adjacent elements are sorted.Input: arr[] = { 8, 1, 4, 2 }
Output: 4 2 8 1
Explanation:
|2 – 4| = 2
|8 – 2| = 6
|1 – 8| = 7
Hence, the differences between adjacent elements are sorted.
Approach: The problem can be solved using Greedy Approach. We know that the maximum difference is between the minimum and maximum elements of the array. Using this fact, if we include one of the minimum element in the answer, then the next element included in the answer array will be the maximum element, then the third element included will be the second minimum, then the fourth element included will be the second maximum and so on will give the desired array.
Below are the steps:
- Sort the given array arr[] in increasing order.
- Choose the first maximum(say a) and minimum element(say b) from the sorted array and insert in the answer array(say ans[]) as {a, b}.
- Repeat the above steps by choosing the second, third, fourth… maximum and minimum element from the sorted array and insert it in the front of the answer array.
- After all the above operations the answer array has the desired result.
Below is the implementation of the above approach:
CPP
// C++ implementation of the above approach#include <bits/stdc++.h>using namespace std;// Function that arrange the array such that// all absolute difference between adjacent// element are sortedvoid sortedAdjacentDifferences(int arr[], int n){ // To store the resultant array int ans[n]; // Sorting the given array // in ascending order sort(arr + 0, arr + n); // Variable to represent left and right // ends of the given array int l = 0, r = n - 1; // Traversing the answer array in reverse // order and arrange the array elements from // arr[] in reverse order for (int i = n - 1; i >= 0; i--) { // Inserting elements in zig-zag manner if (i % 2) { ans[i] = arr[l]; l++; } else { ans[i] = arr[r]; r--; } } // Displaying the resultant array for (int i = 0; i < n; i++) { cout << ans[i] << " "; }}// Driver Codeint main(){ int arr[] = { 5, -2, 4, 8, 6, 4, 5 }; int n = sizeof(arr) / sizeof(arr[0]); // Function Call sortedAdjacentDifferences(arr, n); return 0;} |
Java
// Java implementation of the above approachimport java.util.*;class GFG { // Function that arrange the array such that // all absolute difference between adjacent // element are sorted static void sortedAdjacentDifferences(int arr[], int n) { // To store the resultant array int[] ans = new int[n]; // Sorting the given array // in ascending order Arrays.sort(arr); // Variable to represent left and right // ends of the given array int l = 0, r = n - 1; // Traversing the answer array in reverse // order and arrange the array elements from // arr[] in reverse order for (int i = n - 1; i >= 0; i--) { // Inserting elements in zig-zag manner if (i % 2 == 1) { ans[i] = arr[l]; l++; } else { ans[i] = arr[r]; r--; } } // Displaying the resultant array for (int i = 0; i < n; i++) { System.out.print(ans[i] + " "); } } // Driver Code public static void main(String[] args) { int arr[] = { 5, -2, 4, 8, 6, 4, 5 }; int n = arr.length; // Function Call sortedAdjacentDifferences(arr, n); }}// This code is contributed by Princi Singh |
Python3
# Python3 implementation of the above approach# Function that arrange the array such that# all absolute difference between adjacent# element are sorteddef sortedAdjacentDifferences(arr, n): # To store the resultant array ans = [0]*n # Sorting the given array # in ascending order arr = sorted(arr) # Variable to represent left and right # ends of the given array l = 0 r = n - 1 # Traversing the answer array in reverse # order and arrange the array elements from # arr[] in reverse order for i in range(n - 1, -1, -1): # Inserting elements in zig-zag manner if (i % 2): ans[i] = arr[l] l += 1 else: ans[i] = arr[r] r -= 1 # Displaying the resultant array for i in range(n): print(ans[i], end=" ")# Driver Codeif __name__ == '__main__': arr = [5, -2, 4, 8, 6, 4, 5] n = len(arr) # Function Call sortedAdjacentDifferences(arr, n)# This code is contributed by mohit kumar 29 |
C#
// C# implementation of the above approachusing System;class GFG { // Function that arrange the array such that // all absolute difference between adjacent // element are sorted static void sortedAdjacentDifferences(int[] arr, int n) { // To store the resultant array int[] ans = new int[n]; // Sorting the given array // in ascending order Array.Sort(arr); // Variable to represent left and right // ends of the given array int l = 0, r = n - 1; // Traversing the answer array in reverse // order and arrange the array elements from // arr[] in reverse order for (int i = n - 1; i >= 0; i--) { // Inserting elements in zig-zag manner if (i % 2 != 0) { ans[i] = arr[l]; l++; } else { ans[i] = arr[r]; r--; } } // Displaying the resultant array for (int i = 0; i < n; i++) { Console.Write(ans[i] + " "); } } // Driver Code public static void Main() { int[] arr = { 5, -2, 4, 8, 6, 4, 5 }; int n = arr.Length; // Function Call sortedAdjacentDifferences(arr, n); }}// This code is contributed by chitranayal |
Javascript
<script>// JavaScript implementation of the above approach// Function that arrange the array such that// all absolute difference between adjacent// element are sortedfunction sortedAdjacentDifferences(arr, n){ // To store the resultant array let ans = new Array(n); // Sorting the given array // in ascending order arr.sort(); // Variable to represent left and right // ends of the given array let l = 0, r = n - 1; // Traversing the answer array in reverse // order and arrange the array elements from // arr[] in reverse order for (let i = n - 1; i >= 0; i--) { // Inserting elements in zig-zag manner if (i % 2) { ans[i] = arr[l]; l++; } else { ans[i] = arr[r]; r--; } } // Displaying the resultant array for (let i = 0; i < n; i++) { document.write(ans[i] + " "); }}// Driver Code let arr = [ 5, -2, 4, 8, 6, 4, 5 ]; let n = arr.length; // Function Call sortedAdjacentDifferences(arr, n);</script> |
Output:
5 4 5 4 6 -2 8
Time Complexity: O(N*log N), where N is the number of elements in the given array.
Auxiliary Space: O(N) because it uses extra space for array ans.
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!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
