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]

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

Hints:
Loop through the array starting from the end.
Keep the maximum value seen so far.

Using Additional Maximum Array

Let’s allocate another array storing the maximum values from the right. Then, it is a straightforward solution:

1
2
3
4
5
6
7
8
9
10
11
12

class Solution {
public:
    vector<int> replaceElements(vector<int>& arr) {
        if (arr.empty()) return {};
        vector<int> vmax(arr.size());
        for (int i = arr.size() - 2; i >= 0; -- i) {
            vmax[i] = max(vmax[i + 1], arr[i + 1]);
        }
        vmax[arr.size() - 1] = -1;
        return vmax;
    }
};

class Solution {
public:
    vector<int> replaceElements(vector<int>& arr) {
        if (arr.empty()) return {};
        vector<int> vmax(arr.size());
        for (int i = arr.size() - 2; i >= 0; -- i) {
            vmax[i] = max(vmax[i + 1], arr[i + 1]);
        }
        vmax[arr.size() - 1] = -1;
        return vmax;
    }
};

Time complexity is O(N) as we are iterating the entire array.

Modifying the existing array

We can modify the existing array along the way, then we need a variable to save the current value in the array then update the current maximum, and store it in the next iteration.

1
2
3
4
5
6
7
8
9
10
11
12
13
14

class Solution {
public:
    vector<int> replaceElements(vector<int>& arr) {
        if (arr.empty()) return {};
        int mx = 0;
        for (int i = arr.size() - 1; i >= 0; -- i) {
            int a = arr[i];
            arr[i] = mx;
            mx = max(mx, a);
        }
        arr[arr.size() - 1] = -1;
        return arr;
    }
};

class Solution {
public:
    vector<int> replaceElements(vector<int>& arr) {
        if (arr.empty()) return {};
        int mx = 0;
        for (int i = arr.size() - 1; i >= 0; -- i) {
            int a = arr[i];
            arr[i] = mx;
            mx = max(mx, a);
        }
        arr[arr.size() - 1] = -1;
        return arr;
    }
};

O(N) time and O(1) constant space.

Using std::exchange() in C++

The C++ std::exchange() offers a cleaner implementation of above.

1
2
3
4
5
6
7
8
9
10
11
12

class Solution {
public:
    vector<int> replaceElements(vector<int>& arr) {
        if (arr.empty()) return {};
        int mx = 0;
        for (int i = arr.size() - 1; i >= 0; -- i) {
            mx = max(mx, exchange(arr[i], mx));
        }
        arr[arr.size() - 1] = -1;
        return arr;
    }
};

class Solution {
public:
    vector<int> replaceElements(vector<int>& arr) {
        if (arr.empty()) return {};
        int mx = 0;
        for (int i = arr.size() - 1; i >= 0; -- i) {
            mx = max(mx, exchange(arr[i], mx));
        }
        arr[arr.size() - 1] = -1;
        return arr;
    }
};

As you can see, the std::exchange(a, b) will be equivalent to the following:

1
2
3
4
5
6

template <class T>
T exchange(T a, T b) {
  T x = a;
  a = b;
  return x;
}

template <class T>
T exchange(T a, T b) {
  T x = a;
  a = b;
  return x;
}

Unlike the std::swap(), the second paramter won’t be modified. The original value of first parameter i.e. a will be returned.

–EOF (The Ultimate Computing & Technology Blog) —