Find original Array from the transformed Array
Given two arrays arr1[] of length N and arr2[] of length N – 1 and is built such that arr2[i] = max(arr1[i], arr1[i+1]) for all 1 ≤ i ≤ N-1. The task is to find the original array arr1 of length N. Multiple answers may exist.
Examples:
Input: N = 5, arr2 = {3, 4, 4, 5}
Output: {3, 3, 4, 4, 5}
Explanation: max(3, 3) = 3, max(3, 4) = 4, max(4, 4) = 4, max(4, 5) = 5Input: N = 6, arr2 = {0, 3, 4, 4, 3}
Output: {0, 0, 3, 4, 3, 3}
Explanation: max(0, 0) = 0, max(0, 3) = 3, max(3, 4) = 4, max(4, 3) = 4, max(3, 3) = 3
Approach: The idea is to use a greedy approach.
We can always set the first element of arr1 as first element of arr2 i.e. arr1[0] = arr2[0]. We can always set the last element of arr1 as last element of arr2 i.e. arr1[N-1] = arr2[N-2]. For rest of the indexes, we can set the value as minimum of elements at that index and the previous index, i.e. arr[i] and arr[i-1], then the conditions are always satisfied.
Below are the steps for the above approach:
- Create an empty result array.
- Set res[0] as the first element of given arr2.
- Set res[n-1] as last element of given arr2
- For i = 1 to n – 2, set res[i] = min (arr[i], arr[i-1])
- Print the result array.
Below is the code for the above approach:
C++
// C++ code for the above approach: #include <bits/stdc++.h> using namespace std; void findOriginalArray( int arr[], int n) { // Empty result array int res[n]; // Set last element and first elements, // same as last and first element // of arr2 res[n - 1] = arr[n - 2]; res[0] = arr[0]; // For rest of the elements, set the // elements as minimum of // arr[i[ & arr[i-1] for ( int i = 1; i <= n - 2; i++) { res[i] = min(arr[i], arr[i - 1]); } // Print the result for ( int i = 0; i < n; i++) cout << res[i] << " " ; cout << endl; } // Driver Code int main() { int N1 = 5; int arr21[] = { 3, 4, 4, 5 }; findOriginalArray(arr21, N1); int N2 = 6; int arr22[] = { 0, 3, 4, 4, 3 }; findOriginalArray(arr22, N2); return 0; } |
Java
import java.io.*; class GFG { public static void findOriginalArray( int [] arr, int n) { // Empty result array int [] res = new int [n]; // Set last element and first elements, // same as last and first element // of arr2 res[n - 1 ] = arr[n - 2 ]; res[ 0 ] = arr[ 0 ]; // For rest of the elements, set the // elements as minimum of // arr[i[ & arr[i-1] for ( int i = 1 ; i <= n - 2 ; i++) { res[i] = Math.min(arr[i], arr[i - 1 ]); } // Print the result for ( int i = 0 ; i < n; i++) { System.out.print(res[i] + " " ); } System.out.println(); } // Driver Code public static void main(String[] args) { int N1 = 5 ; int [] arr21 = { 3 , 4 , 4 , 5 }; findOriginalArray(arr21, N1); int N2 = 6 ; int [] arr22 = { 0 , 3 , 4 , 4 , 3 }; findOriginalArray(arr22, N2); } } |
Python3
def findOriginalArray(arr, n): # Empty result array res = [ 0 ] * n # Set last element and first elements, # same as last and first element # of arr2 res[n - 1 ] = arr[n - 2 ] res[ 0 ] = arr[ 0 ] # For rest of the elements, set the # elements as minimum of # arr[i] & arr[i-1] for i in range ( 1 , n - 1 ): res[i] = min (arr[i], arr[i - 1 ]) # Print the result for i in range (n): print (res[i], end = " " ) print () # Driver code N1 = 5 arr21 = [ 3 , 4 , 4 , 5 ] findOriginalArray(arr21, N1) N2 = 6 arr22 = [ 0 , 3 , 4 , 4 , 3 ] findOriginalArray(arr22, N2) |
C#
// C# code for the above approach: using System; class GFG { static void FindOriginalArray( int [] arr, int n) { // Empty result array int [] res = new int [n]; // Set last element and first elements, // same as last and first element // of arr2 res[n - 1] = arr[n - 2]; res[0] = arr[0]; // For rest of the elements, set the // elements as minimum of // arr[i] & arr[i-1] for ( int i = 1; i <= n - 2; i++) { res[i] = Math.Min(arr[i], arr[i - 1]); } // Print the result for ( int i = 0; i < n; i++) { Console.Write(res[i] + " " ); } Console.WriteLine(); } static void Main( string [] args) { int N1 = 5; int [] arr21 = { 3, 4, 4, 5 }; FindOriginalArray(arr21, N1); int N2 = 6; int [] arr22 = { 0, 3, 4, 4, 3 }; FindOriginalArray(arr22, N2); } } |
Javascript
function findOriginalArray(arr, n) { // Empty result array const res = new Array(n); // Set last element and first elements, // same as last and first element // of arr2 res[n - 1] = arr[n - 2]; res[0] = arr[0]; // For rest of the elements, set the // elements as minimum of // arr[i] & arr[i-1] for (let i = 1; i <= n - 2; i++) { res[i] = Math.min(arr[i], arr[i - 1]); } // Print the result console.log(res.join( " " )); } // Driver Code const N1 = 5; const arr21 = [3, 4, 4, 5]; findOriginalArray(arr21, N1); const N2 = 6; const arr22 = [0, 3, 4, 4, 3]; findOriginalArray(arr22, N2); |
3 3 4 4 5 0 0 3 4 3 3
Time Complexity: O(N)
Auxiliary Space: O(N)