Finding max/min in a data string

Question

I have a string of data that is a string of x,y pairs like this:

[
    [0.519999980926514, 0.0900000035762787],
    [0.529999971389771, 0.689999997615814],
    [0.519999980926514, 2.25],
    [0.850000023841858, 2.96000003814697],
    [1.70000004768372, 3.13000011444092],
    [1.91999995708466, 3.33999991416931],
    [0.839999973773956, 3.5],
    [1.57000005245209, 3.38000011444092],
    [0.819999992847443, 3.00999999046326],
    [1.69000005722046, 2.99000000953674],
    [2.98000001907349, 3.23000001907349],
    [0.509999990463257, 1.11000001430511],
    [0.670000016689301, 1.35000002384186],
    [0.660000026226044, 1.26999998092651],
    [0.689999997615814, 0.0500000007450581],
    [1.30999994277954, 0.0599999986588955],
    [0.569999992847443, 0.0299999993294477],
    [0.629999995231628, 0.0399999991059303],
    [0.720000028610229, 0.0399999991059303],
    [0.639999985694885, 0.0399999991059303],
    [0.540000021457672, 0.0399999991059303],
    [0.550000011920929, 0.0500000007450581],
    [0.850000023841858, 0.0399999991059303],
    [0.610000014305115, 0.0199999995529652],
    [0.509999990463257, 0.0500000007450581],
    [0.610000014305115, 0.0599999986588955],
    [0.5, 0.0599999986588955],
    [0.639999985694885, 0.0599999986588955]
]

What I want to do is find the max and min in each pair.

Is there any way of doing this without going through the entire string and examining each element in the pair?

Have you tried anything at all? Can you show us some code? And this might be a duplicate of http://stackoverflow.com/questions/1379553/how-might-i-find-the-largest-number-contained-in-a-javascript-array — Jay Blanchard, Feb 25 '14 at 22:46
What do you mean by min max in each pair? can you print the sample output. And for your question, I think you can start with small set for the question. — Mutant, Feb 25 '14 at 22:46
No, there's no way to do this without going trough each string and comparing them individually, unless you are obtaining this info trough another function, in which you could compare before saving in the array. — LasagnaAndroid, Feb 25 '14 at 22:48
Please post your [**current code**](http://whathaveyoutried.com) you are having issues so we can see what you might be doing wrong. In addition if you can create a [**jsfiddle**](http://jsFiddle.net) demonstrating the issue that would help too. — Nope, Feb 25 '14 at 22:48
Of course there is a way without iteration. There is a function `findAMaxMinForMyUniqueStructure` in a `Magic.WithoutIteration` namespace available. — zerkms, Feb 25 '14 at 22:49
Does this work on data array pairs? The first one in the pair is the x value and the second is the y. I want to find a max and min for the x and the y values independent of each other. I haven't written any code yet. Was trying to get some ideas before I tried and failed a million times first. — Crimpy, Feb 25 '14 at 22:59
@Crimpy: "Was trying to get some ideas before I tried and failed a million times first." --- it's a task for primary school student. How to fail in this trivial task? — zerkms, Feb 25 '14 at 22:59
it's not trival because I can't get it to work with either suggested method... I'm not a programmer and I am just learning how to do things. All I wanted was a direction to go and then try to work it out. Thanks for the help and the negative reputation. — Crimpy, Feb 25 '14 at 23:21

J David Smith · Accepted Answer · 2014-02-25T23:57:55.973

There is no way to outperform O(n) operations (where n is the number of pairs) on this problem.

In some cases, it is possible to find the maximum in less time, however all algorithms require at least 1 comparison (which is the number of comparisons needed to determine the maximum of a pair).

To do what you want, you ought to turn to JavaScript's wonderful map and apply functions:

function maxOfSubArrays(input) {
    // assumes `input` is an array of n-element arrays
    return input.map(function(el) { return Math.max.apply(Math, el); });
}

map returns a new array with each element set to the return value of the function applied to an element in the original array (ie mapped[i] = f(input[i])). apply calls a function , unpacking the provided array as the arguments (so Math.max.apply(Math, [1, 2]) is the same as Math.max(1, 2)).

To find the minimum rather than the maximum, use Math.min. To get both, it is easiest to simply return [Math.min..., Math.max...].

EDIT: If I understand your comment correctly, you want to treat it like an nx2 matrix, where n is the number of pairs (also: number of rows). Then, you want to find the maximum of each column. This is relatively easy to do with apply and map:

function maxOfColumns(input) {
    return [Math.max.apply(Math, input.map(function(el) { return el[0]; })),
            Math.max.apply(Math, input.map(function(el) { return el[1] }))];
}

An attentive reader will note that this creates a copy of the entire data set. For large data sets, this can be a problem. In such a case, using map to construct the columns would not be ideal. However, for most use cases there will not be a significant performance difference.

Here is a JSFiddle that demonstrates both variants: http://jsfiddle.net/utX53/ Look in the JS Console to see the results (Ctrl-Shift-J on Chrome in Win/Lin)

There does not seem to be any particular structure that could be used to speed up the process, which means that O(n) is still the fastest this can be done.

A final word: maxOfColumns can be trivially extended to handle an arbitrary number of columns. I leave it to the reader to figure out how (mostly because it is much less readable than the above).

I appreciate your help and not being condescending in your answer. I had to look up just how to write the variable in JSFiddle. Here's what I'm trying: http://jsfiddle.net/HKhw8/99/ I call the function, but it's empty. I'm not sure if this is going to return the max of the first element in the pair. I am looking for the first element max and the second element max. — Crimpy, Feb 25 '14 at 23:41
You mean that you want to treat it like two columns of a matrix, then find the max of each column? In that case, I'd again use `map` and `apply`, but in a slightly different order: `[Math.max.apply(Math, input.map(function(el) { return el[0]; })), Math.max.apply(/* same thing, but with el[1] */)]` — J David Smith, Feb 25 '14 at 23:50
Thank you very much. I broke it out into two functions to get the X and Y as individual results. I would have never gotten to this point without your help. Much appreciated. — Crimpy, Feb 26 '14 at 00:10

Finding max/min in a data string

1 Answers1