40
\$\begingroup\$

Inspired by a question over at Stack Overflow. The title here is entirely my fault.


The challenge

Given a list of positive integers containing at least two entries, replace each number by the minimum of all entries excluding itself.

Test cases

[4 3 2 5]    ->  [2 2 3 2]
[4 2 2 5]    ->  [2 2 2 2]
[6 3 5 5 8]  ->  [3 5 3 3 3]
[7 1]        ->  [1 7]
[9 9]        ->  [9 9]
[9 8 9]      ->  [8 9 8]

Rules

The algorithm should theoretically work for any input size (greater than one) and values (positive integers). It's accepted if the program is limited by time, memory or data types and so only works for numbers up to a given value, or for input size up to a given value.

Programs or functions are allowed, in any programming language. Standard loopholes are forbidden.

Input can be taken by any reasonable means; and with any format. Same for output. Input and output formats may be different.

Shortest code in bytes wins.

\$\endgroup\$
  • \$\begingroup\$ What should [4 3 2 2 5] output? \$\endgroup\$ – Kritixi Lithos Apr 27 '17 at 9:03
  • \$\begingroup\$ @KritixiLithos didn't the second test case cover this? \$\endgroup\$ – Leaky Nun Apr 27 '17 at 9:04
  • \$\begingroup\$ @KritixiLithos For input [4 3 2 2 5] the output would be [2 2 2 2 2] (this is similar to the second test case) \$\endgroup\$ – Luis Mendo Apr 27 '17 at 9:04
  • \$\begingroup\$ Oh, I missed the second test case. But now I understand how it works \$\endgroup\$ – Kritixi Lithos Apr 27 '17 at 9:08
  • \$\begingroup\$ @LuisMendo You have changed "integer" to "any input size and values". Does that mean we need to account for all real numbers? \$\endgroup\$ – Leaky Nun Apr 27 '17 at 9:34

31 Answers 31

19
\$\begingroup\$

Jelly, 9 6 5 bytes

