Smallest Greater Element In Whole Array Geeks For Geeks

Problem Link:

https://practice.geeksforgeeks.org/problems/smallest-greater-elements-in-whole-array2751/1

(It is also the problem of the day for 25-03-2022)

class Complete{

    

   

    // Function for finding maximum and value pair

    

   

    

    public static int[] greaterElement (int arr[], int n) {

        int arr1[]=new int[arr.length];

       for(int i=0;i<arr.length;i++){

           arr1[i]=arr[i];

       }

       Arrays.sort(arr1);

       HashMap<Integer,Integer>map=new HashMap<Integer,Integer>();

       for(int i=0;i<arr.length-1;i++){

          map.put(arr1[i],arr1[i+1]);

       }

       map.put(arr1[n-1],-10000000);

       

       for(int i=0;i<arr.length;i++){

           arr[i]=map.get(arr[i]);

       }

       return arr;

       

       

    }

       

       

}

Time Complexity: O(NLogN)[Sorting of array][GFG Time:3.1/10.1]

Space Complexity: O(N)[Array Is Given]

Total Test Cases:300

Auxiliary Space: O(N)[Additional Array Is Used]

Approach Used:

Here we need to find out whether an element having greater value than the elements present in the array exists in the same array or not.

If yes then at that index we will modify that element by its higher value and if not then we will make it -10000000.

Now in the array for a particular element higher value than that element can exist anywhere in the array. It is so because the array is not sorted.

First, we will copy the original array content into another array.

Then we will sort the newly created array.

How does sorting help us?

After sorting the duplicate array we created we will get all the values with their greater element. It means every element except the last element will have a greater value as their right adajcent element.

So after sorting we will store the values with their greater element in the hashmap.

For the last element we know no greater element will exist as itself it is the biggest element so we will store it in the map and provide -10000000 as value.

Why do we use hashmap hear?

It is so because the values in the sorted array will be in ascending order while the question array given does have sorted representation, so the element present at index i in the original array may not be the same as the element present at that index in a sorted array. So we need a map that will store the original elements and moreover, it will store the elements having a value greater than originally given elements as the value in the map.

Now we will traverse according to the original array and modify the array elements with the values stored in the map.

Now we will get the array with greater value as compared with the elements present in the original array.

"Thanks For Reading.😇"

"Share Further To Increase Knowledge Treasure.😊"