1299. Replace Elements With Greatest Element on Right Side

📝 Problem Details

• Title: 1299. Replace Elements With Greatest Element on Right Side
• Link: https://leetcode.com/problems/replace-elements-with-greatest-element-on-right-side/
• Difficulty: Easy
• Tags/Categories: Arrays

💭What Were My Initial Thoughts?

- we need to replace each element in the array with the greatest element to its right
- naive approach would be checking all elements to the right for each element
	- this would be O(n^2) - not efficient enough for us 
- we can iterate from right to left to keep track of the max element so far

🤔What Did I Struggle With?

~

💡 Explanation of Solution

- init maxElement to -1, since the last element should always be replaced with -1
- iterate backwards through the array (right to left)
- at each index
	- store the current element temporarily
	- replace the current element with maxElement (the greatest element to its right)
	- update maxElement to be the maximum of the stored element and maxElement
- continue this process until the start of the array
- return the modified array

⌛ Complexity Analysis

Time Complexity: O(n)

Space Complexity: O(1)

💻 Implementation of Solution

#include <vector>
#include <algorithm> // for std::max
using namespace std;
 
class Solution {
public:
    vector<int> replaceElements(vector<int>& arr) {
        // Start at the second last index since we know the last element will always be -1
        int maxElement = -1; // Initialize with -1 as the last element will be replaced
        
        for (int i = arr.size() - 1; i >= 0; i--) {
            int current = arr[i]; // Store the current element before overwriting
            arr[i] = maxElement;  // Replace current element with the greatest to its right
            maxElement = max(maxElement, current); // Update the maximum element
        }
        
        return arr;
    }
};