Finding the objects with the cheapest seats

Question

i have the following json object

 const file = [
 {
 "seatNumber": "1A",
 "price": "19ドル.99",
 "available": true,
 "disabilityAccessible": true
 },
 {
 "seatNumber": "2A",
 "price": "19ドル.99",
 "available": false,
 "disabilityAccessible": false
 },
 {
 "seatNumber": "3A",
 "price": "19ドル.99",
 "available": false,
 "disabilityAccessible": false
 },
 {
 "seatNumber": "4A",
 "price": "19ドル.99",
 "available": true,
 "disabilityAccessible": false
 },
 {
 "seatNumber": "5A",
 "price": "19ドル.99",
 "available": false,
 "disabilityAccessible": false
 },
 {
 "seatNumber": "1B",
 "price": "12ドル.99",
 "available": true,
 "disabilityAccessible": true
 },
 {
 "seatNumber": "2B",
 "price": "12ドル.99",
 "available": false,
 "disabilityAccessible": false
 },
 {
 "seatNumber": "3B",
 "price": "12ドル.99",
 "available": false,
 "disabilityAccessible": false
 },
 {
 "seatNumber": "4B",
 "price": "12ドル.99",
 "available": false,
 "disabilityAccessible": false
 },
 {
 "seatNumber": "5B",
 "price": "12ドル.99",
 "available": true,
 "disabilityAccessible": false
 },
 {
 "seatNumber": "1C",
 "price": "12ドル.99",
 "available": true,
 "disabilityAccessible": true
 },
 {
 "seatNumber": "2C",
 "price": "12ドル.99",
 "available": true,
 "disabilityAccessible": false
 },
 {
 "seatNumber": "3C",
 "price": "12ドル.99",
 "available": true,
 "disabilityAccessible": false
 },
 {
 "seatNumber": "4C",
 "price": "12ドル.99",
 "available": true,
 "disabilityAccessible": false
 },
 {
 "seatNumber": "5C",
 "price": "12ドル.99",
 "available": true,
 "disabilityAccessible": false
 },
 {
 "seatNumber": "1D",
 "price": "12ドル.99",
 "available": true,
 "disabilityAccessible": true
 },
 {
 "seatNumber": "2D",
 "price": "12ドル.99",
 "available": false,
 "disabilityAccessible": false
 },
 {
 "seatNumber": "3D",
 "price": "12ドル.99",
 "available": true,
 "disabilityAccessible": false
 },
 {
 "seatNumber": "4D",
 "price": "12ドル.99",
 "available": true,
 "disabilityAccessible": false
 },
 {
 "seatNumber": "5D",
 "price": "12ドル.99",
 "available": true,
 "disabilityAccessible": false
 },
 {
 "seatNumber": "1E",
 "price": "8ドル.99",
 "available": true,
 "disabilityAccessible": true
 },
 {
 "seatNumber": "2E",
 "price": "8ドル.99",
 "available": true,
 "disabilityAccessible": false
 },
 {
 "seatNumber": "3E",
 "price": "8ドル.99",
 "available": false,
 "disabilityAccessible": false
 },
 {
 "seatNumber": "4E",
 "price": "8ドル.99",
 "available": true,
 "disabilityAccessible": false
 },
 {
 "seatNumber": "5E",
 "price": "8ドル.99",
 "available": false,
 "disabilityAccessible": false
 }
]

I am trying to display seatNumber of the cheapest objects. so far i have the following which works but would like to know if there is a better way following big o notation in es6 format

const seats = file.filter( seat => seat.price.replace(/[^0-9.-]+/g,"") == Math.min(...file.map(function ( seat ) { return Number(seat.price.replace(/[^0-9.-]+/g,"")) }) ) ).map(seat => seat.seatNumber);
 console.log(seats)

output is

[ '1E', '2E', '3E', '4E', '5E' ]

Answer 1

Following the little big O.

You ask

"...if there is a better way following big o notation..." (?)

Big O notation is a formalized mathematical convention used to express how a function (mathematical function) behaves as it approaches infinity.

