# Compute maximum excluding the current position

Given an array of integers A, the task is to output another array B of the same length so that B[i] is the maximum over A for every index that is not i. That is $$\B[i] = \max_{i' \ne i} A[i']\$$.

Examples:

A = [1, 5, -3, 4, 2]. B = [5, 4, 5, 5, 5]
A = [1, 2, 3]. B = [3, 3, 2]
A = [-1, -2, -3, -1]. B = [-1, -1, -1, -1]


The restriction is that your code must run in linear time in the length of the input array A.

The input will always contain at least two integers.

• Closely related (no running time restriction there) Feb 9 at 12:49
• @LuisMendo Yes. The difference is the time complexity restriction.
– Simd
Feb 9 at 13:24
• Is the input array guaranteed to contain at least two integers? Feb 9 at 14:00
• @Arnauld Thanks. Added to question.
– Simd
Feb 9 at 14:02
• @Rosario The O() means that any constant multiplicative or additive factor is ignored. So O(5n+10) is the same as O(n).
– Simd
Feb 10 at 11:39

# JavaScript (ES6), 54 bytes

-2 thanks to @l4m2

a=>a.map(v=>v-a?a:m,a.map(v=>a>v?m>v?0:m=v:(m=a,a=v)))


Try it online!

### Method

During the first pass, we compute $$\m_0=\max A_i\$$ and $$\m_1=\max_{i\neq j}A_i\$$ where $$\j\$$ is the index of the first occurrence of $$\m_0\$$. So we have $$\m_1=m_0\$$ if $$\m_0\$$ appears more than once and $$\m_1 otherwise.

During the second pass, we replace each value $$\v\$$ in the input array with $$\m_1\$$ if $$\v=m_0\$$ or $$\m_0\$$ otherwise.

In the JS implementation, we use a for $$\m_0\$$ and m for $$\m_1\$$.

### Commented

a =>           // a[] = input array,
//       re-used as m0 (initially NaN'ish)
a.map(v =>     // (2nd pass) for each value v in a[]:
v - a ?      //   if v is not equal to a:
a          //     output a
:            //   else:
m,         //     output m
a.map(v =>   //   (1st pass) for each value v in a[]:
a > v ?    //     if a is a number greater than v:
m > v ?  //       if m is a number greater than v:
0      //         do nothing
:        //       else:
m = v  //         save v in m
:          //     else:
(        //
m = a, //       save the previous maximum a in m
a = v  //       save the new maximum v in a
)        //
)            //   end of map()
)              // end of map()

• Can you use a in place of m?
– l4m2
Feb 9 at 13:49
• Can you explain the method?
– Simd
Feb 9 at 13:50
• But input [x] is undefined, it requires max of []
– l4m2
Feb 9 at 13:59
• That's not one of the test cases, and the problem explicitly states that the input will always contain at least two numbers. Feb 10 at 16:31
• @Someone This clarification was not included in the original challenge. It was added at my request, following l4m2's comments. Feb 10 at 16:36

# J, 21 bytes

(={],1>./@}.i.|.[)>./


Try it online!

Thanks to Jonathan Allen for pointing out I had missed the linear time constraint. This answer fixes that.

• >./ Max of all elements
• 1>./@}.i.|.[ Max of all elements after the first instance of the ordinary max is removed. Note because J does not have a "delete at" verb this is accomplished in a roundabout way: We rotate the elements left to put the normal max up front, then delete the first element, then take max.
• ], Returns "ordinary max" catted with the "modified max" as just described.
• = Boolean mask indicating all positions equal to the ordinary max.
• { When the mask is 1, return the modified max. Otherwise return the ordinary max.

## J, orig quadratic time, non-competing, 7 bytes

1>./\.]


Try it online!

J's outfix solves this directly.

# Jelly, 13 bytes

œṡFṀṭʋṀiⱮCị⁸ʋ


A monadic Link that accepts the list and yields the maximised version.

Try it online!

### How?

