{"id":9295,"date":"2022-08-25T11:20:25","date_gmt":"2022-08-25T11:20:25","guid":{"rendered":"https:\/\/www.prepbytes.com\/blog\/?p=9295"},"modified":"2022-09-13T12:54:33","modified_gmt":"2022-09-13T12:54:33","slug":"next-greater-element-2","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/next-greater-element-2\/","title":{"rendered":"Next Greater Element"},"content":{"rendered":"

\"\"<\/p>\n

Problem statement<\/h3>\n

Given an array, consisting of n elements, find the next greater element of each element. The next greater element of any element is the first larger element to its right.<\/p>\n

Input<\/strong>: Integer array of size of n.
\nOutput<\/strong>: Integer array of size n.<\/p>\n

Test cases<\/strong>:
\nInput<\/strong>:
\n[1, 4, 2, 17, 9, 12]<\/p>\n

Output<\/strong>:
\n[4, 17, 17, -1, 12, -1]<\/p>\n

Explanation:<\/h4>\n
    \n
  • Output[0] = 4 because the next element greater than 1 is 4.<\/li>\n
  • Output[1] = 17 because the next element greater than 4 is 17.<\/li>\n
  • Output[2] = 17 because the next element greater than 2 is 4.<\/li>\n
  • Output[3] = -1 because there is no element greater than 17 to its right side.<\/li>\n
  • Output[4] = 12 because the next element greater than 2 is 12.<\/li>\n
  • Output[5] = -1 because there is no element on the right side of 12<\/li>\n<\/ul>\n

    Naive Approach – Brute Force<\/h3>\n

    We will iterate each element of the given array and for each element we will check all the elements to its right.
    \nThe answer of any element will be the first element greater than itself. If we don’t find any greater element than the answer of that element will be -1.<\/p>\n

    Algorithm<\/h4>\n
    1. Initialize an empty array\n2. For each i in 0 to n:\n    a. For each j in i + 1 to n: \n        If  arr[j] > f arr[i], then ans[i] = arr[j]\n    b. If we does not found the greater element, then \n        ans[i] = -1\n3. Return ans array.<\/code><\/pre>\n
    Code Implementation:<\/h3>\n\t\t\t\t\t\t