Introduction

he Replace Elements with Greatest Element on Right Side problem involves replacing every element in the array with the greatest element among the elements to its right.

For the last element:

  • replace it with -1.

Given an array arr[] of size n, the task is to modify the array such that every element becomes the maximum element to its right side.

This is an important array problem that helps in understanding reverse traversal, running maximum, and optimization techniques.

Example

Input: arr[] = [17, 18, 5, 4, 6, 1]Output: [18, 6, 6, 6, 1, -1]
Explanation:
Right side maximum of 17 is 18
Right side maximum of 18 is 6
Right side maximum of 5 is 6
Right side maximum of 4 is 6
Right side maximum of 6 is 1
Last element becomes -1

Input: arr[] = [10, 9, 8, 7]
Output: [9, 8, 7, -1]
Explanation:
Each element is replaced with the largest element to its right.

Constraints

  1 <= n <= 10^5
-10^9 <= arr[i] <= 10^9

Approach 1 : Brute Force

Explanation

The simplest way to solve this problem is:

  1. For every element:
    • traverse all elements on its right side
  2. Find the maximum element
  3. Replace the current element with that maximum

This approach is easy to understand but repeatedly traversing the right side increases time complexity.

    Steps

    1. Traverse the array from index 0 to n-2.
    2. For every element:
      • find maximum element on the right side
    3. Replace current element with that maximum.
    4. Replace last element with -1.

Dry Run

Input Array: [17, 18, 5, 4, 6, 1]Traverse 17:
Right side elements = [18, 5, 4, 6, 1]
Maximum = 18
Replace 17 with 18
Traverse 18:
Right side elements = [5, 4, 6, 1]
Maximum = 6
Replace 18 with 6
Traverse 5:
Right side maximum = 6
Replace 5 with 6
Continue similarly...
Final Result:
[18, 6, 6, 6, 1, -1]

Brute Force Code 

Complexity Analysis

Time Complexity: O(n²)Explanation:
For every element, the right side is traversed again.

Space Complexity: O(1)
Explanation:
No extra data structures are used.

Approach 2 : Optimized Solution (Reverse Traversal)

Explanation

Instead of repeatedly searching the right side, we can traverse the array from right to left.

The idea is:

  1. Maintain the maximum element seen so far
  2. Replace current element with that maximum
  3. Update the running maximum

This avoids repeated traversals and improves efficiency.

Steps

  1. Initialize:
    • maxRight = -1
  2. Traverse the array from right to left.
  3. Store current element temporarily.
  4. Replace current element with maxRight.
  5. Update:
    • maxRight = max(maxRight, current element) 

Instead of repeatedly finding maximum:

  • Traverse array from right to left
  • Maintain running maximum

This avoids repeated scanning.

Why Reverse Traversal Works

When traversing from right:

  • We already know the maximum element seen so far
  • Replace current element directly

This makes the solution efficient.

Dry Run

Input Array: [17, 18, 5, 4, 6, 1]Initially:
maxRight = -1
Traverse 1:
Replace 1 with -1
Update maxRight = 1
Array:
[17, 18, 5, 4, 6, -1]
Traverse 6:
Replace 6 with 1
Update maxRight = 6
Array:
[17, 18, 5, 4, 1, -1]
Traverse 4:
Replace 4 with 6
Update maxRight = 6
Continue similarly...
Final Result:
[18, 6, 6, 6, 1, -1]

Optimized Code 

Complexity Analysis

Time Complexity: O(n)Explanation:
The array is traversed only once.

Space Complexity: O(1)
Explanation:
Only a few variables are used.

Edge Cases

  1. Array contains only one element
  2. Array is already decreasing
  3. Array contains duplicate elements
  4. Array contains negative numbers

Why This Problem is Important

This problem helps in understanding:

  1. Reverse traversal
  2. Running maximum concept
  3. In-place modification
  4. Traversal optimization
  5. Efficient replacement strategies

It is one of the most important array optimization interview problems.

Real-World Applications

Running maximum techniques are used in:

  1. Stock market analysis
  2. Data stream processing
  3. Sensor analytics
  4. Trend analysis systems
  5. Performance monitoring

Common Mistakes

  1. Updating maximum incorrectly
  2. Losing original values before replacement
  3. Traversing in wrong direction
  4. Forgetting last element replacement

Interview Tips

Interviewers often expect:

  1. Reverse traversal optimization
  2. O(n) solution
  3. In-place modification

Always explain why maintaining a running maximum avoids repeated traversals.

Related Questions

  1. Leaders in an Array
  2. Stock Buy and Sell
  3. Next Greater Element
  4. Prefix Maximum
  5. Suffix Maximum

Final Takeaway

The Replace Elements with Greatest Element on Right Side problem is an important array optimization problem that teaches reverse traversal, running maximum concepts, and efficient in-place modification techniques. Understanding this problem builds a strong foundation for advanced prefix/suffix and traversal-based interview problems.