Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1299.html

1299. Replace Elements with Greatest Element on Right Side (Easy)

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

Related Topics:
Array

Solution 1.

// OJ: https://leetcode.com/problems/replace-elements-with-greatest-element-on-right-side/
// Time: O(N)
// Space: O(1)
class Solution {
public:
    vector<int> replaceElements(vector<int>& A) {
        int mx = -1;
        for (int i = A.size() - 1; i >= 0; --i) {
            int n = A[i];
            A[i] = mx;
            mx = max(mx, n);
        }
        return A;
    }
};

  • class Solution {
    public int[] replaceElements(int[] arr) {
        if (arr == null || arr.length == 0)
            return arr;
        int length = arr.length;
        int[] newArray = new int[length];
        newArray[length - 1] = -1;
        if (length == 1)
            return newArray;
        newArray[length - 2] = arr[length - 1];
        for (int i = length - 3; i >= 0; i--) {
            int nextNum = arr[i + 1];
            newArray[i] = Math.max(newArray[i + 1], nextNum);
        }
        return newArray;
    }
}

############

class Solution {
    public int[] replaceElements(int[] arr) {
        for (int i = arr.length - 1, max = -1; i >= 0; --i) {
            int t = arr[i];
            arr[i] = max;
            max = Math.max(max, t);
        }
        return arr;
    }
}

  • // OJ: https://leetcode.com/problems/replace-elements-with-greatest-element-on-right-side/
// Time: O(N)
// Space: O(1)
class Solution {
public:
    vector<int> replaceElements(vector<int>& A) {
        int mx = -1;
        for (int i = A.size() - 1; i >= 0; --i) {
            int n = A[i];
            A[i] = mx;
            mx = max(mx, n);
        }
        return A;
    }
};

  • class Solution:
    def replaceElements(self, arr: List[int]) -> List[int]:
        m = -1
        for i in range(len(arr) - 1, -1, -1):
            t = arr[i]
            arr[i] = m
            m = max(m, t)
        return arr

############

# 1299. Replace Elements with Greatest Element on Right Side
# https://leetcode.com/problems/replace-elements-with-greatest-element-on-right-side/

class Solution:
    def replaceElements(self, A: List[int]) -> List[int]:
        mx = -1
        
        for i in range(len(A)-1, -1, -1):
            A[i],mx = mx, max(A[i], mx)
        
        return A

All Problems

All Solutions