Need help with understanding of LC time measurement
Kainobor
42

Hi, all!

Can somebody help me with understanding one question with LC and Go:
why runtime in LC sometimes is inversely proportional to go benchmark results?

For concrete example:
Problem: https://leetcode.com/problems/diagonal-traverse-ii
I made two decisions:

func findDiagonalOrder(nums [][]int) []int {
	numLines := len(nums)
	m := make(map[int][]int)
	total := 0
	for i := numLines - 1; i >= 0; i-- {
		for j := range nums[i] {
			total++
			if _, ok := m[i+j]; !ok {
				m[i+j] = []int{nums[i][j]}
				continue
			}
			m[i+j] = append(m[i+j], nums[i][j])
		}
	}

	res := make([]int, total)
	diagAmount := len(m)
	lastIdx := 0
	for i := 0; i < diagAmount; i++ {
		for j := range m[i] {
			res[lastIdx] = m[i][j]
			lastIdx++
		}
	}

	return res
}

and

func findDiagonalOrder(nums [][]int) []int {
	lineAmount := len(nums)
	if lineAmount == 0 {
		return []int{}
	}

	resLen := 0
	lineLenList := make([]int, lineAmount)
	for lineIdx, line := range nums {
		lineLenList[lineIdx] = len(line)
		resLen = resLen + lineLenList[lineIdx]
	}

	res := make([]int, resLen)
	lastAddedIdx := 0
	diagNum := 0
	for {
		diagBeginningLine := -1
		if lineAmount-1 >= diagNum {
			diagBeginningLine = diagNum
		} else {
			for i := lineAmount - 1; i >= 0; i-- {
				if lineLenList[i] > diagNum-i {
					diagBeginningLine = i
					break
				}
			}
		}
		if diagBeginningLine == -1 {
			break
		}
		for i := diagBeginningLine; i >= 0; i-- {
			if lineLenList[i] < diagNum-i+1 {
				continue
			}
			res[lastAddedIdx] = nums[i][diagNum-i]
			lastAddedIdx++
		}
		diagNum++
	}

	return res
}

In go benchmarcs I see:
First: 846 ns/op
Second: 99 ns/op
Amount of allocations is also 10 time less and it doesn't matter is input little or huge (tested on both).

But runtime in LC:
First: 196 ms
Second: 3220 ms

Why I have so big runtime in second case?

Comments (0)