20
\$\begingroup\$

Given a list of integers, your task is to output the second largest value in the first k elements, for each k between 2 and the length of the input list.

In other words, output the second largest value for each prefix of the input.

You can output an arbitrary value for the first element (where k = 1), or simply omit this value, as there isn't a second maximum for a list of 1 element. You may assume there are at least 2 elements in the input.

Shortest code wins.

Examples

Input:
1 5 2 3 5 9 5 8
Output:
  1 2 3 5 5 5 8
Input:
1 1 2 2 3 3 4
Output:
  1 1 2 2 3 3
Input:
2 1 0 -1 0 1 2
Output:
  1 1 1 1 1 2
\$\endgroup\$
  • \$\begingroup\$ My English isn't the best, how is k determined? \$\endgroup\$ – LiefdeWen Aug 11 '17 at 12:17
  • \$\begingroup\$ @LiefdeWen Output a list containing the answer for each k. \$\endgroup\$ – jimmy23013 Aug 11 '17 at 12:24
  • 2
    \$\begingroup\$ 1 is not, strictly speaking, the second largest value of 1,1 (2nd example) it's the second value when sorted descending. \$\endgroup\$ – Jonathan Allan Aug 11 '17 at 12:49
  • \$\begingroup\$ Maybe I'm just stupid (although I suspect I could really have the weekend started..), but I'm still not sure how this works. Could someone ELI5 the last test case to me? The first two test cases I can solve by just looping over the list, determining the current minimum of the list, and then remove that item (or easier: sort list and remove last item). It gives the correct results for the first two test cases, but is obviously wrong (and will give -1, 0, 0, 1, 1, 2 for the last test case.) \$\endgroup\$ – Kevin Cruijssen Aug 11 '17 at 14:32
  • 1
    \$\begingroup\$ @KevinCruijssen Remember the two largest numbers you have seen. In the last case, you start with 2 being the largest, and output nothing/whatever since it doesn't make sense at this point. Then you change to 1 and 2 at the next iteration, so you output 1. This stays the same until you reach the 2 at the end, and then you have 2 and 2 as the largest and second largest \$\endgroup\$ – FryAmTheEggman Aug 11 '17 at 14:36

29 Answers 29

6
\$\begingroup\$

05AB1E, 5 bytes

ηεà\à

Try it online!

Returns [] (arbitrary value) for first.

