CODEWITHSUNDEEP
algorithmarray-algorithms
Noowada
Noowada

Reputation: 53

Need to find lowest differences between first line of an array and the rest ones

Well, I've been given a number of pairs of elements (s,h), where s sends an h element on the s-th row of a 2d array.It is not necessary that each line has the same amount of elements, only known that there cannot be more than N elements on a line.

What I want to do is to find the lowest biggest difference(!) between a certain element of the first line and the rest ones.

Thus, if I have 3 lines with (101,92) (100,25,95,52,101) (93,108,0,65,200) what I want to find is 3, because I have to choose 92 and I have 95-92=3 from first to second and 93-92=1 form first to third.

I have reached a point where it is certain that if I have s lines with n(i) elements each and i=0..s, then n0<=n1<=...<=ns so as to have a good average performance scenario when picking the best-fit from 1st line towards the others.

However, I cannot think of a way lower than O(n2) or even maybe O(n3) in some cases. Does anyone have a suggestion about a fairly improved way to do this?

Upvotes: 0

Views: 78

Answers (1)

Bernhard Barker
Bernhard Barker

Reputation: 55589

Combine all lines into a single list, also keeping track of which element comes from where.

Sort this list.

Have a last-value variable for each line.

For each item in the sorted list, update the last-value variable of the applicable list. If not all lines have a last-value set yet, do nothing. If it's an element from the first list:

  • Recalculate the biggest difference for all of the last-value variables. Store this difference.

If it's an element from any other list:

  • If all values have previous not been set, calculate the biggest difference. Otherwise, if the difference between the first list's last-value and this element is bigger than the biggest difference, update the biggest difference with this difference. Store this difference.

The smallest difference is the desired value.

Example:

Lists: (101,92) (100,25,95,52,101) (93,108,0,65,200)

Sorted  0  25 52 65 92 93 95 100 101 101 108 200
Source  2  1  1  2  0  2  1  1   0   1   2   2

Last[0] -  -  -  -  92 92 92 92  101 101 101 101
Last[1] -  25 52 52 52 52 95 100 100 101 101 101
Last[2] 0  0  0  65 65 93 93 93  93  93  108 200

Diff    -  -  -  -  40 41 3  8   8   8   7   9
Best    -  -  -  -  40 40 3  3   3   3   3   3

Best = 3 as required. Storing the actual items or finding them afterwards should be easy enough.

Complexity:

Let n be the total number of items and k be the number of lists.

O(n log n) for the combine + sort.

O(nk) (worst case) for the scan through, since we're checking n items and, at each item, we do maximum O(k) work.

So O(n log n + nk).

Upvotes: 1

Related Questions