I wrote entrance intern test for one IT-company this spring. There was a problem described below. I can't solve it, so I need help (currently I'm going to pass new test, so I need to analyze my mistakes). I'll be glad for any help.
Input: An array arr of N integer numbers, N - length of arr, and number K (K < N)
Statement of the problem: Let me name s_arr(int i): it's sub-array (length K) of arr, which begins with arr[i].
In other words, s_arr(i) is {arr [i], arr [i + 1], ... arr [i + K]}
For all admissible values of offset find minimal element of s_arr(offset)
Complexity of the algorithm should be less than O (N*K)
Output: all pairs (offset, min(s_arr(offset))
Example:
Input: arr = {4, 5 ,3, 3 ,2 ,7 , 1, 5, 9}, N = 9, K = 3
Output:
(0, 3)
(1, 3)
(2, 2)
(3, 2)
(4, 1)
(5, 1)
(6, 1)
For more information about s_arr(i) (in this example):
s_arr(0) = {4, 5, 3} -> min = 3
s_arr(1) = {5, 3, 3} -> min = 3
s_arr(2) = {3, 3, 2} -> min = 2
s_arr(3) = {3, 2, 7} -> min = 2
s_arr(4) = {2, 7, 1} -> min = 1
s_arr(5) = {7, 1, 5} -> min = 1
s_arr(6) = {1, 5, 9} -> min = 1
My trivial solution:
for(int i = 0; i < N - K; i++)
int min = arr[i];
for(int j = 0; j < K; j++)
if (min > arr[i+j])
min = arr[i+j];
print("(" + i + "," + min + ")")
Obviously, the complexity is O(N*K). What should be done to reduce the complexity of this algorithm?
