Replace Elements with Greatest Element on Right Side

💡 Intuition

• When starting from the left, each index i has (n - i - 1) elements to its right, from which we need to determine the maximum. This approach has a time complexity of O(n ^2 ).

• When starting from the right, we can maintain a running maximum, and at each step, we only need to compare two values: num[i+1] and the maximum encountered so far. This approach has a time complexity of O(n).

🚀 Solution

function replaceElements(arr: number[]): number[] {
    let result : number[] = [];
    let length = arr.length;
    let maxnum = -1;

    for ( let i = length - 2; i >=0 ; i-- ) {
        maxnum = Math.max(maxnum,arr[i+1]);
        result[i] = maxnum
    }

    result[length-1] = -1;
    return result;
};

⏳ Time Complexity

• Since we are taking single loop for the array of length n, the time complexity will be O(n)