2
\$\begingroup\$

(Inspired by the first problem solved in Stanford’s advanced data structures course.)

Despite the academicese-heavy name, the problem we're going to solve is almost unbearably simple.

We have a list of numbers.

[31, 41, 59, 26, 53, 58, 97]

We're going to cut some contiguous snippet out of that list of numbers.

[31, 41, 59, 26, 53, 58, 97]
    |41, 59, 26, 53|

And then we're going to find the minimum of that snippet. In this case, that's quite obviously 26. That's all.

And the obvious solution is pretty fast, too, with \$O(n)\$ time and \$O(1)\$ space in the size of the list:

minval = arbitrarily large value
for (i=first snippet index, i<last snippet index, i++)
  if (list[i]<minval) minval = list[i]

So what's with the ?

Where it gets interesting is when you try to see how efficient you can make it when you have a fixed list but a large number of range minimum queries -- snippets to find the minimum of. This version of the problem is useful, for example, if you have a huge time series you want to load only once, but you want to find the minimum of many different subintervals of that time series.

In such a scenario, it would actually be faster in practice to literally precompute all \$n^2/2\$ queries, store it in a table, and then just retrieve data from that table for an \$O(1)\$ time and \$O(n^2)\$ space solution. Dynamic programming solution from the Stanford slides ^dynamic programming solution taken from the Stanford slides

And then if you're clever enough, you realize that you only have to store each query with size that's a power of two -- you can just combine those power-of-two minima to sum to an arbitrarily sized query, and achieve the same results with constant time and linearithmic rather than quadratic space.

Interestingly, if you keep optimizing, you can get to an \$O(1)\$ time and \$O(n)\$ space solution using a sort of augmented list known as a Fischer-Heun structure. I'd love to go into the details of the structure here, but explaining how it weaves into Cartesian tree building on fixed-size snippets would make this question about 50 pages long. It's explained in the Wikipedia page, however, along with several faster-than-linear intermediate structures.

(If you can get past a research paywall, here's the original Fischer & Heun 2011 paper. And if you’d prefer the much more verbose but much more hand-holdy Stanford lecture style, here are the follow-up slides that goes into this solution, including lots of intermediates.)


The challenge

You can either write a full program or a function that calculates the result of a series of range minimum queries given a fixed list. Scoring is set up such that in general, the shortest and most-efficient-over-lots-of-queries code wins.

Input:

A list of integers xs, followed by a series of i, j pairs denoting the start and end of the snippet, inclusive (so the 26 example above uses indices i=1 and j=4). The list of integers is guaranteed to have at least one integer, and 0 <= i <= j < len(xs). This can be taken in any format that works best for your language — for example, one list for xs and one list of tuples for the i, j pairs; or maybe all the different pairs as a variable number of arguments. For a full program that takes in input from stdin, I’ll fix a format for the input:

xs[0] xs[1] xs[2] xs[3] ...
i1 j1
i2 j2
i3 j3
...

Output:

An ordered collection of the range minima for each i, j query, in the same order that they were given. In case an unordered map (such as a Python dictionary) from each i, j query to its range minimum works better for your language, that will also be allowed as an output; as long as it's obvious which minimum is related to which query.

Once again, for a full program that prints to stdout or a file, I’ll fix the format to have each range minimum on each newline (trailing newlines permitted).

Scoring:

Lower score is better; score is determined by

at(b)^2+as(b)

Where b is the byte count of your code, at is the asymptotic runtime Ө(n) of the algorithm in the size of xs interpreted as a function of n, and as is the asymptotic space usage \$\Theta(n)\$ in the size of xs interpreted as a function of \$n\$. (All constant coefficients in such \$\Theta(n)\$ expressions must be 1, and only the fastest growing term may be kept in expressions, as is standard.)

Therefore, the above pseudocode solution, which uses \$\Theta(n)\$ time and \$\Theta(1)\$ space, and is 126 characters, would have a score of (b => b**2 + 1)(126)=15876+1=15877. (Of course, the pseudocode isn't really valid since it's missing a construct to deal with multiple queries, and also because it's uncompilable pseudocode...)

Test cases:

Input:

31 41 59 26 53 58 97
1 4
0 2
5 6

Output:

26
31
58

Input:

1
0 0
0 0

Output:

1
1

Input:

-4 28 31 -54
0 0
0 1
0 2
0 3
1 1
1 2
1 3
2 2
2 3
3 3

Output:

-4
-4
-4
-4
28
28
-54
31
-54
-54
\$\endgroup\$

closed as unclear what you're asking by Sriotchilism O'Zaic, nimi, Xcali, Mr. Xcoder, mbomb007 Aug 6 at 13:28

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 1
    \$\begingroup\$ It seems that we may be as inefficient as we like building a lookup table (since from the description that does not appear to contribute to run-time complexity) and end up with just the values the (i, j) pairs inputted need and then have something which is O(1) in both time and space (since the (i, j) pairs are not n). I feel like I must have misinterpreted something! \$\endgroup\$ – Jonathan Allan Aug 5 at 16:31
  • 1
    \$\begingroup\$ I don't understand your scoring system, it seems to depend only on the bytes and size of the input array, but not on the number of queries (nq). What is the score if I call the Ө(n)-time/Ө(1)-space pseudo code nq times in a loop? \$\endgroup\$ – nimi Aug 5 at 16:33
  • \$\begingroup\$ You seem to be working with the size of elements of the list being bounded. This is implied by your "arbitrarily large value" and your "\$O(1)\$" space complexity in the first bit. Your algorithm doesn't work if the minimum is larger than the starting value and is \$O(m)\$ where \$m\$ is the size of the number. However it doesn't seem to mention this in the question. Are the values bounded and if so by what? \$\endgroup\$ – Sriotchilism O'Zaic Aug 5 at 16:58
  • 1
    \$\begingroup\$ Also although it is a common assumption that tables have constant amortized lookup, however in practice (as far as I am aware) there is no known table to actually achieve constant time lookup. Your question however seems to operate on the assumption that such a table does exist. How are we to score answers that make use of tables? \$\endgroup\$ – Sriotchilism O'Zaic Aug 5 at 17:09
  • \$\begingroup\$ @SriotchilismO'Zaic Dictionaries have constant lookup, right? So a table could just be a dictionary with tuples for the keys. \$\endgroup\$ – mbomb007 Aug 6 at 13:26
0
\$\begingroup\$

Jelly, 6 bytes, \$O(n)\$ runtime, \$O(1)\$ space, score 37

r/ịṂɗ€

Try it online!

I hope I’ve understood the scoring correctly. Naive implementation that simply indexes into the list and finds the minimum. Requires no lookup table, but limited by needing to check each input value (so \$O(n)\$ in efficiency.

\$\endgroup\$
0
\$\begingroup\$

Python 2, 42 bytes, \$O(n)\$ runtime, \$O(1)\$ space, score 1765

lambda x,L:[min(x[l[0]:l[1]+1])for l in L]
\$\endgroup\$
0
\$\begingroup\$

T-SQL 2008, 55 bytes

I apologize for being unable to figure out the scoring system.

Input is 2 tables

SELECT min(x)FROM a,b
WHERE i>f and i<t+2GROUP BY z,f,t

Try it online

\$\endgroup\$

Not the answer you're looking for? Browse other questions tagged or ask your own question.