# 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.

Inspired by Arnauld's answer

• >./ 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
ʋ        - 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)

### 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)

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