LeetCode 1299. Replace Elements with Greatest Element on Right Side Solution in Java, C++, Python & More | Explanation + Code

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 <= 104
• 1 <= arr[i] <= 105

Solutions

Solution 1: Reverse Traversal

We use a variable mx to record the maximum value to the right of the current position, initially mx = -1.

Then we traverse the array from right to left. For each position i, we denote the current value as x, update the current position's value to mx, and then update mx = max(mx, x).

Finally, return the original array.

The time complexity is O(n), where n is the length of the array. The space complexity is O(1).

PythonJavaC++GoTypeScript

class Solution: def replaceElements(self, arr: List[int]) -> List[int]: mx = -1 for i in reversed(range(len(arr))): x = arr[i] arr[i] = mx mx = max(mx, x) return arr(code-box)

class Solution { public int[] replaceElements(int[] arr) { for (int i = arr.length - 1, mx = -1; i >= 0; --i) { int x = arr[i]; arr[i] = mx; mx = Math.max(mx, x); } return arr; } }(code-box)

class Solution { public: vector<int> replaceElements(vector<int>& arr) { for (int i = arr.size() - 1, mx = -1; ~i; --i) { int x = arr[i]; arr[i] = mx; mx = max(mx, x); } return arr; } };(code-box)

func replaceElements(arr []int) []int { for i, mx := len(arr)-1, -1; i >= 0; i-- { x := arr[i] arr[i] = mx mx = max(mx, x) } return arr }(code-box)

function replaceElements(arr: number[]): number[] { for (let i = arr.length - 1, mx = -1; ~i; --i) { const x = arr[i]; arr[i] = mx; mx = Math.max(mx, x); } return arr; }(code-box)