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
Solution:
using System;
using System.Collections.Generic;
using System.Text;
namespace LeetCode.AskGif.Easy.Array
{
public class ReplaceElementsSoln
{
public int[] ReplaceElements(int[] arr)
{
var temp = new int[arr.Length];
temp[arr.Length - 1] = arr[arr.Length - 1];
for (int i = arr.Length-2; i >= 0; i--)
{
if (arr[i] > temp[i + 1])
{
temp[i] = arr[i];
}
else
{
temp[i] = temp[i + 1];
}
}
var res = new int[arr.Length];
for (int i = 0; i < arr.Length-1; i++)
{
res[i] = temp[i + 1];
}
res[arr.Length - 1] = -1;
return res;
}
}
}
Time Complexity: O(n)
Space Complexity: O(n)
Unit Tests:
using LeetCode.AskGif.Easy.Array;
using Microsoft.VisualStudio.TestTools.UnitTesting;
using System;
using System.Collections.Generic;
using System.Text;
namespace CodingUnitTest.Easy.Array
{
[TestClass]
public class ReplaceElementsSolnTests
{
[TestMethod]
public void ReplaceElementsSoln_First()
{
var arr = new int[] { 17, 18, 5, 4, 6, 1 };
var output = new int[] { 18, 6, 6, 6, 1, -1 };
var res = new ReplaceElementsSoln().ReplaceElements(arr);
AreEqual(res, output);
}
private void AreEqual(int[] res, int[] output)
{
Assert.AreEqual(res.Length, output.Length);
for (int i = 0; i < res.Length; i++)
{
Assert.AreEqual(res[i], output[i]);
}
}
}
}
