Arrays101 Replace Elements with Greatest Element on Right Side in GO

Accepted Solutions Runtime Distribution

Accepted Solutions Memory Distribution

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.