It is used in computer science to classify an algorithms complexity in regard to a definable input metric, usually the size of the input array when dealing with arrays.

You can not "follow" big O notation as it provides no insight into how to reduce an algorithms complexity apart from a comparison.

Find the big O

To classify your function using Big O, first we need to make it at least readable, and convert it to a function. See snippet.

Now count the number of times the function loops over each item in the input array data. Experience lets you do this in your head, but to demonstrate we modify the function to count every time you handle an item in the input array.

Because we need to fit a curve we need at least 3 different input sizes which I do with some random data.

function bestSeats(data) {
 var c = 0; // the counter
 const seats = data.filter( seat => 
 (c++, // count the filter iterations
 seat.price.replace(/[^0-9.-]+/g, "") == Math.min(
 ...data.map(function ( seat ) { 
 c += 2; // this counts as two
 // once each to map to the arguments of Math.min
 // once each to find the min 
 return Number(seat.price.replace(/[^0-9.-]+/g, "")) 
 }
 )
 ))).map(seat => (
 c++, // count each result
 seat.seat
 )); 
 return "O(n) = O(" + data.length + ") = " + c;
}
function randomData(size) { 
 const data = [];
 while (size--) { data.push({seat:size, price: "$"+(Math.random() * 100 | 0)})}
 return data;
}
console.log("Eval complexity A:" + bestSeats(randomData(10)));
console.log("Eval complexity B:" + bestSeats(randomData(100)));
console.log("Eval complexity C:" + bestSeats(randomData(500)));

The 3 points we can use to find the curve that best fits

 O(10) ~= 211
 O(100) ~= 20,102
 O(500) ~= 500,005

Experience tells me it's a polynomial of some (not too high) order. Using a graphing calculator I found a reasonable fits at 2.15 making your functions big O complexity

\$O(n^{2.15})\$

Which is insanely inefficient. OMDG!!!!

So keeping

"...in es6 format" (?)

in mind a cleaner more readable, less CO2 producing sea level rising approach is to do a two pass scan of the seats. The first pass finds the min price, the second extracts the min price seat numbers.

This example uses for of loops rather than the Array methods like filter and map, because these array methods have a nasty way of blinding people to the insane level of complexity of what they do, and for of is a little quicker and often allows better optimizations than the array methods, so it's win win for for of

Examples in \$O(n)\$ linear time.

 function bestSeats(seats) {
 var min = Infinity, minVal;
 const result = [];
 for (const seat of seats) {
 const price = Number(seat.price.slice(1));
 if (price < min) {
 min = price;
 minVal = seat.price;
 }
 }
 for (const seat of seats) {
 if (seat.price === minVal) { result.push(seat.seatNumber) }
 }
 return result;
 }

And if you must use the array methods.

 function bestSeats(seats) {
 const price2Num = seat => Number(seat.price.slice(1));
 const min = (min, seat) => price2Num(seat) < min ? price2Num(seat) : min;
 const minPrice = "$" + seats.reduce(min, Infinity);
 return seats.filter(seat => seat.price === minPrice).map(seat => seat.seatNumber);
 }

• dfhwze: Wouldn't it be possible to cache the seats with min value as we go in the first loop making it O(n)? Now it looks O(2*n) to me.
• Blindman67: @dfhwze O(2n) is the same as O(n), both are linear and the scalar 2 is never included in Big O notation as it becomes insignificant as we approach infinity.Yes a single pass O(n) solution can use a Map to hold each price category filing in the cats as you check each value, returning the min cat. Personally that should be part of the data query (pre processed index by price) and then searching only prices categories could make it O(n^c) 0<c<1 (being less complex than O(n)) if price category count had that relationship to seat count. Could even be O(1) if the price categories count is fixed
• dfhwze: Thanks for this thorough clarification.
• shorif2000: should i use the above answer? @Blindman67 confused me
• Blindman67: @shorif2000 You are under no obligation to accept an answer, you are free to undo accepted answers if you feel the answer has not helped you. A question without an accepted answer is much more likely to get another answer, an answer that may better address your needs, which is after-all what this site is for. :)