DEV Community

Abhishek Chaudhary
Abhishek Chaudhary

Posted on

Replace Elements with Greatest Element on Right Side

Given an array arr, replace every element in that array with the greatest element among the elements to its right, and replace the last element with -1.

After doing so, return the array.

Example 1:

Input: arr = [17,18,5,4,6,1]
Output: [18,6,6,6,1,-1]
Explanation:

  • index 0 --> the greatest element to the right of index 0 is index 1 (18).
  • index 1 --> the greatest element to the right of index 1 is index 4 (6).
  • index 2 --> the greatest element to the right of index 2 is index 4 (6).
  • index 3 --> the greatest element to the right of index 3 is index 4 (6).
  • index 4 --> the greatest element to the right of index 4 is index 5 (1).
  • index 5 --> there are no elements to the right of index 5, so we put -1.

Example 2:

Input: arr = [400]
Output: [-1]
Explanation: There are no elements to the right of index 0.

Constraints:

  • 1 <= arr.length <= 104
  • 1 <= arr[i] <= 105

SOLUTION:

class Solution:
#     def makeSeg(self, arr, i, j):
#         seg = self.seg
#         if (i, j) in seg:
#             return seg[(i, j)]
#         if i == j:
#             seg[(i, j)] = arr[i]
#             return arr[i]
#         mid = (i + j) // 2
#         curr = max(self.makeSeg(arr, i, mid), self.makeSeg(arr, mid + 1, j))
#         seg[(i, j)] = curr
#         return curr

#     def getMax(self, arr, i, j, ni, nj):
#         seg = self.seg
#         if ni >= i and nj <= j:
#             return seg[(ni, nj)]
#         if (ni < i and nj < i) or (ni > j and nj > j):
#             return float('-inf')
#         mid = (ni + nj) // 2
#         return max(self.getMax(arr, i, j, ni, mid), self.getMax(arr, i, j, mid + 1, nj))

#     def replaceElements(self, arr: List[int]) -> List[int]:
#         n = len(arr)
#         self.seg = {}
#         self.makeSeg(arr, 0, n - 1)
#         for i in range(n):
#             if i < n - 1:
#                 arr[i] = self.getMax(arr, i + 1, n, 0, n - 1)
#             else:
#                 arr[i] = -1
#         return arr

    def replaceElements(self, arr: List[int]) -> List[int]:
        n = len(arr)
        op = [-1] * n
        currMax = float('-inf')
        for i in range(n - 1, 0, -1):
            currMax = max(currMax, arr[i])
            op[i - 1] = currMax
        return op
Enter fullscreen mode Exit fullscreen mode

Top comments (0)