Array 101 Height Checker

Accepted Solutions Runtime Distribution

Accepted Solutions Memory Distribution

A school is trying to take an annual photo of all the students. The students are asked to stand in a single file line in non-decreasing order by height. Let this ordering be represented by the integer array expected where expected[i] is the expected height of the ith student in line.

You are given an integer array heights representing the current order that the students are standing in. Each heights[i] is the height of the ith student in line (0-indexed).

Return the number of indices where heights[i] != expected[i].

Example 1:

Input: heights = [1,1,4,2,1,3]
Output: 3
Explanation: 
heights:  [1,1,4,2,1,3]
expected: [1,1,1,2,3,4]
Indices 2, 4, and 5 do not match.

Example 2:

Input: heights = [5,1,2,3,4]
Output: 5
Explanation:
heights:  [5,1,2,3,4]
expected: [1,2,3,4,5]
All indices do not match.

Example 3:

Input: heights = [1,2,3,4,5]
Output: 0
Explanation:
heights:  [1,2,3,4,5]
expected: [1,2,3,4,5]
All indices match.

Constraints:

• 1 <= heights.length <= 100
• 1 <= heights[i] <= 100

My code

func heightChecker(heights []int) int {
    if len(heights) <= 1 {
        return 0
    }

    temp := make([]int, len(heights))
    copy(temp, heights)
    // for _, v := range heights {
    //     temp = append(temp, v)
    // }

    quickSort(temp, 0, len(temp)-1)
    count := 0
    for i := range temp {
        if temp[i] != heights[i] {
            count++
        }
    }
    return count
}

func quickSort(arr []int, l, r int) {
    if l < r {
        p := partition(arr, l, r)
        quickSort(arr, l, p-1)
        quickSort(arr, p+1, r)
    }
}

func partition(arr []int, l, r int) int {
    pivot := arr[r] // pivot
    i := (l - 1)

    for j := l; j <= r-1; j++ {

        if arr[j] <= pivot {
            i++
            arr[i], arr[j] = arr[j], arr[i]
        }
    }
    arr[i+1], arr[r] = arr[r], arr[i+1]
    return i + 1
}

https://go.dev/play/p/6b3F0PVS6Jd

• I implemented it by using Quick sort.
• When i used temp := heights, temp just took address from it.
• So I used copy.
• Also we can use append.
• I don't have a idea how to reduce size.
• Random pivot will work maybe...?

sample 0 ms submission

func heightChecker(heights []int) int {
    s := make([]int, len(heights))
    i,count := 0,0

    copy(s, heights)
    sort.Ints(s)

    for i < len(s) {
        if s[i] != heights[i] {
            count++
        }
        i++
    }

    return count
}

• So simple code.
• This uses sort function
• I didn't use because when I get interview, they will ask what soring method is good.

sample 2 ms submission & sample 2100 KB submission

func heightChecker(heights []int) int {
    var heightFreq [101]int
    for _,i := range heights {
        heightFreq[i]++
    }
    result := 0
    currentHeight := 0

    for i:=0; i < len(heights); i++ {
        for heightFreq[currentHeight] == 0 {
            currentHeight++
        }

        if currentHeight != heights[i] {
            result++
        }
        heightFreq[currentHeight]--
    }
    return result
}

• I guess more than slice, fixed array uses less size?
• Array must have fixed constant.What we can deduce from these benchmark would be a slice with declared length would almost always perform better. Whereby over allocating or under allocating the capacity would certainly impact the performance of the system you are building.
  https://dev.to/jonathanlawhh/golang-slice-vs-array-and-should-i-declare-my-slice-size-4kng
• This code allocate value in 101 array. I think 100 would be better.
• First for loop has frequency which how many numbers array has.
• Second for loop will check currentHeight based on array index.
• if currentHeight is 0, but heightFreq has 0 value, then currentHeight will increase.
• If not, if condition checks height has numbers in order.
• When they are not match, result will increase.
• End of for loop, heightFreq will decrease.
• I think very effective code.

Pratice

func heightChecker(heights []int) int {
    heightfreq := make([]int, 101)
    for _, v := range heights {
        heightfreq[v]++
    }

    check := 0
    result := 0

    for _, v := range heights {
        for heightfreq[check] == 0 {
            check++
        }

        if check != v {
            result++
        }
        heightfreq[check]--

    }

    return result
}

sample 3 ms submission

func heightChecker(heights []int) int {
    var heights_sort = make([]int, len(heights))
    copy(heights_sort, heights)
    var result int = 0
    sort.Ints(heights_sort)
    for i, _ := range heights {
        if heights_sort[i] != heights[i] {
            result++
        }
    }
    return result;
}

sample 2200 KB submission

func heightChecker(heights []int) int {
    freq := make([]int, 101)
    for _, val := range heights {
        freq[val]++
    }
    cur := 1
    res := 0
    for _, h := range heights {
        for freq[cur] == 0 {
            cur++
        }
        if cur != h {
            res++
        }
        freq[cur]--
    }
    return res
}

sample 2300 KB submission

func heightChecker(heights []int) int {
    s := make([]int, len(heights))
    i,count := 0,0

    copy(s, heights)
    sort.Ints(s)

    for i < len(s) {
        if s[i] != heights[i] {
            count++
        }
        i++
    }

    return count
}