Given an integer array arr[] of size N, the task is to generate a new array by replacing ith element with its immediate right smaller neighbour i.e., by (i+t)th element if it is smaller.
Examples:
Input: N = 5, Arr[] = {4, 2, 1, 5, 3}
Output: 2 1 -1 3 -1
Explanation: Array elements are 4, 2, 1, 5, 3.
Next to 4 is 2 which is smaller, so we print 2. Next of 2 is 1 which is smaller, so we print 1. Next of 1 is 5 which is greater, so we print -1. Next of 5 is 3 which is smaller, so we print 3. Note that for last element, output is always going to be -1 because there is no element on right.Input: N = 6, Arr[] = {5, 6, 2, 3, 1, 7}
Output: -1 2 -1 1 -1 -1
Approach: To solve the problem follow the below idea:
The idea is to traverse the array and check if the next element is smaller or not. If next element is smaller then replace current element with next smaller element otherwise replace current element with -1.
Follow the steps below to implement the above idea:
- Iterate over the array i = 0 to i < size of array – 1
- Check if the current element is greater than the next element, (i.e, arr[i] > arr[i + 1])
- If true, replace arr[i] = arr[i + 1]
- Otherwise, replace arr[i] = -1
- Check if the current element is greater than the next element, (i.e, arr[i] > arr[i + 1])
Below is the implementation of the above approach.
C++
// C++ code to implement the approach#include <bits/stdc++.h>using namespace std;// Function to create the new arrayvoid immediateSmaller(vector<int>& arr, int n){ for (int i = 0; i < n - 1; i++) { if (arr[i] > arr[i + 1]) { arr[i] = arr[i + 1]; } else arr[i] = -1; } arr[n - 1] = -1;}// Driver codeint main(){ vector<int> arr = { 5, 6, 2, 3, 1, 7 }; int N = arr.size(); // Function Call immediateSmaller(arr, N); for (auto i : arr) cout << i << " "; return 0;} |
Java
// Java code to implement the approachimport java.io.*;class GFG { // Function to create the new array public static void immediateSmaller(int arr[], int n) { for (int i = 0; i < n - 1; i++) { if (arr[i] > arr[i + 1]) { arr[i] = arr[i + 1]; } else arr[i] = -1; } arr[n - 1] = -1; } // Driver Code public static void main(String[] args) { int arr[] = { 5, 6, 2, 3, 1, 7 }; int N = arr.length; // Function Call immediateSmaller(arr, N); for (int i : arr) System.out.print(i + " "); }}// This code is contributed by Rohit Pradhan |
Python3
# Python3 code to implement the approach# Function to create the new arraydef immediateSmaller(arr, n) : for i in range(n - 1) : if (arr[i] > arr[i + 1]) : arr[i] = arr[i + 1]; else : arr[i] = -1; arr[n - 1] = -1;# Driver codeif __name__ == "__main__" : arr = [ 5, 6, 2, 3, 1, 7 ]; N = len(arr); # Function Call immediateSmaller(arr, N); for i in arr: print(i, end = " "); # This code is contributed by AnkThon |
C#
// C# code to implement the approachusing System;class GFG { // Function to create the new array static void immediateSmaller(int[] arr, int n) { for (int i = 0; i < n - 1; i++) { if (arr[i] > arr[i + 1]) { arr[i] = arr[i + 1]; } else arr[i] = -1; } arr[n - 1] = -1; } // Driver Code public static void Main() { int[] arr = { 5, 6, 2, 3, 1, 7 }; int N = arr.Length; // Function Call immediateSmaller(arr, N); for (int i = 0; i < arr.Length; i++) Console.Write(arr[i] + " "); }}// This code is contributed by Samim Hossain Mondal. |
Javascript
// JavaScript code to implement the approach// Function to create the new arrayfunction immediateSmaller(arr, n){ for (let i = 0; i < n - 1; i++) { if (arr[i] > arr[i + 1]) { arr[i] = arr[i + 1]; } else arr[i] = -1; } arr[n - 1] = -1; return arr;}// Driver codearr = [ 5, 6, 2, 3, 1, 7 ];N = arr.length;// Function Callrslt = immediateSmaller(arr, N);let string = "";for (let i = 0; i < rslt.length ; i++) string += rslt[i] + " ";console.log(string);// This code is contributed by AnkThon |
-1 2 -1 1 -1 -1
Time Complexity: O(N)
Auxiliary Space: O(1)
