8. Replace Elements with Greatest Element on Right Side

🔗 LeetCode Problem: 1299. Replace Elements with Greatest Element on Right Side
📊 Difficulty: Easy
🏷️ Topics: Array

Problem Statement

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 → max of [18,5,4,6,1] = 18
- index 1 → max of [5,4,6,1] = 6
- index 2 → max of [4,6,1] = 6
- index 3 → max of [6,1] = 6
- index 4 → max of [1] = 1
- index 5 → -1 (last element)

Example 2:

Input: arr = [400]
Output: [-1]
Explanation: Single element → replace with -1

Constraints: - 1 <= arr.length <= 10^4 - 1 <= arr[i] <= 10^5

---

🎨 Visual Understanding

The Problem Visualized

Input: arr = [17, 18, 5, 4, 6, 1]

For each element, find max to its right:

Index 0: arr[0]=17
  Right side: [18, 5, 4, 6, 1]
  Max: 18
  Replace: 17 → 18

Index 1: arr[1]=18
  Right side: [5, 4, 6, 1]
  Max: 6
  Replace: 18 → 6

Index 2: arr[2]=5
  Right side: [4, 6, 1]
  Max: 6
  Replace: 5 → 6

Index 3: arr[3]=4
  Right side: [6, 1]
  Max: 6
  Replace: 4 → 6

Index 4: arr[4]=6
  Right side: [1]
  Max: 1
  Replace: 6 → 1

Index 5: arr[5]=1
  Right side: []
  No elements → -1
  Replace: 1 → -1

Result: [18, 6, 6, 6, 1, -1]

Brute Force vs Optimal Visualization

❌ Brute Force (Left to Right):
For each position, scan all elements to the right

[17, 18, 5, 4, 6, 1]
 ↓
 Scan: 18,5,4,6,1 → max=18

    [18, 5, 4, 6, 1]
     ↓
     Scan: 5,4,6,1 → max=6

        [5, 4, 6, 1]
         ↓
         Scan: 4,6,1 → max=6

Many redundant comparisons!
Time: O(n²)


✅ Optimal (Right to Left):
Track maximum as we go backwards

[17, 18, 5, 4, 6, 1]
                   ↓
                   maxRight=-1, result[5]=-1

              [6, 1, -1]
               ↓
               maxRight=1, result[4]=1

           [4, 6, 1, -1]
            ↓
            maxRight=6, result[3]=6

        [5, 4, 6, 1, -1]
         ↓
         maxRight=6, result[2]=6

     [18, 5, 6, 6, 1, -1]
      ↓
      maxRight=6, result[1]=6

  [17, 18, 6, 6, 1, -1]
   ↓
   maxRight=18, result[0]=18

Single pass, track max!
Time: O(n)

---

🎯 Approach 1: Brute Force (Nested Loop)

The Most Natural Thinking 💭

Core Logic:

For each element at index i:
- Scan all elements from i+1 to end
- Find maximum in that range
- Replace arr[i] with that maximum

Last element: Replace with -1 (no elements to right)

Why This Works: - Directly implements problem statement - For each position, finds actual max to its right - Easy to understand and code

Why This is Slow: - For each element, scan remaining array - Nested loops → O(n²) complexity - Many redundant comparisons (recalculating same maxes)

Implementation

public int[] replaceElements(int[] arr) {
    int n = arr.length;

    // For each element except last
    for (int i = 0; i < n - 1; i++) {
        // Find max in remaining array
        int maxRight = arr[i + 1];
        for (int j = i + 2; j < n; j++) {
            maxRight = Math.max(maxRight, arr[j]);
        }
        arr[i] = maxRight;
    }

    // Last element becomes -1
    arr[n - 1] = -1;

    return arr;
}

Step-by-Step Execution: arr = [17,18,5,4,6,1]

Initial: arr = [17, 18, 5, 4, 6, 1]

i=0: Find max in [18,5,4,6,1]
├─ maxRight = 18
├─ Compare with 5: max(18,5) = 18
├─ Compare with 4: max(18,4) = 18
├─ Compare with 6: max(18,6) = 18
├─ Compare with 1: max(18,1) = 18
└─ arr[0] = 18
   arr = [18, 18, 5, 4, 6, 1]

i=1: Find max in [5,4,6,1]
├─ maxRight = 5
├─ Compare with 4: max(5,4) = 5
├─ Compare with 6: max(5,6) = 6
├─ Compare with 1: max(6,1) = 6
└─ arr[1] = 6
   arr = [18, 6, 5, 4, 6, 1]

i=2: Find max in [4,6,1]
├─ maxRight = 4
├─ Compare with 6: max(4,6) = 6
├─ Compare with 1: max(6,1) = 6
└─ arr[2] = 6
   arr = [18, 6, 6, 4, 6, 1]

