Find the smallest missing number

January 16, 2018

Introduction

It is another 10:00 PM mock interview. I started to work on my analysis of algorithm, I tried to put together the algorithm requirement, constraints, and my solution, time complexity, space complexity, and also go over the small case to explain the algorithm. This time the analysis of the algorithm is not up to standard I like.

Analysis of the algorithm review

Instead of doing code review, I like to review my analysis of the algorithm. I like to make it better. Clarify the question, understand the constraints, and also the problem to work on.

	/*
	assumption: unique, nonnegative, integer array
	getDifferentNumber = find smallest, nonnegative >=0, integer, not in the array
	not allowed to modify the input array
	time complexity
	- O(n)
	space complexity
	- extra space - O(n)
	[0, 1, 2, 3]
	4
	extraFound
	[1, 1, 1, 1] -> from 0 - length - 1, length
	[1, 0, 100, 200]
	[1,1,0,0] -> 100 > 4 , length + 1
	Changet the array -> O(nlogn) sort the array, it is optimal
	if the number is found and the number is less than length, then
	mark the element's value to -1 * Math.Abs(arr[i]) for arr[i] > 0, if arr[i] == 0,
	and if i != 0, then set arr[0] as a negative number, and then arr[i] = -(length + 2).
	[2, -1, -3, -4] - O(n)
	[0, 1, 2, 3]
	*/

view raw GetFirstMissingNumber.cs hosted with ❤ by GitHub

I also like to find a few issues in the above writing:
I should write a summary to describe the idea to solve the problem, using the extra array to store 1 if index value is found in the original array.

Here is the code with the analysis.