œṡFṀṭʋṀiⱮCị⁸ʋ - Link: list of integers, A
Ṁ       - maximum of {A} -> Max
œṡ            -   {A} split at first {Max}
F           -   flatten {that}
Ṁ          -   maximum of {that} -> SecondMax (possibly equal to Max)
ṭ         -   tack {SecondMax} to {Max} -> TwoMaxes = [Max, SecondMax]
Ɱ     -   map across {V in A} with:
i      -     first 1-indexed index of {V} in {TwoMaxes} or 0 if not found
-> 1 if V==Max;
2 if V==SecondMax and SecondMax!=Max;
0 otherwise
C    -   complement {those} (1-x) takes 0:1, 1:0, 2:-1
⁸  -   chain's left argument -> TwoMaxes
ị   -   {complemented locations in TwoMaxes} index into {TwoMaxes}
(1-indexed and modular, so 1:Max, 0:SecondMax, -1:Max)


### Non restricted solution, 3 bytes

Ṁ-Ƥ - map max over overlapping outfixes of length one less than the input


Try it online!

• Can you explain what non restricted means?
– Simd
Feb 11 at 8:53
• Your question is restricted-complexity. Feb 11 at 17:29

# Haskell + hgl, 34 bytes

zW ma<tl<g rS*^g lS

g h=h ma~<mn


Attempt This Online!

## Explanation

First this calculates the minimum value of the list (linear time). Then this scans the list rightwards calculating cumulative maxima, then it scans leftwards calculating cumulative maxima (both linear time). Finally it zips the two results together (lienar time). Since the cumulative maxima are the maxima of the prefixes / suffixes this means that when we zip them together we get the maximum of the values in the prefix before our value and the suffix after. This, naturally is the entire list other than the value in question. Since this is just a series of linear time operations the entire algorithm is linear time.

## Reflection

It feels wrong that g isn't shorter in point-free, however I think this is mostly because in normal golf, writing things in point free saves 2 bytes automatically by removing the function declaration. However here we need the function declaration (inlining g completely is very long) so point-free has to compete on even ground.

• fid should not be 3 bytes. This would make the point-free version of g shorter by a byte, replacing a ($ma) with fi ma, but would still be longer than the point-ful version. • What this really wants is a way to zip with an offset. I'm not sure how universally applicable this idea is, but if implemented it would really simplify this answer. # C (GCC)-lm, 97 93 90 104 101 bytes -2 bytes thanks to @Arnauld -1 byte thanks to @att +14 bytes due to a bug fix (m was initialized with a[0] this causes problems when a[0] is the max) -3 bytes thanks to @ceilingcat f(n,a,m,M,i)int*a;{for(m=fmin(M=*a,a[1]),i=2*n;--i;)i>n?M<*++a?m=M,M=*a:m<*a?m=*a:0:(*a--=*a-M?M:m);}  Attempt This Online! # C (GCC), 97 93 90 104 bytes  f(n,a,m,M,i)int*a;{for(M=*a,m=M<a[1]?M:a[1],i=2*n;--i;)i>n?M<*++a?m=M,M=*a:m<*a?m=*a:0:(*a--=*a-M?M:m);}  Attempt This Online! • 95 bytes Feb 9 at 18:12 • @Arnauld, shaved off another two bytes by reverting the ternary order; also thanks for the variable name changes much easier to understand now Feb 9 at 18:42 • 92 bytes – att Feb 9 at 19:22 • Wow, interesting idea to use fmin on integers. GCC treats it as a built-in, and even though GCC complains about an incompatible implicit declaration (of int fmin()), GCC does convert the args to double and take the return value as a double in XMM0 instead of an integer in EAX. godbolt.org/z/3W4r6esxE With -fno-builtin, that doesn't happen; GCC passes two integers in integer regs and expects a return value in EAX. So this code isn't relying on treating small integers as subnormal floats, which wouldn't work for non-negative; that wouldn't work due to calling convention diffs Feb 11 at 20:54 # Python 3, 71 bytes def f(a):h=nlargest(2,a);return[h[x>h[1]]for x in a] from heapq import*  Try it online! -4 bytes thanks to movatica Compute the first and second maximum h[0] and h[1] of array a, then output h[0] or h[1] where appropriate. Using sorted would take 20 fewer bytes than using heapq.nlargest, but would break the O(n) requirement. • This doesn't give the right answers on the test cases. You seem to be looking for the smallest where it should be the largest. – Simd Feb 9 at 14:12 • sorted(a)[::-1] is no longer linear time. – Simd Feb 9 at 14:19 • use x>h[1] to save a byte Feb 11 at 19:44 • 71 bytes by saving newlines: def f(a):h=nlargest(2,a);return[h[x>h[1]]for x in a] Feb 11 at 19:48 • @movatica Uh. I tried someting similar at first and it was a syntax error; I was sure python refused a def without a newline. Now it works. Don't know what I did wrong last time. Thanks. – Stef Feb 11 at 20:16 # JavaScript (Node.js), 71 bytes x=>x.map(v=>v-n?m:M(...x.filter(u=>u-n||0*++n)),m=n=M(...x)) M=Math.max  Try it online! -1 byte from Arnauld After first meet of n, n is increased so it's larger than max, aka no more value can equal to n • @Arnauld Two maps are both called once, max is called twice – l4m2 Feb 9 at 13:48 • Ah yes. I can see now how ++n prevents the inner map from being called more than once. Feb 9 at 13:53 # Python + NumPy, 44 bytes lambda L:L[L.argpartition(-2)[(L<max(L))-2]]  Attempt This Online! Takes and returns NumPy arrays. numpy.argpartition uses the linear time introselect algorithm to find in this case the second largest element (or rather its index) and split at this value. # Google Sheets, 49 bytes =let(a,A1:E1,m,max(a),sort(if(a=m,large(a,2),m)))  Put the input in cells A1:E1 and the formula in cell G1. max() and large() get evaluated once only. sort() is used as an array enabler and won't actually sort anything. # J, 20 19 bytes (]{~[=0{])(2$,\:,)/


