Raikish
Reputation: 744
How to get the 2 max numbers of numbers array in typescript
I'm trying to find the index and value of the 2 max numbers from the next array:
{24, 64, 3, 54, 2, 80, 20}
I can't use sort method because I need to perserve the index of the items.
In this example, the result should be.
max1 = 80
max2 = 64
indexMax1 = 5
indexMax2 = 1
Any help will be appreciated.
Upvotes: 0
Views: 1125
Answers (1)
Mulan
Reputation: 135247
Here's a way we can do it using reduce and some generous destructuring assignment. Note max2 returns None if the input has less than two (2) elements –
const None =
Symbol ('None')
const max2 = ([ a = None, b = None, ...rest ]) =>
a === None || b === None
? None
: rest .reduce
( ([ m1, m2 ], val, i) =>
val > m1.val
? [ { val, i: i + 2 }, m1 ]
: val > m2.val
? [ m1, { val, i: i + 2 } ]
: [ m1, m2 ]
, b < a
? [ { val: a, i: 0 }, { val: b, i: 1 } ]
: [ { val: b, i: 1 }, { val: a, i: 0 } ]
)
console .log
( max2 ([])
// None
, max2 ([ 1 ])
// None
, max2 ([ 24, 64, 3, 54, 2, 80, 20 ])
// [ { val: 80, i: 5 }, { val: 64, i: 1 } ]
, max2 ([ 1, 1000, 100, 101, 109, 99 ])
// [ { val: 1000, i: 1 }, { val: 109: i 4 } ]
, max2 ([ 9, 9, 9, 9, 9, 2, 2, 2 ])
// [ { val: 9, i: 1 }, { val: 9, i: 0 } ]
)You asked what this would look like without using reduce. One way we can do this is by using a helper function and calling it recursively with updated arguments. We stop the recursive call when we arrive at a base case -
const None =
Symbol ('None')
const max2 = ([ a = None, b = None, ...rest ]) =>
// if a or b are non-values ...
a === None || b === None
? None // return the empty result
// when b is smaller than a
: b < a
? helper // call our helper
( { val: a, i: 0 } // m1 is the larger value (a) with index 0
, { val: b, i: 1 } // m2 is the smaller value (b) with index 1
, 2 // start the next index at 2
, rest // the remaining values of the input list
)
// otherwise, b is larger than a
: helper // call our helper
( { val: b, i: 1 } // m1 is the larger value (b) at index 1
, { val: a, i: 0 } // m2 is the smaller value (a) at index 0
, 2 // start the next index at 2
, rest // the remaining values of the input list
)
const helper = (m1, m2, i, [ val = None, ...rest ]) =>
// base case
val === None
? [ m1, m2 ]
// val is greater than m1
: val > m1.val
? helper // recur ...
( { val, i } // replace m1 with new largest value (val)
, m1 // replace m2 with previous largest value (m1)
, i + 1 // increment index
, rest // with the rest of the list
)
// val is greater than m2
: val > m2.val
? helper // recur ...
( m1 // keep the previous largest value (m1)
, { val, i } // replace m2 with new second largest value (val)
, i + 1 // increment index
, rest // with the rest of the list
)
// otherwise
: helper // recur ...
( m1 // keep the largest value (m1)
, m2 // keep the second largest value (m2)
, i + 1 // increment index
, rest // with the rest of the list
)
console .log
( max2 ([])
// None
, max2 ([ 1 ])
// None
, max2 ([ 24, 64, 3, 54, 2, 80, 20 ])
// [ { val: 80, i: 5 }, { val: 64, i: 1 } ]
, max2 ([ 1, 1000, 100, 101, 109, 99 ])
// [ { val: 1000, i: 1 }, { val: 109: i 4 } ]
, max2 ([ 9, 9, 9, 9, 9, 2, 2, 2 ])
// [ { val: 9, i: 1 }, { val: 9, i: 0 } ]
)The technique can be generalized so that defining external functions like helper is not necessary. Instead, general functions loop and recur can be defined once and then called wherever you wish to utilize this technique. No hidden magic, just functions that accept arguments and guarantee a result -
const recur = (...values) =>
({ recur, values })
const loop = f =>
{ let acc =
f ()
while (acc && acc.recur === recur)
acc = f (...acc.values)
return acc
}
const None =
Symbol ('None')
const max2 = ([ a = None, b = None, ...values ]) =>
a === None || b === None
? None
: loop // loop with arguments ...
( ( m1 = { val: a, i: 0 } // init m1 = ...
, m2 = { val: b, i: 1 } // init m2 = ...
, i = 2 // ...
, [ val = None, ...rest ] = values
) =>
// base case
val === None
? [ m1, m2 ] // <- no recur for base case
// m1 must be larger than m2
: m1.val < m2.val
? recur (m2, m1, i, [ val, ...rest ]) // <- retry with swapped m1 and m2
// val > m1
: val > m1.val
? recur ({ val, i }, m1, i + 1, rest) // <- recur
// val > m2
: val > m2.val
? recur (m1, { val, i }, i + 1, rest) // <- recur
// otherwise
: recur (m1, m2, i + 1, rest) // <- recur
)
console .log
( max2 ([])
// None
, max2 ([ 1 ])
// None
, max2 ([ 24, 64, 3, 54, 2, 80, 20 ])
// [ { val: 80, i: 5 }, { val: 64, i: 1 } ]
, max2 ([ 1, 1000, 100, 101, 109, 99 ])
// [ { val: 1000, i: 1 }, { val: 109: i 4 } ]
, max2 ([ 9, 9, 9, 9, 9, 2, 2, 2 ])
// [ { val: 9, i: 1 }, { val: 9, i: 0 } ]
)Above we find the two (2) max values, but we can expand our program to find the max N values -
console .log
( maxn (3, [])
// None (less than 3 input values)
, maxn (3, [ 1 ])
// None (less than 3 input values)
, maxn (3, [ 24, 64, 3, 54, 2, 80, 20 ])
// [ { val: 80, i: 5 }, { val: 64, i: 1 }, { val: 54, i: 3 } ]
, maxn (3, [ 1, 1000, 100, 101, 109, 99 ])
// [ { val: 1000, i: 1 }, { val: 109, i: 4 }, { val: 101, i: 3 } ]
, maxn (3, [ 9, 9, 9, 9, 9, 2, 2, 2 ])
// [ { val: 9, i: 1 }, { val: 9, i: 2 }, { val: 9, i: 3 } ]
)
Here's a possible implementation of maxn using reduce and a helper function insert -
const maxn = (n = 1, values = []) =>
n >= values.length
? None
: values .reduce
( (acc, val, i) =>
insert ({ val, i }, acc)
, []
)
.slice (0, n)
const insert = (a, [ b = None, ...rest ]) =>
b == None
? [ a ]
: a.val > b.val
? [ a, b, ...rest ]
: [ b, ...insert (a, rest) ]
And again, but this time using our no-magic loop and recur -
const maxn = (n = 1, values = []) =>
n >= values.length
? None
: loop
( ( acc = []
, i = 0
) =>
i >= values.length
? n > acc.length
? None
: acc .slice (0, n)
: recur
( insert
({ val: values[i], i }
, acc
)
, i + 1
)
)
const insert = (a, values = []) =>
loop
( ( acc = []
, [ b = None, ...rest ] = values
) =>
b === None
? [ ...acc, a ]
: a.val > b.val
? [ ...acc, b, ...rest ]
: recur
( [ ...acc, b ]
, rest
)
)
Expand the snippet below to read additional source comments and verify the results in your own browser -
const recur = (...values) =>
({ recur, values })
const loop = f =>
{ let acc =
f ()
while (acc && acc.recur === recur)
acc = f (...acc.values)
return acc
}
const None =
Symbol ('None')
const maxn = (n = 1, [ val = None, ...values ]) =>
val === None
? None
: loop // init loop
( ( acc = [] // init accumulator as empty list
, i = 0 // start at index 0
) =>
// base case
i >= values.length // when i is out of bounds ...
? n > acc.length // when accumulator has fewer than n values...
? None // return None result
: acc // otherwise return the accumulator
// inductive
: recur
( insert // insert new value into accumlator
({ val: values[i], i: i + 1 }
, acc
)
.slice (0, n) // only keep at most n values
, i + 1 // increment index
)
)
const insert = (a, [ b = None, ...rest ]) =>
// base case
b == None
? [ a ]
// a is larger than b
: a.val > b.val
? [ a, b, ...rest ]
// otherwise
: [ b, ...insert (a, rest) ]
console .log
( maxn (3, [])
// None (less than 3 input values)
, maxn (3, [ 1 ])
// None (less than 3 input values)
, maxn (3, [ 24, 64, 3, 54, 2, 80, 20 ])
// [ { val: 80, i: 5 }, { val: 64, i: 1 }, { val: 54, i: 3 } ]
, maxn (3, [ 1, 1000, 100, 101, 109, 99 ])
// [ { val: 1000, i: 1 }, { val: 109, i: 4 }, { val: 101, i: 3 } ]
, maxn (3, [ 9, 9, 9, 9, 9, 2, 2, 2 ])
// [ { val: 9, i: 1 }, { val: 9, i: 2 }, { val: 9, i: 3 } ]
)Upvotes: 2
Related Questions
- Find the second largest number in array
- How to get the maximum value from an array of array of tuples in TypeScript?
- Type script get max array
- TypeScript - Get max value from a mixed array
- Return the two highest numbers in an array javascript
- how to return the two largest number from each array of an array in JavaScript without using for loops?
- Getting Largest Number From Array
- Return Largest Numbers in an array
- How to find the biggest number in array
- return largest number in arrays