Go/Leet Code
Arrays101 Replace Elements with Greatest Element on Right Side in GO
Gopythor
2022. 3. 5. 20:43
728x90
반응형
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]
Explanation:
- index 0 --> the greatest element to the right of index 0 is index 1 (18).
- index 1 --> the greatest element to the right of index 1 is index 4 (6).
- index 2 --> the greatest element to the right of index 2 is index 4 (6).
- index 3 --> the greatest element to the right of index 3 is index 4 (6).
- index 4 --> the greatest element to the right of index 4 is index 5 (1).
- index 5 --> there are no elements to the right of index 5, so we put -1.
Example 2:
Input: arr = [400]
Output: [-1]
Explanation: There are no elements to the right of index 0.
Constraints:
- 1 <= arr.length <= 104
- 1 <= arr[i] <= 105
MY code
Without Go routine
func replaceElements(arr []int) []int {
le := len(arr)
if le < 2 {
arr[0] = -1
return arr
}
for i := 0; i < le; i++ {
big := -1
for y := i + 1; y < le; y++ {
if big < arr[y] {
big = arr[y]
}
}
arr[i] = big
}
return arr
}
https://go.dev/play/p/LyGSC7p7oBf
With Go routine
func replaceElements(arr []int) []int {
le := len(arr)
if le < 2 {
arr[0] = -1
return arr
}
lch := make(chan []int)
go standardValue(arr, lch, le)
return <-lch
}
func standardValue(arr []int, lch chan []int, le int) {
rch := make(chan int)
for i := 0; i < le; i++ {
go bigValue(arr, rch, i, le)
arr[i] = <-rch
}
lch <- arr
}
func bigValue(arr []int, rch chan int, i, le int) {
big := -1
for y := i + 1; y < le; y++ {
if big < arr[y] {
big = arr[y]
}
}
rch <- big
}
https://go.dev/play/p/VV_koDD_13T
Sample 4ms submission
func replaceElements(arr []int) []int {
greatest := -1
for i := len(arr) - 1; i >= 0; i-- {
arr[i], greatest = greatest, max(greatest, arr[i]) // has to be the same line b4 arr[i] get updated
}
return arr
}
func max(i,j int)int{
if i > j {
return i
}
return j
}
- This code starts from right to left.
- greatest default is -1.
- So arr[end] will take -1 and arr[end] value will be the next greatest value.
- Next step is like same.
- arr[end-1] will have greatest value and max will check which number is bigger between end-1 to end.
- This max scope will be increased from end to arr[1]
sample 8 ms submission
func replaceElements(arr []int) []int {
max, current := arr[len(arr)-1], 0
arr[len(arr)-1] = -1
for i := len(arr) - 2; i >= 0; i-- {
current, arr[i] = arr[i], max
if current > max {
max = current
}
}
return arr
}
- I changed like below becuase one line code can be reduced.
Modificaion
func replaceElements(arr []int) []int {
max, current := -1, -1
for i := len(arr) - 1; i >= 0; i-- {
current, arr[i] = arr[i], max
if current > max {
max = current
}
}
return arr
}
- max(-1) will be allocated to arr[end] and arr[end] will be allocated to current.
- later if condition checks which will be bigger.
- It will starts from end of array to first array.
sample 10 ms submission
func replaceElements(arr []int) []int {
max := -1
if len(arr) == 1 {
return []int{-1}
}
for i := len(arr) - 1; i >= 0; i-- {
temp := arr[i]
arr[i] = max
if temp > max {
max = temp
}
}
return arr
}
- I think max will be better to be after if condition.
- first arr[end] will give value to temp.
- -1 will be allocated to arr[end]
- later max and temp will be checked which on is bigger.
sample 5800 KB submission
func replaceElements(arr []int) []int {
for i := 0; i < len(arr)-1; i++ {
index := i+1
for j := i+1; j < len(arr); j++ {
if arr[j] > arr[index] {
index = j
}
}
arr[i]=arr[index]
}
if len(arr) > 0 {
arr[len(arr)-1]= -1
}
return arr
}
- I don't have idea why this code is less size than mine.
- This code allocate -1 forcely to end of array
- this code looping until end-1 array.
sample 6100 KB submission
func replaceElements(arr []int) []int {
l := len(arr)
for i := 0; i < l; i++ {
if i == l - 1 {
arr[i] = -1
break
}
h := arr[i+1]
for j := i + 2; j < l; j++ {
if arr[j] > h {
h = arr[j]
}
}
arr[i] = h
}
return arr
}
- This code also end of array will have -1
- h will be like index upper code.
sample 6200 KB submission
func Max (x, y int) int {
if x > y {
return x
}
return y
}
func replaceElements(arr []int) []int {
maxRight := arr[len(arr)-1]
arr[len(arr)-1] = -1
for i := len(arr) -2 ; i >= 0; i-- {
temp := arr[i]
arr[i] = maxRight
maxRight = Max(maxRight, temp)
}
return arr
}
- This code has first end of array to maxRight and end of array will be -1.
- from this i will loop from end-1 array to 0.
sample 6300 KB submission
func replaceElements(arr []int) []int {
m, t := -1, 0
for i := len(arr) - 1; i >= 0; i-- {
t, arr[i] = arr[i], m
if m < t {
m = t
}
}
return arr
}
- This code looks like modification from first sample of fastest one.
728x90
반응형