JḟЀ`ị⁸Ṃ€
ṙJṖ€Ṃ€
ṙJṖ«/     argument: 1D array (z)

 J        [1,2,3,...,len(z)]
ṙ         rotate z by each of the above amount (current array is 2D)
  Ṗ       remove the last array
   «/     reduce by [impliclitly vectorized] minimum

Try it online!

Verify all of them at once! (slightly modified)

I'm pretty sure Dennis can out-golf this.

How it works

The algorithm is rather convoluted. Let us observe what this does to [4,2,2,5].

Firstly, we use J to obtain [1,2,3,4]. Note that Jelly uses 1-indexing.

Then, we see . It takes two arguments: an array and an integer. It rotates the array to the left by an amount specified by the integer. Here, would see [4,2,2,5] on its left and [1,2,3,4] on its right (more about how this works can be found in the tutorial). In Jelly, commands implicitly vectorize. Therefore, this command will be performed over each individual element on the right, which is why we would create a 2D array:

Therefore, [4,2,2,5]ṙ[1,2,3,4] becomes [[4,2,2,5]ṙ1,[4,2,2,5]ṙ2,[4,2,2,5]ṙ3,[4,2,2,5]ṙ4], which becomes:

[[2,2,5,4],
 [2,5,4,2],
 [5,4,2,2],
 [4,2,2,5]]

Notice that the original elements are on the last row, since in that row we rotated to the left by an amount equal to the length of the array, which is why we use next to remove that row, so that the columns are the collections of the elements of the array which are not at the current index:

[[2,2,5,4],
 [2,5,4,2],
 [5,4,2,2]]

The following operation, «/, is also quite convoluted. Firstly, « returns the minimum of the two numbers it sees on its left and on its right. For example, 5«3 returns 3. Now, if the two arguments are arrays, then it would vectorize as I have said above. What this means it that [1,5,2,3]«[4,1,5,2] would become [1«4,5«1,2«5,3«2] which is [1,1,2,2]. Now, / is reduce, which means that we do the operation over each row until the end. For example, [1,2,3,4]+/ would become ((1+2)+3)+4, which is the sum of the array [1,2,3,4].

So, if we apply «/ to the 2D array we just obtained, we would get:

([2,2,5,4]«[2,5,4,2])«[5,4,2,2]

which, because of the vectorization, would be equivalent to:

[2«2«5,2«5«4,5«4«2,4«2«2]

which computes the minimum of every array without the element at the index.

\$\endgroup\$
  • 1
    \$\begingroup\$ Oh, your edit... you got there first. \$\endgroup\$ – Jonathan Allan Apr 27 '17 at 9:10
  • 1
    \$\begingroup\$ @JonathanAllan I'm sorry. \$\endgroup\$ – Leaky Nun Apr 27 '17 at 9:11
40
\$\begingroup\$

Python 2, 41 bytes

lambda l:[sorted(l)[x==min(l)]for x in l]

Try it online!

For each element x we check whether x==min(l). If not, this is False, which is treated as 0 when used as a list index into sorted(l), giving the smallest element. Otherwise, it's True aka 1, giving the second-smallest element, since that element itself is smallest and should be ignored.

\$\endgroup\$
  • 2
    \$\begingroup\$ I have a hard time believing that this works. \$\endgroup\$ – Leaky Nun Apr 27 '17 at 9:24
  • 2
    \$\begingroup\$ Great approach! \$\endgroup\$ – Luis Mendo Apr 27 '17 at 9:26
  • \$\begingroup\$ Could you add an explanation? It wouldn't be very complicated, but the trick of "every number will be the minimum, except for the one that is the minimum, which will be the second-smallest" and the fact that False gets converted to 0 and True gets converted to 1 are really cool and should be bragged about^W^Wexplained \$\endgroup\$ – Fund Monica's Lawsuit Apr 28 '17 at 16:55
18
\$\begingroup\$

Jelly, 5 bytes

=Ṃ‘ịṢ

Try it online!

How?

=Ṃ‘ịṢ - Main link: list a     e.g.  [4,3,2,5]
 Ṃ    - minimum of a                2
=     - equals? (vectorises)        [0,0,1,0]
  ‘   - increment                   [1,1,2,1]
    Ṣ - sort a                      [2,3,4,5]
   ị  - index into                  [2,2,3,2]
\$\endgroup\$
  • 4
    \$\begingroup\$ @LeakyNun This is not a port, it's just the same method, I'm still looking for less too... I have upvoted that answer too now :) \$\endgroup\$ – Jonathan Allan Apr 27 '17 at 9:40
  • 5
    \$\begingroup\$ @LeakyNun I am new here, but are you always this hostile? It's not like there are ton of unique ways to approach this. Even if he did port it, he still has the shorter answer. \$\endgroup\$ – Grayson Kent Apr 27 '17 at 15:46
  • 3
    \$\begingroup\$ @GraysonKent I apologize for my perceived hostility. \$\endgroup\$ – Leaky Nun Apr 27 '17 at 17:32
  • 1
    \$\begingroup\$ @GraysonKent Welcome to PPCG! \$\endgroup\$ – Luis Mendo Apr 27 '17 at 23:47
  • 1
    \$\begingroup\$ @LeakyNun This happens a lot in simpler challenges, you can't really say every answer is a port of every other one \$\endgroup\$ – ASCII-only Apr 28 '17 at 0:20
12
\$\begingroup\$

Haskell, 42 41 39 bytes

EDIT:

  • -1 byte thanks to nimi!
  • -2 bytes. One thanks to xnor! And one by myself.

f takes a list of integers (or any Ord type) and returns a list.

f(x:y)=minimum y:(fst<$>zip(f$y++[x])y)

Try it online!

f recurses while rotating the list. x is the first list element and y the remainder. Since the recursion is infinite, the result list needs to be cut off: fst<$>zip...y is a shorter way of saying take(length y)....

\$\endgroup\$
  • 1
    \$\begingroup\$ You can save one byte by naming the whole input list via @ and flip the lists to be zipped: f l@(x:y)=fst<$>zip(minimum...)l. \$\endgroup\$ – nimi Apr 27 '17 at 20:01
  • 1
    \$\begingroup\$ f(h:t)=minimum t:(fst<$>zip(f(t++[h]))t) \$\endgroup\$ – xnor Apr 27 '17 at 21:19
9
\$\begingroup\$

Octave, 26 bytes

@(x)sort(x)((x==min(x))+1)

A similar approach as used in this answer, which happens to be the same as this.

I'm not really a fan of just porting other answers, which is why I'd like to note that I had a similar idea before I saw the other ones.

Explanation:

Jonathan Allan has already provided a good explanation for the Jelly-code, so this covers the Octave-bit, and why it works (and wouldn't work in MATLAB).

@(x)                       % An unnamed anonymous function taking a vector x as input
    sort(x)                % Gives a sorted version of x
            (x==min(x))    % Checks if each element is equal to the minimum value
           ((x==min(x))+1) % Adds 1 to the boolean vector, to use as indices
@(x)sort(x)((x==min(x))+1) % Complete function

This doesn't work in MATLAB, since inline assignments and direct indexing doesn't work. sort(x)(1) gives an error in MATLAB, not the first element in the sorted vector.

\$\endgroup\$
8
\$\begingroup\$

Haskell, 41 bytes

a#(b:c)=minimum(a++c):(b:a)#c
a#b=b 
([]#)

Usage example: ([]#) [4,3,2,5]-> [2,2,3,2]. Try it online!

Start with an empty accumulator a and run down the input list. The next element in the output list is the minimum of the accumulator a and all but the first element of the input list (->c) followed by a recursive call with the first element b added to the accumulator and c. Stop when you reach the end of the input list.

\$\endgroup\$
7
\$\begingroup\$

JavaScript (ES6), 50 46 bytes

a=>a.map((_,i)=>Math.min(...a.filter(_=>i--)))

Edit: Saved 4 bytes thanks to @Arnauld.

\$\endgroup\$
  • \$\begingroup\$ a=>a.map(x=>Math.min(...a.filter(y=>x!=y))) for 43 bytes. \$\endgroup\$ – Shaggy Apr 27 '17 at 9:35
  • \$\begingroup\$ @Shaggy I don't think that works for an input such as 3,3,3,3 \$\endgroup\$ – Arnauld Apr 27 '17 at 9:36
  • \$\begingroup\$ D'oh! No, it won't work if there are 2 or more occurrences of the minimum value. \$\endgroup\$ – Shaggy Apr 27 '17 at 9:37
  • 1
    \$\begingroup\$ However, you can do a=>a.map((_,i)=>Math.min(...a.filter(_=>i--))) for 46. \$\endgroup\$ – Arnauld Apr 27 '17 at 9:40
  • \$\begingroup\$ @Arnauld Very clever, thanks! \$\endgroup\$ – Neil Apr 27 '17 at 9:42
7
\$\begingroup\$

Brachylog, 13 12 bytes

l+₁:?⊇ᶠ⁽⌋ᵐb↔

Try it online!

Saved one byte thanks to @ais523.

Explanation

l+₁:?            The list [length(Input) + 1, Input]
     ⊇ᶠ⁽         Find the length(Input) + 1 first subsets of the Input
        ⌋ᵐ       Get the min of each subset 
           b↔    Remove the first element and reverse

We exploit the fact that unifies subsets from biggest to smallest. For example for [1,2,3], the subsets we get are in this order: [1,2,3], [1,2], [1,3], [2,3], [1], [2], [3], [].

We can see that the subsets [1,2], [1,3], [2,3] are the ones we want the minimum from, but are in the reverse order compared to the input list (hence the ). We can select those subsets only by finding the first length(Input) + 1 subsets, which will contain all of them + the entire list first. We discard that entire list with b.

\$\endgroup\$
  • 1
    \$\begingroup\$ You can save a byte by splitting your "findall subset+minimum" into "findall subset" and "map minimum". (I need to go add this to the Brachylog tips thread, now you've reminded me of it.) \$\endgroup\$ – user62131 Apr 27 '17 at 22:55
  • 1
    \$\begingroup\$ @ais523 Thanks, I always forget about that trick… \$\endgroup\$ – Fatalize Apr 28 '17 at 6:20
6
\$\begingroup\$

Actually, 13 bytes

;;S╝m╗⌠╜=╛E⌡M

Uses the same technique that xnor also discovered.

Try it online!

Explanation:

;;S╝m╗⌠╜=╛E⌡M
;;             make two extra copies of input list
  S╝           sort one and save it in register 1
    m╗         save the minimum of the other in register 0
      ⌠╜=╛E⌡M  for each value in list:
       ╜=╛E      return the minimum element of the input list if the value is not equal to the minimum, else return the second-smallest element
\$\endgroup\$
  • 1
    \$\begingroup\$ You still haven't allowed us to look at the global stack inside the temporary stack? \$\endgroup\$ – Leaky Nun Apr 27 '17 at 9:36
  • 1
    \$\begingroup\$ @LeakyNun Not yet. In the current state that the interpreter's code is in, that would be very difficult. After I finish the large refactoring I'm working on, I'll see about adding that functionality. \$\endgroup\$ – Mego Apr 27 '17 at 9:37
  • 1
    \$\begingroup\$ When did you begin the large refactoring? \$\endgroup\$ – Leaky Nun Apr 27 '17 at 9:37
6
\$\begingroup\$

R, 46 31 bytes

l=scan();sort(l)[(min(l)==l)+1]

implements Stewie Griffin's solution in R, alas, my original idea is 50% longer! still reads the list from stdin, but now returns a much more readable numeric vector.

Try it online!

old implementation:

l=scan();Map(function(x)min(l[-x]),match(l,l))

reads in the list from stdin. A negative index l[-x] excludes the element from the list, and match(l,l) returns the index of the first occurrence of each element of the list. Returns a list.

\$\endgroup\$
5
\$\begingroup\$

Python 2, 51 bytes

I know there's already a better Python solution, but I still want to post mine.

lambda L:[min(L[:i]+L[i+1:])for i in range(len(L))]

Try it online

\$\endgroup\$
5
\$\begingroup\$

Mathematica 34 Bytes

Min[#~Drop~{i}]~Table~{i,Tr[1^#]}&
\$\endgroup\$
5
\$\begingroup\$

PowerShell, 68 59 bytes

($a=$args)|%{$b+=@((($c=$a|sort)[0],$c[1])[$_-eq$c[0]])};$b

Try it online!

I'm pretty confident it can be shortened, I will continue to look at it

\$\endgroup\$
4
\$\begingroup\$

C, 85 bytes

i,j,m;f(d,o,n)int*d,*o;{for(i=n;i--;)for(m=d[!i],j=n;j;o[i]=m=--j^i&&d[j]<m?d[j]:m);}

First argument is the input integer array. The second argument is the output integer array. The third argument is the element count for both arrays.

See it work online.

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

Perl 6,  26 24  19 bytes

26

{.map: (.Bag∖*).min.key}

Note that is U+2216 not \ U+5C

Try it

{.map: (.Bag⊖*).min.key}

Try it

24

{(.min X%$_)X||.sort[1]}

Try it

19

{.sort[.min X==$_]}

Try it


26

{           # bare block lambda with implicit parameter 「$_」

  .map:     # for each of the values in the input (implicit method call on 「$_」)
  (
    .Bag    # turn the block's input into a Bag
    ∖       # set-difference           「∖」 U+2216 aka 「(-)」
    # ⊖     # symmetric-set-difference 「⊖」 U+2296 aka 「(^)」
    *       # turn expression into a WhateverCode lambda (this is the parameter)
  ).min.key # get the minimum pair from the Bag, and return its key
}

I used the "fancy" unicode operators rather than the ascii equivalents because they would have required a space before them so that they wouldn't be parsed as part of the .Bag method call.

24

{
  (.min X% $_) # the minimum cross modulus-ed with the input
  X||          # cross or-ed 
  .sort[1]     # with the second minimum
}

19

{
  .sort\        # sort the values
  [             # index into that
    .min X== $_ # the minimum cross compared with the input
  ]
}

(The 24 and 19 byte golfs were inspired by a Jelly implementation)

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

Clojure, 36 81 62 71 bytes

Newest (shouldn't really submit these in a hurry):

#(for[c[(zipmap(range)%)]i(sort(keys c))](apply min(vals(dissoc c i))))

Try it online.

Aaaand this one has a bug (62 bytes), zipmap produces an unordered map so this won't produce the correct sequence on larger inputs.

#(for[c[(zipmap(range)%)][i v]c](apply min(vals(dissoc c i))))

v is not actually used for anything but this is shorter than i (keys c).

Previous at 81 bytes:

Try it online.

#(let[r(range(count %))](for[i r](apply min(for[j r :when(not= i j)](nth % j)))))

Try it online.

Oh damn the original (36 bytes) does not work when the minimum number is repeated, [4 2 2 5] results in [2 4 4 2] as both 2s are removed :(

#(for[i %](apply min(remove #{i}%)))

#{i} is the set which contains only i, it returns truthy for i and falsy for others, meaning that the minimum is calculated from all other numbers within the input list.

Try it online.

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

Pyth, 8 7 bytes

mh.-SQ]

-1 Byte thanks to @isaacg

Try it!

\$\endgroup\$
  • \$\begingroup\$ You can remove the d at the end - it's implicitly filled in. \$\endgroup\$ – isaacg Apr 28 '17 at 22:25
  • \$\begingroup\$ @isaacg thank you, didn't know that \$\endgroup\$ – KarlKastor Apr 29 '17 at 10:40
2
\$\begingroup\$

PHP, 72 Bytes

<?$k=$g=$_GET;sort($k);foreach($g as&$v)$v=$k[$v==$k[0]?:0];print_r($g);

Online Version

\$\endgroup\$
2
\$\begingroup\$

PHP, 47 bytes

while(++$i<$argc)echo@min([z,$i=>z]+$argv),' ';
\$\endgroup\$
2
\$\begingroup\$

Scala, 37 bytes

l.indices map(i=>l diff Seq(l(i))min)

l is any collection of Int.

Test cases:

scala> val l = List(4,3,2,5)
l: List[Int] = List(4, 3, 2, 5)

scala> l.indices map(i=>l diff Seq(l(i))min)
res0: scala.collection.immutable.IndexedSeq[Int] = Vector(2, 2, 3, 2)

scala> val l = List(4,2,2,5)
l: List[Int] = List(4, 2, 2, 5)

scala> l.indices map(i=>l diff Seq(l(i))min)
res1: scala.collection.immutable.IndexedSeq[Int] = Vector(2, 2, 2, 2)

scala> val l = List(6,3,5,5,8)
l: List[Int] = List(6, 3, 5, 5, 8)

scala> l.indices map(i=>l diff Seq(l(i))min)
res2: scala.collection.immutable.IndexedSeq[Int] = Vector(3, 5, 3, 3, 3)

scala> val l = List(7,1)
l: List[Int] = List(7, 1)

scala> l.indices map(i=>l diff Seq(l(i))min)
res3: scala.collection.immutable.IndexedSeq[Int] = Vector(1, 7)

scala> val l = List(9,9)
l: List[Int] = List(9, 9)

scala> l.indices map(i=>l diff Seq(l(i))min)
res4: scala.collection.immutable.IndexedSeq[Int] = Vector(9, 9)

scala> val l = List(9,8,9)
l: List[Int] = List(9, 8, 9)

scala> l.indices map(i=>l diff Seq(l(i))min)
res5: scala.collection.immutable.IndexedSeq[Int] = Vector(8, 9, 8)

This can probably still be golfed, I couldn't find a shorter way to remove an element from a list than l diff Seq(l(i))

\$\endgroup\$
2
\$\begingroup\$

C#, 36 Bytes

i.Select((x,a)=>i.Where((y,b)=>b!=a).Min())

Takes the elements (i) and looks in the elements without the current item for the minimal value.

It's kind of sad, that some other attempts don't work, as we work with primitive types, and therefore don't have lists with references to compare the items from.

\$\endgroup\$
2
\$\begingroup\$

PowerShell, 49 38 bytes

-11 bytes thanks to mazzy

($a=$args)|%{($c=$a|sort)[$_-eq$c[0]]}

Try it online!

Improvement of Sinusoid's lovely answer. Saves 10 bytes by using explicit output instead of building an array. Indexes into the sorted array to either spot 0 (i.e. smallest value) or spot 1 if the conditional is true.

\$\endgroup\$
  • 1
    \$\begingroup\$ It's smart. Save more :) Try it online! \$\endgroup\$ – mazzy Mar 14 at 16:18
  • 1
    \$\begingroup\$ @mazzy Well done. It's obvious now that I see it but I never would've put that together. \$\endgroup\$ – Veskah Mar 14 at 16:31
  • 1
    \$\begingroup\$ Nice work! Yours is more lovely :) \$\endgroup\$ – Sinusoid Jun 13 at 17:52
1
\$\begingroup\$

Perl 5, 43 bytes

sub{@x=sort{$a<=>$b}@_;map$x[$_==$x[0]],@_}

Equivalent to the Python solution. Perl's sort unfortunately has the wrong default for numbers (requiring an explicit comparator), and min isn't built-in, but it almost makes up for it by sub being shorter than lambda, map$_, being shorter than x for x in, and the implicitness of return and args lists.

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

Ruby, 30 bytes

For each element, sort the array, remove the current element and grab the first element of the remaining array.

->a{a.map{|e|(a.sort-[e])[0]}}

It's an anonymous function that can be used like this:

f = ->a{a.map{|e|(a.sort-[e])[0]}}
p f[[6, 3, 5, 5, 8]] # => [3, 5, 3, 3, 3]
\$\endgroup\$
1
\$\begingroup\$

CJam, 15 bytes

{:S{S:e<=S$=}%}

Essentially a translation of xnor's algorithm into CJam.

This is an unnamed block that takes an array from the stack and leaves the result on the stack.

Explanation:

{
  :S     e# Save in S
  {      e# For X in S:
    S:e< e#   Push Min(S)
    =    e#   X == Min(S)
    S$=  e#   Sorted(S)[top of stack]
  }%     e# End
}
\$\endgroup\$
  • 1
    \$\begingroup\$ @LuisMendo Whoops - I forgot to actually sort the array. It should work now. \$\endgroup\$ – Esolanging Fruit Apr 30 '17 at 23:38
1
\$\begingroup\$

05AB1E, 5 bytes

{sWQè

Port of @xnor's Python 2 answer.

Try it online or verify all test cases.

Explanation:

{        # Sort the (implicit) input-list
         #  i.e. [4,1,3,6] → [1,3,4,6]
 s       # Swap, so the (implicit) input-list is at the top of the stack again
  W      # Get the minimum without popping from the list
         #  i.e. [4,1,3,6] → 1
   Q     # Check for each element if they are equal to this value (1/0 as truthy/falsey)
         #  i.e. [4,1,3,6] and 1 → [0,1,0,0]
    è    # Use these 0s and 1s to index in the sorted list
         #  i.e. [1,3,4,6] and [0,1,0,0] → [1,3,1,1]
\$\endgroup\$
1
\$\begingroup\$

Java 8, 119 bytes

a->{int t[]=a.clone(),m=a[0],i=a.length;for(int x:a)m=x<m?x:m;for(java.util.Arrays.sort(t);i-->0;)a[i]=t[a[i]==m?1:0];}

Port of @xnor's Python 2 answer.

Modifies the input-array instead of returning a new one to save bytes.

Try it online.

Explanation:

a->{                  // Method with integer-array parameter and no return-type
  int t[]=a.clone(),  //  Make a copy of the input-array
      m=a[0],         //  Minimum `m`, starting at the first value of the input-array
      i=a.length;     //  Index-integer, starting at the length of the input-array
  for(int x:a)        //  Loop over the input-array
    m=x<m?            //   If the current item is smaller than the current `m`
       x              //    Replace `m` with this value
      :               //   Else:
       m;             //    Leave `m` the same
  for(java.util.Arrays.sort(t);
                      //  Sort the copy we've made of the input-array
      i-->0;)         //  Loop `i` in the range (length, 0]
    a[i]=             //   Modify the item at index `i` of the input-array to:
      t[              //    The item in the sorted array at index:
        a[i]==m?      //     If the current item and the minimum are equal:
         1            //      Use index 1 in the sorted array
        :             //     Else:
         0];}         //      Use index 0 in the sorted array
\$\endgroup\$
1
+100
\$\begingroup\$

APL (Dyalog Extended), 7 bytes

Port of xnor's Python 2 answer. Requires ⎕IO←0:

∧⊇⍨⊢=⌊/

Try it online!

Explanation:

∧⊇⍨⊢=⌊/  ⍝ Monadic function train
      ⌊/  ⍝ The minimum element of the input
    ⊢=    ⍝ Element-wise compare the input to the above
          ⍝ Results in a boolean vector, let's call it "X"
∧         ⍝ Sort the input
 ⊇⍨      ⍝ Index into sorted input by X
\$\endgroup\$
1
\$\begingroup\$

Haskell, 76 bytes

This is considerably longer than the earlier Haskell entries, but it's the first that only performs a linear number of comparisons and a linear amount of additional work.

f(x:y)|(z,w)<-x!y=z:w
a![x]=(x,[a])
a!(x:y)|(p,q)<-a#x!y=(x#p,a#p:q)
(#)=min

Try it online!

Explanation

! takes two arguments: a running minimum and a nonempty list. It returns the minimum value in the list and the result of processing the given list using the running minimum.

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

MathGolf, 9 7 bytes

s_╓?m=§

Try it online!

Explanation

Basically a port of Kevin Cruijssen's 05AB1E answer, but I lose 2 bytes thanks to having to do things explicitly.

s         sort(array)
 _        duplicate TOS
  ╓       minimum of two elements, min of list, minimum by filter
   ?      rot3 pops input on top of stack again
    m=    explicit map to check equality
      §   get from sorted array for each
\$\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.