i=3: Find max in [6,1]
├─ maxRight = 6
├─ Compare with 1: max(6,1) = 6
└─ arr[3] = 6
   arr = [18, 6, 6, 6, 6, 1]

i=4: Find max in [1]
├─ maxRight = 1
└─ arr[4] = 1
   arr = [18, 6, 6, 6, 1, 1]

Last element:
└─ arr[5] = -1
   arr = [18, 6, 6, 6, 1, -1]

Result: [18, 6, 6, 6, 1, -1]

⏰ Time: O(n²) - nested loops
💾 Space: O(1) - in-place modification

---

✅ Approach 2: Right to Left with Running Max (Optimal)

The Breakthrough Insight 💡

Core Logic:

Key Observation:
When scanning left-to-right, we recalculate max many times
What if we scan RIGHT-TO-LEFT and track max as we go?

Strategy:
1. Start from rightmost element
2. Keep track of maximum seen so far (going right to left)
3. For current element: replace with maxRight
4. Update maxRight to include current element

Why this works:
- As we move left, maxRight already knows the max to the right
- Each element processed once
- No redundant comparisons

Mathematical Insight:

For position i:
  maxRight[i] = max(arr[i+1], arr[i+2], ..., arr[n-1])

When going right-to-left:
  maxRight[i] = max(arr[i+1], maxRight[i+1])

We build maxRight incrementally!

Why This is Better: - Single pass through array - O(n) time complexity - Track running maximum as we scan backwards - No nested loops needed

Implementation

public int[] replaceElements(int[] arr) {
    int n = arr.length;
    int maxRight = -1;  // Start with -1 for last element

    // Scan from right to left
    for (int i = n - 1; i >= 0; i--) {
        int current = arr[i];     // Save current value
        arr[i] = maxRight;        // Replace with max to right
        maxRight = Math.max(maxRight, current);  // Update max
    }

    return arr;
}

Step-by-Step Execution: arr = [17,18,5,4,6,1]

Initial State:
═══════════════════════════════════════════════════════════════════
arr = [17, 18, 5, 4, 6, 1]
maxRight = -1 (start value for last element)
Scan direction: RIGHT ← LEFT
═══════════════════════════════════════════════════════════════════

Iteration 1: i=5 (last element)
├─ current = arr[5] = 1
├─ arr[5] = maxRight = -1  ← Replace with -1
├─ maxRight = max(-1, 1) = 1  ← Update max
└─ arr = [17, 18, 5, 4, 6, -1]
   Think: "Last element is -1, now max to right is 1"

Iteration 2: i=4
├─ current = arr[4] = 6
├─ arr[4] = maxRight = 1  ← Replace with max to right
├─ maxRight = max(1, 6) = 6  ← Update max
└─ arr = [17, 18, 5, 4, 1, -1]
   Think: "Element at 4 sees max=1 to right, now max is 6"

Iteration 3: i=3
├─ current = arr[3] = 4
├─ arr[3] = maxRight = 6  ← Replace with max to right
├─ maxRight = max(6, 4) = 6  ← Max stays 6
└─ arr = [17, 18, 5, 6, 1, -1]
   Think: "Element at 3 sees max=6 to right"

Iteration 4: i=2
├─ current = arr[2] = 5
├─ arr[2] = maxRight = 6  ← Replace with max to right
├─ maxRight = max(6, 5) = 6  ← Max stays 6
└─ arr = [17, 18, 6, 6, 1, -1]
   Think: "Element at 2 sees max=6 to right"

Iteration 5: i=1
├─ current = arr[1] = 18
├─ arr[1] = maxRight = 6  ← Replace with max to right
├─ maxRight = max(6, 18) = 18  ← Update max to 18
└─ arr = [17, 6, 6, 6, 1, -1]
   Think: "Element at 1 sees max=6, now max becomes 18"

Iteration 6: i=0
├─ current = arr[0] = 17
├─ arr[0] = maxRight = 18  ← Replace with max to right
├─ maxRight = max(18, 17) = 18  ← Max stays 18
└─ arr = [18, 6, 6, 6, 1, -1]
   Think: "Element at 0 sees max=18 to right"

═══════════════════════════════════════════════════════════════════
🎯 FINAL RESULT: [18, 6, 6, 6, 1, -1]
═══════════════════════════════════════════════════════════════════

Summary: Single pass, tracked max as we went right-to-left

Another Example: arr = [400]

Single element case:

Iteration 1: i=0
├─ current = 400
├─ arr[0] = maxRight = -1  ← Only element, replace with -1
├─ maxRight = max(-1, 400) = 400
└─ arr = [-1]

Result: [-1]

⏰ Time: O(n) - single pass
💾 Space: O(1) - in-place, only one variable

---

🔍 Edge Cases

