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.
-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))) 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<m_0\$ 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\$.
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() 
a in place of m? \$\endgroup\$ (={],1>./@}.i.|.[)>./ Thanks to Jonathan Allen for pointing out I had missed the linear time constraint. This answer fixes that.
Inspired by Arnauld's answer
>./ Max of all elements1>./@}.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.1>./\.] J's outfix solves this directly.
œṡFṀṭʋṀiⱮCị⁸ʋ A monadic Link that accepts the list and yields the maximised version.
œṡFṀṭʋṀiⱮCị⁸ʋ - Link: list of integers, A Ṁ - maximum of {A} -> Max ʋ - last four links as a dyad - f(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] ʋ - last four links as a dyad - f(TwoMaxes, A): Ɱ - 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) Ṁ-Ƥ - map max over overlapping outfixes of length one less than the input 
zW ma<tl<g rS*^g lS g h=h ma~<mn 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.
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.
-lm, -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);} 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);} 
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 \$\endgroup\$ def f(a):h=nlargest(2,a);return[h[x>h[1]]for x in a] from heapq import* -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.
x>h[1] to save a byte \$\endgroup\$ def f(a):h=nlargest(2,a);return[h[x>h[1]]for x in a] \$\endgroup\$ def without a newline. Now it works. Don't know what I did wrong last time. Thanks. \$\endgroup\$ x=>x.map(v=>v-n?m:M(...x.filter(u=>u-n||0*++n)),m=n=M(...x)) M=Math.max -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
++n prevents the inner map from being called more than once. \$\endgroup\$ lambda L:L[L.argpartition(-2)[(L<max(L))-2]] 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.
=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.
(]{~[=0{])(2$,\:,)/ 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 port of the above algorithm.
(2$,\:,)/{~>./=] 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.
(>.|.)&(#$__,>./\)|. Port of Wheat Wizard's Haskell+hgl answer.
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) 
(]{~[=0{])(2$,\:,)/ for 19. \$\endgroup\$ 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) } } 
if(a.size<=1)a; \$\endgroup\$ x <= m, so (x != m) => (x < m). This saves 2 more bytes \$\endgroup\$ ≔⌈θη≔⌕θηζ≔⌈Φθ⁻κζζＩＥθ⎇⁼ιηζη 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.
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. \$\endgroup\$ 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 
-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 
def f(A):B=len(A)*[A.pop(i:=A.index(max(A)))];B[i]=max(A);return B 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)
Prompts for vector. Index origin = 0
⌈/0 1↓(⍳⍴n)⌽(2⍴⍴n)⍴n←⎕ 