Generate an N-length array having length of non-decreasing subarrays maximized and minimum difference between first and last array elements
Given an array arr[ ] of size N, the task is to print an N-length array whose sum of lengths of all non-decreasing subarrays is maximum and the difference between the first and last elements is minimum.
Examples:
Input: N = 5, arr = {4, 3, 5, 3, 2}
Output: {3, 4, 5, 2, 3}
Explanation: Difference between the first and last element is minimum, i.e. 3 – 3 = 0, and sum of non-decreasing subarrays is maximum, i.e.
1. {3, 4, 5}, length = 3
2. {2, 3}, length = 2
therefore sum of non-decreasing sub-arrays is 5.Input: N = 8, arr = {4, 6, 2, 6, 8, 2, 6, 4}
Output: {2, 4, 4, 6, 6, 6, 8, 2}
Approach: The problem can be solved greedily. Follow the steps below to solve the problem:
- Sort the array arr[ ] in non-decreasing order.
- Find the index of two consecutive elements with minimum difference, say i and i + 1.
- Swap arr[0] with arr[i] and arr[N] with arr[i + 1].
- Swap arr[1 : i – 1] with arr[i + 2 : N – 1].
- Print the array arr[ ].
Below is the implementation of the above approach:
C++
// C++ program for above approach #include <bits/stdc++.h> using namespace std; // Function to print target array void printArr( int arr[], int n) { // Sort the given array sort(arr, arr + n); // Seeking for index of elements with minimum diff. int minDifference = INT_MAX; int minIndex = -1; // Seeking for index for ( int i = 1; i < n; i++) { if (minDifference > abs (arr[i] - arr[i - 1])) { minDifference = abs (arr[i] - arr[i - 1]); minIndex = i - 1; } } // To store target array int Arr[n]; Arr[0] = arr[minIndex]; Arr[n - 1] = arr[minIndex + 1]; int pos = 1; // Copying element for ( int i = minIndex + 2; i < n; i++) { Arr[pos++] = arr[i]; } // Copying remaining element for ( int i = 0; i < minIndex; i++) { Arr[pos++] = arr[i]; } // Printing target array for ( int i = 0; i < n; i++) { cout << Arr[i] << " " ; } } // Driver Code int main() { // Given Input int N = 8; int arr[] = { 4, 6, 2, 6, 8, 2, 6, 4 }; // Function Call printArr(arr, N); return 0; } |
Java
// Java program for above approach import java.io.*; import java.util.*; class GFG{ // Function to print target array public static void printArr( int arr[], int n) { // Sort the given array Arrays.sort(arr); // Seeking for index of elements // with minimum diff. int minDifference = 1000000007 ; int minIndex = - 1 ; // Seeking for index for ( int i = 1 ; i < n; i++) { if (minDifference > Math.abs(arr[i] - arr[i - 1 ])) { minDifference = Math.abs(arr[i] - arr[i - 1 ]); minIndex = i - 1 ; } } // To store target array int Arr[] = new int [n]; Arr[ 0 ] = arr[minIndex]; Arr[n - 1 ] = arr[minIndex + 1 ]; int pos = 1 ; // Copying element for ( int i = minIndex + 2 ; i < n; i++) { Arr[pos++] = arr[i]; } // Copying remaining element for ( int i = 0 ; i < minIndex; i++) { Arr[pos++] = arr[i]; } // Printing target array for ( int i = 0 ; i < n; i++) { System.out.print(Arr[i] + " " ); } } // Driver code public static void main(String[] args) { int N = 8 ; int arr[] = { 4 , 6 , 2 , 6 , 8 , 2 , 6 , 4 }; // Function Call printArr(arr, N); } } // This code is contributed by maddler |
Python3
# Python3 program for above approach import sys # Function to print target array def printArr(arr, n): # Sort the given array arr.sort() # Seeking for index of elements with minimum diff. minDifference = sys.maxsize minIndex = - 1 # Seeking for index for i in range ( 1 ,n, 1 ): if (minDifference > abs (arr[i] - arr[i - 1 ])): minDifference = abs (arr[i] - arr[i - 1 ]) minIndex = i - 1 # To store target array Arr = [ 0 for i in range (n)] Arr[ 0 ] = arr[minIndex] Arr[n - 1 ] = arr[minIndex + 1 ] pos = 1 # Copying element for i in range (minIndex + 2 ,n, 1 ): Arr[pos] = arr[i] pos + = 1 # Copying remaining element for i in range (minIndex): Arr[pos] = arr[i] pos + = 1 # Printing target array for i in range (n): print (Arr[i],end = " " ) # Driver Code if __name__ = = '__main__' : # Given Input N = 8 arr = [ 4 , 6 , 2 , 6 , 8 , 2 , 6 , 4 ] # Function Call printArr(arr, N) # This code is contributed by bgangwar59. |
C#
// C# program for above approach using System; class GFG{ // Function to print target array public static void printArr( int []arr, int n) { // Sort the given array Array.Sort(arr); // Seeking for index of elements // with minimum diff. int minDifference = 1000000007; int minIndex = -1; // Seeking for index for ( int i = 1; i < n; i++) { if (minDifference > Math.Abs(arr[i] - arr[i - 1])) { minDifference = Math.Abs(arr[i] - arr[i - 1]); minIndex = i - 1; } } // To store target array int []Arr = new int [n]; Arr[0] = arr[minIndex]; Arr[n - 1] = arr[minIndex + 1]; int pos = 1; // Copying element for ( int i = minIndex + 2; i < n; i++) { Arr[pos++] = arr[i]; } // Copying remaining element for ( int i = 0; i < minIndex; i++) { Arr[pos++] = arr[i]; } // Printing target array for ( int i = 0; i < n; i++) { Console.Write(Arr[i] + " " ); } } // Driver code public static void Main(String[] args) { int N = 8; int []arr = { 4, 6, 2, 6, 8, 2, 6, 4 }; // Function Call printArr(arr, N); } } // This code is contributed by shivanisinghss2110 |
Javascript
<script> // Javascript program for above approach // Function to print target array function printArr(arr, n) { // Sort the given array arr.sort((a, b) => a - b); // Seeking for index of elements // with minimum diff. let minDifference = Number.MAX_SAFE_INTEGER; let minIndex = -1; // Seeking for index for (let i = 1; i < n; i++) { if (minDifference > Math.abs(arr[i] - arr[i - 1])) { minDifference = Math.abs(arr[i] - arr[i - 1]); minIndex = i - 1; } } // To store target array let Arr = new Array(n); Arr[0] = arr[minIndex]; Arr[n - 1] = arr[minIndex + 1]; let pos = 1; // Copying element for (let i = minIndex + 2; i < n; i++) { Arr[pos++] = arr[i]; } // Copying remaining element for (let i = 0; i < minIndex; i++) { Arr[pos++] = arr[i]; } // Printing target array for (let i = 0; i < n; i++) { document.write(Arr[i] + " " ); } } // Driver Code // Given Input let N = 8; let arr = [ 4, 6, 2, 6, 8, 2, 6, 4 ]; // Function Call printArr(arr, N); // This code is contributed by gfgking </script> |
2 4 4 6 6 6 8 2
Time complexity: O(N*logN)
Auxiliary Space: O(N)