Case 1: Single element
Input: [5]
Output: [-1]
Strategy: Only element → always -1

Case 2: Two elements
Input: [2, 1]
Output: [1, -1]
Strategy: First gets second, second gets -1

Case 3: Ascending order
Input: [1, 2, 3, 4, 5]
Output: [5, 5, 5, 5, -1]
Strategy: Max is always last element

Case 4: Descending order
Input: [5, 4, 3, 2, 1]
Output: [4, 3, 2, 1, -1]
Strategy: Each element replaced by next element

Case 5: All same elements
Input: [3, 3, 3, 3]
Output: [3, 3, 3, -1]
Strategy: Max is always same value

Case 6: Large numbers
Input: [100000, 99999, 100000]
Output: [100000, 100000, -1]

Case 7: Two identical max values
Input: [1, 5, 2, 5, 3]
Output: [5, 5, 5, 3, -1]
Strategy: First max chosen, but value same

Case 8: Max at beginning
Input: [10, 1, 2, 3]
Output: [3, 3, 3, -1]
Strategy: First element's value doesn't matter for others

---

Common Mistakes

Mistake 1: Not handling last element specially
❌ Wrong: Try to find max to right of last element
✓ Right: Last element always becomes -1

Mistake 2: Scanning left-to-right
❌ Wrong: O(n²) with nested loops
✓ Right: Scan right-to-left with running max O(n)

Mistake 3: Updating maxRight before using it
❌ Wrong: 
    maxRight = Math.max(maxRight, arr[i]);
    arr[i] = maxRight;
✓ Right: 
    int current = arr[i];
    arr[i] = maxRight;
    maxRight = Math.max(maxRight, current);

Mistake 4: Wrong initial value for maxRight
❌ Wrong: maxRight = 0 or Integer.MIN_VALUE
✓ Right: maxRight = -1 (as per problem requirement)

Mistake 5: Not preserving current value
❌ Wrong: Overwrite arr[i] then try to use it for max
✓ Right: Save current value before overwriting

---

🎯 Key Takeaways

⚡ Algorithm Comparison

Approach 1: Brute Force (Left to Right)
  Time: O(n²) - nested loops
  Space: O(1)
  Use: Never (too slow)

Approach 2: Right to Left with Running Max (OPTIMAL)
  Time: O(n) - single pass
  Space: O(1)
  Use: Always (fastest solution)

🔑 The Core Insight

Problem transformation:
  From: "For each element, find max to its right"
  To: "Scan backwards, track max as we go"

Why backwards is better:
→ When at position i, we already know max(i+1...n)
→ No need to recalculate
→ Just update running max with current element

Pattern: Running maximum from right to left

🎯 Pattern Recognition

Problem Type: Array Transformation with Rightward Dependencies
Core Pattern: Right-to-Left Scan with Running State

When to Apply:
✓ Each element depends on elements to its right
✓ Can maintain running aggregate (max, sum, etc.)
✓ Want to avoid nested loops
✓ In-place modification allowed

Key Technique:
→ Reverse iteration direction
→ Maintain running state (max, min, sum, etc.)
→ Update state after using it

Related Problems:
- Next Greater Element (LC 496)
- Daily Temperatures (LC 739)
- Online Stock Span (LC 901)
- Trapping Rain Water (LC 42)

🧠 Interview Strategy

Step 1: "Need max to right of each element"
Step 2: "Brute force scans right for each element - O(n²)"
Step 3: "Key insight: scan RIGHT-TO-LEFT instead"
Step 4: "Track running maximum as we go backwards"
Step 5: "Single pass solution: O(n) time, O(1) space"

---

📝 Quick Revision Notes

🎯 Core Concept:

Scan array right-to-left, maintain running maximum. For each element, replace with current max, then update max with current element.

⚡ Quick Implementation:

public int[] replaceElements(int[] a) {
   int len = a.length;
   int maxSoFar = a[len - 1];

   for(int i = len - 2; i >= 0 ; i--) {
      // Before replacing, save the current element to compare and update maxSoFar
      int temp = a[i];
      // Replace the current element with max element from right side
      a[i] = maxSoFar;
      // Updating maxSoFar with current element (temp) and prev maxSoFar
      maxSoFar = Math.max(maxSoFar, temp);
   }

   // last element value will be always -1
   a[len - 1] = -1;

   return a;
}

🔑 Key Insights:

• Scan backwards to avoid redundant calculations
• Running maximum eliminates nested loops
• Save current before overwriting
• Update max after replacing element
• Last element always becomes -1

🎪 Memory Aid:

"Go backwards, remember the biggest, replace and update!"
Think: "Right-to-left with running max = O(n)"

---

Related Patterns

• Next Greater Element (LC 496)
• Daily Temperatures (LC 739)
• Online Stock Span (LC 901)

---

Happy practicing! 🎯