Leetcode 315: Count of Smaller Numbers After Self

Dec. 24, 2017

Introduction

It is the hard level algorithm, and binary search tree can be selected to store the array of elements from left to right. The only trick is to increment the count whenever the new node is bigger than root node's value.

My practice

I like the hard level algorithm. So what I do is to go over the brainstorm first, and think about sorting the array, save the index; and then figure out the time complexity could not beat the brute force O(n<sup>2<sup>), and then think about store the array into binary search tree, and also keep some calculation in the same time.

I underestimated the problem, and I spent 30 minutes to write code but I could not pass the sample test case.

Here is C# code which could not pass the sample test case.

Follow up 

I asked the peer after mock interview on Dec. 24, 2017, a university of southern California university master graduate student, he analyzed using dynamic programming approach. We reached the agreement after 10 minutes, the solution may end up O(n²) at last.

Follow up 

I asked the peer after mock interview on Dec. 27, 2017 10 PM, a software engineer over 10 years experience in the city of Shanghai,he explained to me the divide and conquer algorithm similar to merge sort. I was not able to follow his explanation.