1299. Replace Elements with Greatest Element on Right Side

Description

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 <= 10⁴
• 1 <= arr[i] <= 10⁵

💡 Hint 1:
Loop through the array starting from the end.

💡 Hint 2:
Keep the maximum value seen so far.

Submitted Code

class Solution:
    def replaceElements(self, arr: List[int]) -> List[int]:
        n = len(arr)
        max_val = -1

        for i in range(n-1, -1, -1):
            arr[i], max_val = max_val, max(max_val, arr[i])
        
        return arr

Runtime: 20 ms | Beats 72.69%
Memory: 20.50 MB | Beats 28.28%

뒤에서부터 순회하는 방법이 가장 간단하다. 맨 마지막 원소는 무조건 -1이 되기 때문에 max_val도 -1로 시작했다.

Other Solutions

1st

class Solution:
    def replaceElements(self, arr: List[int]) -> List[int]:
        Max = arr[-1]
        arr[-1] = -1
        for i in range(len(arr)-2, -1, -1):
            temp = arr[i]
            arr[i] = Max
            if temp > Max: Max = temp 
        return arr

time complexity: 𝑂(𝑛)
space complexity: 𝑂(1)