Attempt This Online!

Copy of my answer in chat to the CMC version of this challenge.

-1 byte thanks to Jonah by spotting \:~@,,\:,.

(]{~[=0{])(2$\:~@,)/ input: v = a vector ( )/ tops = reduce from right: \:~@, concatenate and sort descending (this sorts a constant(2 or 3) number of values, so it runs in constant time per element) 2$           take the first two (largest and 2nd largest)
(        )            run the rest with v on the left and tops on the right:
0{]               the largest
[=                  per element, 1 if it is equal to the largest,
0 otherwise
]{~                    per element, 2nd largest if ^ is 1, largest otherwise
(gives 2nd largest for largest and largest otherwise)


# Jelly, 9 bytes

=Ṁị;Ṣṫ-ʋ/


Try it online!

Jelly port of the above algorithm.

(2$,\:,)/{~>./=]  Attempt This Online! J backport of the Jelly port of the above algorithm, which turns out to be shorter! Does not reuse the "tops" array and computes the maximum again instead, which does not affect the overall time complexity. # J, 20 bytes (>.|.)&(#$__,>./\)|.


Attempt This Online!

f/\ normally creates prefixes and reduces each prefix by f from the right, which costs quadratic time, but it is special-cased for atomic and associative functions, which includes >. (max of two numbers).

(>.|.)&(#$__,>./\)|. input: v = a vector |. reverse(v) call the rest with v on the left and reverse(v) on the right: ( )&( ) apply the right to both sides: >./\ cumulative max (linear) #$__,             prepend __ (negative infinity) and
chop one from the end (linear)
>.|.                   reverse the right side again and
take elementwise max (linear)

• Nice, (]{~[=0{])(2$,\:,)/ for 19. Feb 13 at 2:39 # Scala 3, 10994 92 bytes Saved 17 bytes thanks to @movatica Golfed version. Attempt This Online! a=>{val m=a.max;val s=if(a.count(_==m)>1)m else a.filter(_<m).max;a.map(x=>if(x<m)m else s)}  Ungolfed version. Attempt This Online! object Main { def main(args: Array[String]): Unit = { val tests = Array( (Array(1, 5, -3, 4, 2), Array(5, 4, 5, 5, 5)), (Array(1, 2, 3), Array(3, 3, 2)), (Array(-1, -2, -3, -1), Array(-1, -1, -1, -1)) ); tests.foreach { case (a, b) => val c = f(a) println(s"${a.mkString("[", ", ", "]")} --> Expected: ${b.mkString("[", ", ", "]")}, Actual:${c.mkString("[", ", ", "]")}, Result: ${b.sameElements(c)}") } } def f(a: Array[Int]): Array[Int] = { if (a.length <= 1) return a val maxVal = a.max val secondMaxVal = if (a.count(_ == maxVal) > 1) maxVal else a.filter(_ != maxVal).max a.map(x => if (x == maxVal) secondMaxVal else maxVal) } }  • The challenge states, that the input always has size >= 2, so you can remove if(a.size<=1)a; Mar 3 at 18:49 • Observation: x <= m, so (x != m) => (x < m). This saves 2 more bytes Mar 4 at 17:42 # Charcoal, 26 bytes ≔⌈θη≔⌕θηζ≔⌈Φθ⁻κζζＩＥθ⎇⁼ιηζη  Try it online! Link is to verbose version of code. Explanation: ≔⌈θη  Get the maximum value of the input list. ≔⌕θηζ  Get the index of its first occurrence. ≔⌈Φθ⁻κζζ  Make a new list excluding that index, and take the maximum of that. ＩＥθ⎇⁼ιηζη  Output that value for the maximum values in the list, and the maximum for the other values. By comparison a fully golfed version would be 19 9 bytes: ＩＥθ⌈Φθ⁻μκ  Try it online! Link is to verbose version of code. Runs in O(n²) time. Explanation: For each element, creates a new list without that element, and takes the maximum of that list. • Does your golfed answer run in linear time? It looks like it should from the description. – Simd Feb 10 at 7:25 • @Simd No, my golfed answer is nowhere near linear time; the main loop recomputes max(A) (twice, not that that matters) for each element for a start, so that's already O(n²), but for each element that equals the maximum, there's another O(n²) per element to compute the second highest element. – Neil Feb 10 at 7:51 • @Simd ... or if I actually golfed it correctly, it would just be O(n²)... – Neil Feb 10 at 7:55 • The challenge does require linear time. – Simd Feb 10 at 8:02 • @Simd Yes there's a linear time answer and a golfed answer. – Neil Feb 10 at 8:05 # APL(NARS), 119 chars r←f w;a;b;n;i;t n←≢w⋄i←2⋄a←b←w[1] →4×⍳i>n⋄→3×⍳∼b<t←w[i]⋄a←b⋄b←t i+←1⋄→2 i←1⋄r←⍬ t←w[i]⋄→6×⍳∼t=b⋄r,←a⋄→7 r,←b →5×⍳n≥i+←1  15+17+29+7+7+23+4+10 +7=119 2 pass of the array, one for to find the maxs, and one for build the result array. Test&how to use. one not difficult solution but possible the more long and lazy.  f 1 2 3 3 3 2 f 1 1 1 1 f ,1 1  • How does it work? – Simd Feb 9 at 17:40 • @Simd it is used standard input ⎕ and a global variable k for store original array. all the remain are easy APL instructions. ⎕fmt is used only for see if type is right Feb 9 at 17:46 • What is the algorithm it is using? – Simd Feb 9 at 17:48 • i dont know if it is right. in the array seen as a set is cancelled the element array[i] for i 1..(lenght array), then is calculate the max each sub array, and it is return. this fail if all emements are all the same Feb 9 at 17:54 • Now would be ok even if all emements are the same Feb 9 at 18:38 # Perl 5-MList::Util=max,first -a, 81 bytes $m=max@F;$i=first{$F[$_]==$m}@t=0..$#F;$;=max@F[grep$i-$_,@t];say$_-$i?$m:$;for@t


Try it online!

# Python 3.8 (pre-release), 72 66 bytes

def f(A):B=len(A)*[A.pop(i:=A.index(max(A)))];B[i]=max(A);return B


Try it online!

First, observe that B contains the second largest value of A at position i iff the largest value in A exists exactly once, at that very position. In all other cases (largest value exists more than once or A holds only one value), B consists solely of max(A). So all we have to handle is that one special case.

Ungolfed:

def f(A):
l = len(A)
m = max(A)
B = l * [m]
i = A.index(m)
A.pop(i)
B[i] = max(A)
return B


As max and index are linear operations and len, pop and assignment are constant time, the runtime is O(3n) = O(n)

# APL+WIN, 22 bytes

Prompts for vector. Index origin = 0

⌈/0 1↓(⍳⍴n)⌽(2⍴⍴n)⍴n←⎕


Try it online! Thanks to Dyalog Classic