💬 Discord
Sign In
NeetCode #4LC-1299EasyArrays & Hashing
← Back to All Problems

#4 · #1299 · Replace Elements with Greatest Element on Right Side(将每个元素替换为右侧最大元素)

📌 Problem Statement & Constraints

Given an array arr, replace every element with the greatest element among the elements to its right, and replace the last element with -1. Return the resulting array. Constraints: 1 <= arr.length <= 10^4, 1 <= arr[i] <= 10^5.

💡 Core Algorithmic Approaches

  1. Scanning right to left makes the answer incremental: while walking leftward you only need to remember the maximum seen so far.
  2. Keep best, the maximum of all elements strictly to the right of the current index, initialised to -1.
  3. For each index from n-1 down to 0: save the current value, write best into that slot, then update best = max(best, saved).
  4. Order matters -- the old value must be captured before being overwritten, since it feeds the next iteration.

💻 Benchmark Python3 Implementation

class Solution:
    def replaceElements(self, arr: List[int]) -> List[int]:
        best = -1                          # nothing to the right of the last index
        for i in range(len(arr) - 1, -1, -1):
            cur = arr[i]
            arr[i] = best                  # greatest element to the right
            best = max(best, cur)          # include the current element for the next step
        return arr

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): a single right-to-left pass with constant work per element.
💾 Space Complexity
O(1) extra: the result is written in place over the input.

⚠️ Interview Pitfalls & Follow-ups

  • Scanning left to right and re-scanning the suffix: O(n^2) and unnecessary.
  • Updating best before writing arr[i]: the current element would replace itself, giving wrong values.
  • Initialising best to arr[-1]: the last element's answer must be -1, not its own value.
  • Assuming the array can be sorted: positions are fixed, so sorting destroys the problem.