11
\$\begingroup\$

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.

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

16 Answers 16

5
\$\begingroup\$

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<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\$.

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

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.

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

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!

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

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.
\$\endgroup\$
3
\$\begingroup\$

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!

\$\endgroup\$
4
  • 1
    \$\begingroup\$ 95 bytes \$\endgroup\$
    – Arnauld
    Feb 9 at 18:12
  • \$\begingroup\$ @Arnauld, shaved off another two bytes by reverting the ternary order; also thanks for the variable name changes much easier to understand now \$\endgroup\$ Feb 9 at 18:42
  • 1
    \$\begingroup\$ 92 bytes \$\endgroup\$
    – att
    Feb 9 at 19:22
  • 1
    \$\begingroup\$ 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 \$\endgroup\$ Feb 11 at 20:54
3
\$\begingroup\$

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.

\$\endgroup\$
13
  • \$\begingroup\$ 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. \$\endgroup\$
    – Simd
    Feb 9 at 14:12
  • 1
    \$\begingroup\$ sorted(a)[::-1] is no longer linear time. \$\endgroup\$
    – Simd
    Feb 9 at 14:19
  • 1
    \$\begingroup\$ use x>h[1] to save a byte \$\endgroup\$
    – movatica
    Feb 11 at 19:44
  • 2
    \$\begingroup\$ 71 bytes by saving newlines: def f(a):h=nlargest(2,a);return[h[x>h[1]]for x in a] \$\endgroup\$
    – movatica
    Feb 11 at 19:48
  • 1
    \$\begingroup\$ @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. \$\endgroup\$
    – Stef
    Feb 11 at 20:16
2
\$\begingroup\$

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

\$\endgroup\$
2
  • 1
    \$\begingroup\$ @Arnauld Two maps are both called once, max is called twice \$\endgroup\$
    – l4m2
    Feb 9 at 13:48
  • \$\begingroup\$ Ah yes. I can see now how ++n prevents the inner map from being called more than once. \$\endgroup\$
    – Arnauld
    Feb 9 at 13:53
2
\$\begingroup\$

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.

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

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.

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

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.

J, 16 bytes

(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!

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)
\$\endgroup\$
1
  • \$\begingroup\$ Nice, (]{~[=0{])(2$,\:,)/ for 19. \$\endgroup\$
    – Jonah
    Feb 13 at 2:39
2
\$\begingroup\$

Scala 3, 109 94 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)
  }
}
\$\endgroup\$
2
  • \$\begingroup\$ The challenge states, that the input always has size >= 2, so you can remove if(a.size<=1)a; \$\endgroup\$
    – movatica
    Mar 3 at 18:49
  • \$\begingroup\$ Observation: x <= m, so (x != m) => (x < m). This saves 2 more bytes \$\endgroup\$
    – movatica
    Mar 4 at 17:42
1
\$\begingroup\$

Charcoal, 26 bytes

≔⌈θη≔⌕θηζ≔⌈Φθ⁻κζζIEθ⎇⁼ιηζη

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.

IEθ⎇⁼ιηζη

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:

IEθ⌈Φθ⁻μκ

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.

\$\endgroup\$
5
  • \$\begingroup\$ Does your golfed answer run in linear time? It looks like it should from the description. \$\endgroup\$
    – Simd
    Feb 10 at 7:25
  • \$\begingroup\$ @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. \$\endgroup\$
    – Neil
    Feb 10 at 7:51
  • \$\begingroup\$ @Simd ... or if I actually golfed it correctly, it would just be O(n²)... \$\endgroup\$
    – Neil
    Feb 10 at 7:55
  • \$\begingroup\$ The challenge does require linear time. \$\endgroup\$
    – Simd
    Feb 10 at 8:02
  • 2
    \$\begingroup\$ @Simd Yes there's a linear time answer and a golfed answer. \$\endgroup\$
    – Neil
    Feb 10 at 8:05
1
\$\begingroup\$

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 
\$\endgroup\$
5
  • \$\begingroup\$ How does it work? \$\endgroup\$
    – Simd
    Feb 9 at 17:40
  • \$\begingroup\$ @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 \$\endgroup\$
    – Rosario
    Feb 9 at 17:46
  • \$\begingroup\$ What is the algorithm it is using? \$\endgroup\$
    – Simd
    Feb 9 at 17:48
  • \$\begingroup\$ 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 \$\endgroup\$
    – Rosario
    Feb 9 at 17:54
  • \$\begingroup\$ Now would be ok even if all emements are the same \$\endgroup\$
    – Rosario
    Feb 9 at 18:38
1
\$\begingroup\$

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!

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

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)

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

APL+WIN, 22 bytes

Prompts for vector. Index origin = 0

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

Try it online! Thanks to Dyalog Classic

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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