\$\endgroup\$
  • \$\begingroup\$ η¦ε{¨θ should work for 6 bytes \$\endgroup\$ – Adnan Aug 11 '17 at 12:33
  • \$\begingroup\$ @Adnan Of course >_< found a better way anyways though... \$\endgroup\$ – Erik the Outgolfer Aug 11 '17 at 12:33
  • \$\begingroup\$ Interesting... Z©KZ®‚¹sà was what I was thinkinh, didn't know à was even a thing! \$\endgroup\$ – Magic Octopus Urn Aug 11 '17 at 13:54
  • \$\begingroup\$ Found another 5-byte alternative. I used Áθ instead. \$\endgroup\$ – Mr. Xcoder Aug 11 '17 at 14:02
5
\$\begingroup\$

Husk, 9 7 bytes

Saved a byte or two thanks to @Zgarb

mȯ→hOtḣ

Returns 0 for the first "second maximum"

Explaination

         -- implicit input, e.g          [1,5,3,6]
      ḣ  -- prefixes                     [[],[1],[1,5],[1,5,3],[1,5,3,6]]
     t   -- remove the first element     [[1],[1,5],[1,5,3],[1,5,3,6]]
mȯ       -- map the composition of 3 functions
    O    --   sort                       [[1],[1,5],[1,3,5],[1,3,5,6]]
   h     --   drop the last element      [[],[1],[1,3],[1,3,5]
  →      --   return the last element    [0,1,3,5]
         -- implicit output

Try it online!

\$\endgroup\$
  • 1
    \$\begingroup\$ You could map →hO instead and save a byte. \$\endgroup\$ – Zgarb Aug 11 '17 at 13:16
4
\$\begingroup\$

Python 2, 54 bytes

lambda x:[sorted(x[:i])[-2]for i in range(2,1+len(x))]

Try it online!

\$\endgroup\$
3
\$\begingroup\$

JavaScript (ES6), 58 51 50 bytes

Saved 1 byte thanks to @Neil

Appends undefined for k = 1.

a=>a.map(e=>(b=[e,...b]).sort((a,b)=>b-a)[1],b=[])

Test cases

NB: This snippet uses JSON.stringify() for readability, which -- as a side effect -- converts undefined to null.

let f =

a=>a.map(e=>(b=[e,...b]).sort((a,b)=>b-a)[1],b=[])

console.log(JSON.stringify(f([1, 5, 2, 3, 5, 9, 5, 8]))) // 1 2 3 5 5 5 8
console.log(JSON.stringify(f([1, 1, 2, 2, 3, 3, 4])))    // 1 1 2 2 3 3
console.log(JSON.stringify(f([2, 1, 0, -1, 0, 1, 2])))   // 1 1 1 1 1 2

\$\endgroup\$
  • 1
    \$\begingroup\$ I think a=>a.map(e=>(b=[e,...b]).sort((a,b)=>b-a)[1],b=[]) is only 50. \$\endgroup\$ – Neil Aug 11 '17 at 12:57
  • \$\begingroup\$ @Neil Nice. :-) \$\endgroup\$ – Arnauld Aug 11 '17 at 13:14
2
\$\begingroup\$

Pyth, 8 bytes

m@Sd_2._

Try it online! or Try the Test Suite!


How?

This outputs the first element of the list as the first value in the list, as per the spec You can output an arbitrary value for the first element.

m@Sd_2._   - Full program with implicit input.

m     ._Q  - Map over the prefixes of the input with a variable d.
  Sd       - Sorts the current prefix.
 @         - Gets the element...
    _2       - At index - 2 (the second highest).
           - Print implicitly.
\$\endgroup\$
2
\$\begingroup\$

Jelly, 8 bytes

ḣJṢ€Ṗ€Ṫ€

Try it online!

The first value will be 0, always, and the following numbers will be the second maximums of each prefix.

Explanation

ḣJṢ€Ṗ€Ṫ€  Input: array A
 J        Enumerate indices, [1, 2, ..., len(A)]
ḣ         Head, get that many values from the start for each, forms the prefixes
  Ṣ€      Sort each
    Ṗ€    Pop each, removes the maximum
      Ṫ€  Tail each
\$\endgroup\$
  • \$\begingroup\$ @Challenger5 I don't believe that works \$\endgroup\$ – miles Aug 13 '17 at 17:14
  • \$\begingroup\$ @Challenger5 That doesn't work... \$\endgroup\$ – Erik the Outgolfer Aug 13 '17 at 19:53
  • \$\begingroup\$ @EriktheOutgolfer Oh, ok. \$\endgroup\$ – Esolanging Fruit Aug 14 '17 at 16:25
2
\$\begingroup\$

Java (OpenJDK 8), 87 86 bytes

a->{int x,y=x=1<<-1;for(int c:a){if((c>x?x=c:c)>y){x=y;y=c;}System.out.print(x+" ");}}

Try it online!

\$\endgroup\$
  • \$\begingroup\$ +1 for int x,y=x=. I didn't know separate declaration and assignment could be done in the same statement. \$\endgroup\$ – Jakob Aug 11 '17 at 22:00
2
\$\begingroup\$

Python 2, 45 bytes

f=lambda l:l[1:]and f(l[:-1])+[sorted(l)[-2]]

Try it online!

The right side of the code is self-explanatory. However, what do we put to the left of the and? Because we are concatenating parts of a list recursively, we need the left side to be truthy if l has 2 or more elements, and an empty list otherwise. l[1:] satisfies this criterion nicely.

\$\endgroup\$
1
\$\begingroup\$

C# (Mono), 81 bytes

using System.Linq;a=>a.Select((_,i)=>a.Take(++i).OrderBy(n=>n).Skip(i-2).First())

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Brachylog, 10 bytes

a₀ᶠb{okt}ᵐ

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Batch, 123 bytes

@set/af=s=%1
@for %%n in (%*)do @call:c %%n
@exit/b
:c
@if %1 gtr %s% set s=%1
@if %1 gtr %f% set/as=f,f=%1
@echo %s%
\$\endgroup\$
1
\$\begingroup\$

APL (Dyalog), 15 bytes

(2⊃⍒⊃¨⊂)¨1↓,\∘⊢

Try it online!

\$\endgroup\$
1
\$\begingroup\$

05AB1E, 5 bytes

Found another 5-byter, very different from Erik's solution. The arbitrary value is the first element of the list.

ηε{Áθ

Try it online!


Explanation

ηε{Áθ  - Full program that reads implicitly from STDIN and outputs to STDOUT.

η      - Push the Prefixes of the list.
 ε     - Apply to each element (each prefix):
  {      - Sort the prefix list.
   Á     - Shift the list to the right by 1, such that the first element goes to the 
           beginning  and the second largest one becomes the last.
    θ    - Get the last element (i.e. the second largest)
         - Print implicitly.

Let's take an example, to make it easier to understand.

  • First we get the implicit input, let's say it's [1, 5, 2, 3, 5, 9, 5, 8].

  • Then, we push its prefixes using η - [[1], [1, 5], [1, 5, 2], [1, 5, 2, 3], [1, 5, 2, 3, 5], [1, 5, 2, 3, 5, 9], [1, 5, 2, 3, 5, 9, 5], [1, 5, 2, 3, 5, 9, 5, 8]].

  • Now, the code maps through the list and sorts each prefix using { - [[1], [1, 5], [1, 2, 5], [1, 2, 3, 5], [1, 2, 3, 5, 5], [1, 2, 3, 5, 5, 9], [1, 2, 3, 5, 5, 5, 9], [1, 2, 3, 5, 5, 5, 8, 9]].

  • We then take the very last element and move it to the beginning: [[1], [5, 1], [5, 1, 2], [5, 1, 2, 3], [5, 1, 2, 3, 5], [9, 1, 2, 3, 5, 5], [9, 1, 2, 3, 5, 5, 5], [9, 1, 2, 3, 5, 5, 5, 8]].

  • Of course, now the code gets the last element of each sublist using θ - [1, 1, 2, 3, 5, 5, 5, 8] (the first one being the arbitrary value.

\$\endgroup\$
1
\$\begingroup\$

CJam, 16 bytes

{_,,:)\f{<$-2=}}

Try it online!

Returns first element for first.

-2 thanks to Challenger5.

\$\endgroup\$
  • \$\begingroup\$ {_,,:)\f{<$-2=}} is two bytes shorter. \$\endgroup\$ – Esolanging Fruit Aug 11 '17 at 17:25
1
\$\begingroup\$

R, 54 49 bytes

Thanks to Giuseppe -5 bytes. I did not know this feature of seq().

for(i in seq(x<-scan()))cat(sort(x[1:i],T)[2],"")

Try it online!

\$\endgroup\$
  • 1
    \$\begingroup\$ seq(x<-scan()) is shorter by a few bytes. \$\endgroup\$ – Giuseppe Aug 11 '17 at 17:43
1
\$\begingroup\$

Japt, 12 10 bytes

The output array consists of the first element in the input array followed by the desired sequence.

£¯YÄ n< g1

Test it


Explanation

Implicit input of array U.

£

Map over U, where Y is the current index.

¯YÄ

Slice U from 0 to Y+1.

n<

Sort descending.

g1

Get the second element.

Implicitly output the resulting array.

\$\endgroup\$
1
\$\begingroup\$

MATL, 19 10 bytes

Thanks to Luis Mendo for shaving off 9 bytes!

"GX@:)SP2)

Try it here.

Explanation

"GX@:)SP2)
"                  for all the values in the input
 G                 get input
  X@:)             get values up to the iteration
      SP           sort it in descending order
        2)         get the second value
                   implicit end of loop and output
\$\endgroup\$
  • \$\begingroup\$ @LuisMendo Wow! Goes to show how much I know about MATL. Thanks for the help! \$\endgroup\$ – DanTheMan Aug 12 '17 at 19:35
1
\$\begingroup\$

J, 13 bytes

_2&{@/:~ ::#\

Try it online! The first element is always 1.

Explanation

_2&{@/:~ ::#\
            \  Apply to prefixes
_2&{@/:~        Sort and take second-to-last atom
     /:~         Sort upwards
_2 {             Take second-to-last atom
         ::     If there's an error (i.e only one atom)
           #     Return the length of the list (1)

The space matters.

\$\endgroup\$
1
\$\begingroup\$

Ohm, 10 8 bytes

-2 bytes thanks to ETHproductions.

∙p»îS2~ª

Try it online!

Uh, this is odd but I don't know how else to push a negative number... I don't really know Ohm. :P

\$\endgroup\$
  • 1
    \$\begingroup\$ Okay, 0 2- seems very strange... \$\endgroup\$ – Mr. Xcoder Aug 11 '17 at 13:54
  • 1
    \$\begingroup\$ Just looking at the docs (I know nothing about Ohm), could you do 2~? \$\endgroup\$ – ETHproductions Aug 11 '17 at 14:18
  • \$\begingroup\$ @TEHProductions Oh, much better. Thanks! \$\endgroup\$ – totallyhuman Aug 11 '17 at 14:20
0
\$\begingroup\$

Mathematica, 45 bytes

Sort[s[[;;i]]][[-2]]~Table~{i,2,Length[s=#]}&

Try it online!

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

Perl 5, 42 + 1 (-a) = 43 bytes

say((sort{$b<=>$a}@F[0..$_])[1])for 1..$#F

Try it online!

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

Swift 3, 67 bytes

func g(l:[Int]){print((1..<l.count).map{l[0...$0].sorted()[$0-1]})}

Test Suite.

Swift 3, 65 bytes

{l in(1..<l.count).map{l[0...$0].sorted()[$0-1]}}as([Int])->[Int]

Test Suite.


How to run these?

The first one is a complete function that takes the input as a function parameter and prints the result. You can use them exactly as shown in the testing link. I decided to add instructions though, because the second type of function is used very rarely and most people don't even know of its existence. Usage:

g(l: [1, 1, 2, 2, 3, 3, 4] )

The second one is an anonymous function, like lambdas. You can use it exactly as you'd do it Python, declaring a variable f and calling it:

var f = {l in(1..<l.count).map{l[0...$0].sorted()[$0-1]}}as([Int])->[Int]

print(f([1, 1, 2, 2, 3, 3, 4]))

or wrap it between brackets and call it directly ((...)(ArrayGoesHere)):

print(({l in(1..<l.count).map{l[0...$0].sorted()[$0-1]}}as([Int])->[Int])([1, 1, 2, 2, 3, 3, 4]))
\$\endgroup\$
0
\$\begingroup\$

PHP, 53 bytes

for(;a&$n=$argv[++$i];rsort($a),print$a[1]._)$a[]=$n;

takes input from command line arguments. Output delimited, lead and trailed by semicola.
Run with -nr or try it online.

Yields a warning in PHP 7.1; replace a& with ""< to fix.
Or use for(;++$i<$argc;rsort($a),print$a[1]._)$a[]=$argv[$i]; (54 bytes)

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

Mathematica 42 Bytes

Independently arrived at a answer very similar to @Jenny_mathy but 3 bytes shorter

Sort[#[[;;i]]][[-2]]~Table~{i,2,Length@#}&

Realized that the 1st running max takes only 15 bytes and two function calls!:

Max~FoldList~#&

This can be done so concisely because Max has the attributes Flat and OneIdentity but that's not true for RankedMax which would be the logical replacement. Unfortunately defining attributes or modifying them on existing functions takes up way too many bytes, so the flattening must be done by other means.

All of the nth running maxes can be found in 48 bytes:

PadLeft[Sort/@Flatten/@FoldList[{##}&,{},#&@#]]&
\$\endgroup\$
0
\$\begingroup\$

Pyth, 15 bytes

FNr2hlQ@_S<QN1

Try it here: https://pyth.herokuapp.com/?code=FNr2hlQ%40_S%3CQN1&input=%5B1%2C+5%2C+2%2C+3%2C+5%2C+9%2C+5%2C+8%5D&debug=0

Explanation

FNr2hlQ - For loop with counter 2 <= N <= list length

@_S<QN1 - 2nd element when the first N elements of the list are sorted in ascending order and then reversed (sorted in descending order)

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

k, 13 bytes

{x(>x)1}'1_,\

Try it online!

           ,\ /sublists of increasing lengths (scan concat)
         1_   /remove the first sublist
{      }'     /for each sublist:
  (>x)        /    indices to permute sublist into largest to smallest
      1       /    get second index
 x            /    get sublist[that index]
\$\endgroup\$
0
\$\begingroup\$

Octave, 51 bytes

@(a){[~,I]=cummax(a);a(I(2:end))=-inf;cummax(a)}{3}

- An arbitrary value returned for the first element.

Try it online!

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

JavaScript (ES6), 43 51 bytes

Edit: Added 8 bytes since numerical sorting is desired. :(

a=>a.map((_,b)=>a.slice(0,b+1).sort((a,b)=>b-a)[1])

Keeping this one here, though, as it is shorter providing one wants lexicographical ordering:

a=>a.map((_,b)=>a.slice(0,b+1).sort()[b-1])

Both expressions produce undefined for the first element.

Test code

const golfed =

a=>a.map((_,b)=>a.slice(0,b+1).sort((a,b)=>b-a)[1])

const inputs = [
  [1, 5, 2, 3, 5, 9, 5, 8],
  [1, 1, 2, 2, 3, 3, 4],
  [2, 1, 0, -1, 0, 1, 2]
];
console.log(inputs.map(x => golfed(x)));
// [ [ undefined, 1, 2, 3, 5, 5, 5, 8 ],
//   [ undefined, 1, 1, 2, 2, 3, 3 ],
//   [ undefined, 1, 1, 1, 1, 1, 2 ] ]

\$\endgroup\$
  • \$\begingroup\$ Note that I would have preferred to simply comment on the existing JS post if it were not for the reputation system. \$\endgroup\$ – Aaron Hill Aug 12 '17 at 6:00
  • \$\begingroup\$ Welcome to PPCG! I don't like the 50-rep comment threshold either, but I guess they need it to keep spammers from commenting. Anyway, I think this will fail if the input contains a double digit number such as 10, as .sort() sorts lexicographically by default (i.e. 1,10,100,11,12,13,...,2,20,21,...). You'd need to include (a,b)=>a-b or similar to get it to sort by number. \$\endgroup\$ – ETHproductions Aug 12 '17 at 12:20
  • \$\begingroup\$ Thanks, @ETHproductions. I've updated for numerical ordering, which means this is no longer good enough. Oh, well. \$\endgroup\$ – Aaron Hill Aug 13 '17 at 21:10
0
\$\begingroup\$

Clojure, 56 bytes

#(for[i(drop 2(reductions conj[]%))](nth(sort-by - i)1))

Maybe there is a better way to generate those prefixes.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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