615. Replace Elements with Greatest Element on Right Side
You receive an integer array arr. Build and return a new array of the same length where each position holds the largest value that appears anywhere to its right in the original array.
The last position has nothing to its right, so it becomes -1.
For example, in [17, 18, 5, 4, 6, 1] the value at index 0 becomes 18 (the biggest of everything after it), while index 4 becomes 1 and index 5 becomes -1.
Example 1:
Input: arr = [17, 18, 5, 4, 6, 1]
Output: [18, 6, 6, 6, 1, -1]
Explanation: To the right of 17 the maximum is 18; to the right of 18 it is 6; the suffixes after indices 2 and 3 also peak at 6; after index 4 only 1 remains; the final slot is -1.
Example 2:
Input: arr = [400]
Output: [-1]
Explanation: A single element has no right side, so the only slot becomes -1.
Constraints:
- 1 ≤ arr.length ≤ 10⁴
- 0 ≤ arr[i] ≤ 10⁵
Hints:
The direct approach rescans the whole right side for every index — that repeats almost identical scans n times.
The maximum to the right of index i is just max(arr[i+1], maximum to the right of i+1). Walk from the END, carrying one running maximum, and fill answers as you go.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: arr = [17, 18, 5, 4, 6, 1]
Expected output: [18, 6, 6, 6, 1, -1]