StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>So here is an algorithm to do solve this problem in two steps:</p> <p>First step is to merge all your arrays into one sorted array which would look like this:</p> <p>combined_val[] - which holds all numbers <br> combined_ind[] - which holds index of which array did this number originally belonged to</p> <p>this step can be done easily in O(K*N*log(N)) but i think you can do better than that too (maybe not, you can lookup variants of merge sort because they do step similar to that)</p> <p>Now second step:</p> <p>it is easier to just put code instead of explaining so here is the pseduocode:</p> <pre><code> int count[N] = { 0 } int head = 0; int diffcnt = 0; // mindiff is initialized to overall maximum value - overall minimum value int mindiff = combined_val[N * K - 1] - combined_val[0]; for (int i = 0; i &lt N * K; i++) { count[combined_ind[i]]++; if (count[combined_ind[i]] == 1) { // diffcnt counts how many arrays have at least one element between // indexes of "head" and "i". Once diffcnt reaches N it will stay N and // not increase anymore diffcnt++; } else { while (count[combined_ind[head]] > 1) { // We try to move head index as forward as possible while keeping diffcnt constant. // i.e. if count[combined_ind[head]] is 1, then if we would move head forward // diffcnt would decrease, that is something we dont want to do. count[combined_ind[head]]--; head++; } } if (diffcnt == N) { // i.e. we got at least one element from all arrays if (combined_val[i] - combined_val[head] &lt mindiff) { mindiff = combined_val[i] - combined_val[head]; // if you want to save actual numbers too, you can save this (i.e. i and head // and then extract data from that) } } } </code></pre> <p>the result is in mindiff.</p> <p>The runing time of second step is O(N * K). This is because "head" index will move only N*K times maximum. so the inner loop does not make this quadratic, it is still linear.</p> <p>So total algorithm running time is O(N * K * log(N)), however this is because of merging step, if you can come up with better merging step you can probably bring it down to O(N * K).</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload