0

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?

lantalex
  • 33
  • 5
  • Look at http://stackoverflow.com/questions/12190184/can-min-max-of-moving-window-achieve-in-on/12195098#12195098 – MBo Sep 22 '14 at 15:28

2 Answers2

1

You can use a well-known sliding window minumum algorithm to achieve O(N) complexity.
Here is an article about it: http://people.cs.uct.ac.za/~ksmith/articles/sliding_window_minimum.html

kraskevich
  • 18,368
  • 4
  • 33
  • 45
-1

You should use the information you already have in your previous array. If the first element of the previous array (i-1) is not the smaller, you could simply compare the minimal you found last iteration with the last element of your current array (i+k-1).

Hope that helps.

Fernando Aires
  • 532
  • 2
  • 7
  • It does not improve the worst case time complexity(for example, it does not help if the initial array is sorted). – kraskevich Sep 22 '14 at 14:46