algoadvance

Leetcode 1299. Replace Elements with Greatest Element on Right Side

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.

You need to solve it with O(n) time complexity.

Clarifying Questions

  1. What is the size range of the input array?
    • The size can be between 1 and 10^4.
  2. What are the possible values for elements in the array?
    • The elements can range between 1 and 10^5.
  3. Can the input array be empty?
    • According to the problem constraints, it will always have at least one element.

Strategy

  1. Iterate from Right to Left: Start iterating the array from the second to last element and move towards the beginning.
  2. Track the Maximum: Keep track of the maximum value encountered so far to the right of the current element.
  3. Replace Elements: Replace the current element with the maximum value and update the maximum if the current element is larger.

This approach ensures we only traverse the array once linearly, achieving the desired time complexity of O(n).

Code

#include <vector>
#include <iostream>
using namespace std;

vector<int> replaceElements(vector<int>& arr) {
    int n = arr.size();
    int maxRight = -1;
    
    // Iterate from right to left
    for (int i = n - 1; i >= 0; --i) {
        int current = arr[i];
        arr[i] = maxRight;
        if (current > maxRight) {
            maxRight = current;
        }
    }
    
    return arr;
}

// Function to print the array for debugging purposes
void printArray(const vector<int>& arr) {
    for (int val : arr) {
        cout << val << " ";
    }
    cout << endl;
}

// Example usage
int main() {
    vector<int> arr = {17, 18, 5, 4, 6, 1};
    vector<int> result = replaceElements(arr);
    printArray(result);  // Expected output: [18, 6, 6, 6, 1, -1]
    return 0;
}

Time Complexity

This solution is optimal in terms of both time and space complexity.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI