sliding window in the array

Dec. 26, 2017

Introduction

It is the mock interview of 12:00 PM. I have to practice a solution for k-messed array sort. Since C# does not provide minimum heap class, the peer told me that I can apply sorting similar to insertion sort.

After we discussion to use linear scan k + 1 window to find the index with the minimum value, and then swap the start position with minimum index, I wrote the following code.

C# code is here.

My argument is to write the code and also the code can pass all mock interview platform test cases. Although the time complexity is O(kn), k is the size of slide window, n is the array's length. The optimal one using minimum heap is better with time complexity O(nlogk).