Find the nearest greater number

Question

The task

Given any array of integers, e.g.:

[-1,476,578,27,0,1,-1,1,2]

and an index of that array (this example uses 0 based indexing, though you can use 1 based indexing as well.):

         index = 5
                 v
[-1,476,578,27,0,1,-1,1,2]

Then return the nearest number greater than the element at that index. In the example, the closest number greater than 1 is 27 (at 2 indices away).

         index = 5
                 v
[-1,476,578,27,0,1,-1,1,2]
            ^
Nearest greater number

Output = 27

Assumptions

• Nearest does not include wrapping.
• The program will never be given an array of length 1 (e.g; [55]).
• You are to assume there is always a number greater than the given element.
• If there are 2 numbers greater than the element at equal distances, you can return either one.

I/O pairs

Input:
Index = 45
Array = [69, 43, 89, 93, 62, 25, 4, 11, 115, 87, 174, 60, 84, 58, 28, 67, 71, 157, 47, 8, 33, 192, 187, 87, 175, 32, 135, 25, 137, 92, 183, 151, 147, 7, 133, 7, 41, 12, 96, 147, 9, 134, 197, 3, 107, 164, 90, 199, 21, 71, 77, 62, 190, 122, 33, 127, 185, 58, 92, 106, 26, 24, 56, 79, 71, 24, 24, 114, 17, 84, 121, 188, 6, 177, 114, 159, 159, 102, 50, 136, 47, 32, 1, 199, 74, 141, 125, 23, 118, 9, 12, 100, 94, 166, 12, 9, 179, 147, 149, 178, 90, 71, 141, 49, 74, 100, 199, 160, 120, 14, 195, 112, 176, 164, 68, 88, 108, 72, 124, 173, 155, 146, 193, 30, 2, 186, 102, 45, 147, 99, 178, 84, 83, 93, 153, 11, 171, 186, 157, 32, 90, 57, 181, 5, 157, 106, 20, 5, 194, 130, 100, 97, 3, 87, 116, 57, 125, 157, 190, 83, 148, 90, 44, 156, 167, 131, 100, 58, 139, 183, 53, 91, 151, 65, 121, 61, 40, 80, 40, 68, 73, 20, 135, 197, 124, 190, 108, 66, 21, 27, 147, 118, 192, 29, 193, 27, 155, 93, 33, 129]
Output = 199

Input:
Index = 2
Array = [4,-2,1,-3,5]
Output = 4 OR 5

Input:
Index = 0
Array = [2124, -173, -155, 146, 193, -30, 2, 186, 102, 4545]
Output = 4545

Input:
Index = 0
Array = [1,0,2,3]
Output = 2

Input:
Index = 2
Array = [3,-1,-3,-2,5]
Output = -1 OR -2

Answer 1

MATL, 10 bytes

yt&y)>fYk)

This uses 1-based indexing. Try it online!

Explanation

Consider inputs [4,-2,1,-3,5], 3 as an example.

y     % Take two inputs implicitly. Duplicate 2nd-top element in the stack
      % STACK: [4,-2,1,-3,5], 3, [4,-2,1,-3,5]
t     % Duplicate top of the stack
      % STACK: [4,-2,1,-3,5], 3, [4,-2,1,-3,5], [4,-2,1,-3,5]
&y    % Duplicate 3rd-top element in the stack
      % STACK: [4,-2,1,-3,5], 3, [4,-2,1,-3,5], [4,-2,1,-3,5], 3
)     % Index: select elements from first input as indicated by second input
      % STACK: [4,-2,1,-3,5], 3, [4,-2,1,-3,5], 1
>     % Greater than, element-wise
      % STACK: [4,-2,1,-3,5], 3, [1,0,0,0,1]
f     % Find: gives indices of non-zero entries
      % STACK: [4,-2,1,-3,5], 3, [1,5]
Yk    % Closest element: gives closest element of each entry in second input
      % ([1,5]) to each entry in the first input (3). In case of a tie it 
      % gives the left-most one
      % STACK: [4,-2,1,-3,5], 1
)     % Index: select elements from first input as indicated by second input
      % STACK: 4
      % Implicitly display

Answer 2

Jelly, 10 bytes

ị<ṛTạ⁸$ÞḢị

Try it online!

Answer 3

Jelly, 11 12 bytes

+1 byte - No wrapping allowed.

Jạż⁸ṢZṪ»\Q2ị

1-indexed.

Try it online!

---

Previous 11 byter (wrapping indexing), 0-indexed:

ṙżU$Fµ>ḢTḢị

Answer 4

JavaScript (ES6), 57 55 bytes

Takes the array a and the index i in currying syntax (a)(i).

a=>g=(i,p)=>(x=a[i-p])>a[i]||(x=a[i+p])>a[i]?x:g(i,-~p)

Test cases

let f =

a=>g=(i,p)=>(x=a[i-p])>a[i]||(x=a[i+p])>a[i]?x:g(i,-~p)

console.log(f([-1, 476, 578, 27, 0, 1, -1, 1, 2])(5))

console.log(f([69, 43, 89, 93, 62, 25, 4, 11, 115, 87, 174, 60, 84, 58, 28, 67, 71, 157, 47, 8, 33, 192, 187, 87, 175, 32, 135, 25, 137, 92, 183, 151, 147, 7, 133, 7, 41, 12, 96, 147, 9, 134, 197, 3, 107, 164, 90, 199, 21, 71, 77, 62, 190, 122, 33, 127, 185, 58, 92, 106, 26, 24, 56, 79, 71, 24, 24, 114, 17, 84, 121, 188, 6, 177, 114, 159, 159, 102, 50, 136, 47, 32, 1, 199, 74, 141, 125, 23, 118, 9, 12, 100, 94, 166, 12, 9, 179, 147, 149, 178, 90, 71, 141, 49, 74, 100, 199, 160, 120, 14, 195, 112, 176, 164, 68, 88, 108, 72, 124, 173, 155, 146, 193, 30, 2, 186, 102, 45, 147, 99, 178, 84, 83, 93, 153, 11, 171, 186, 157, 32, 90, 57, 181, 5, 157, 106, 20, 5, 194, 130, 100, 97, 3, 87, 116, 57, 125, 157, 190, 83, 148, 90, 44, 156, 167, 131, 100, 58, 139, 183, 53, 91, 151, 65, 121, 61, 40, 80, 40, 68, 73, 20, 135, 197, 124, 190, 108, 66, 21, 27, 147, 118, 192, 29, 193, 27, 155, 93, 33, 129])(45))

console.log(f([4, -2, 1, -3, 5])(2))

console.log(f([2124, -173, -155, 146, 193, -30, 2, 186, 102, 4545])(0))

Answer 5

PHP, 106 Bytes

<?for($y=($a=$_GET[0])[$x=$_GET[1]];$y>=$a[$x-++$i]&&$y>=$a[$x+$i];);echo$y<$a[$x+$i]?$a[$x+$i]:$a[$x-$i];

Online Version

Answer 6

Haskell, 48 bytes

i%l=minimum[[j*j,x]|(j,x)<-zip[-i..]l,x>l!!i]!!1

Try it online! Test framework from Ørjan Johansen.

Answer 7

x86-64 Assembly, 40 bytes

Inspired by analyzing Johan du Toit and 2501's C solutions, the following is a function that can be assembled with MASM for x86-64 platforms.

It follows the Microsoft x64 calling convention for passing parameters, so the total length of the array is passed in ECX, the position of interest is passed in EDX, and the pointer to the integer array is passed in R8 (it's a 64-bit platform, so it's a 64-bit pointer).

It returns the result (the "nearest greater number") in EAX.

             FindNearestGreater PROC      
8B F2       \    mov     esi, edx     ; move pos parameter to preferred register
8B D9       |    mov     ebx, ecx     ; make copy of count (ecx == i; ebx == count)
            | MainLoop:
8B C6       |    mov     eax, esi     ; temp  = pos
2B C1       |    sub     eax, ecx     ; temp -= i
99          |    cdq
33 C2       |    xor     eax, edx
2B C2       |    sub     eax, edx     ; temp = AbsValue(temp)
            | 
41 8B 14 B0 |    mov     edx, DWORD PTR [r8+rsi*4]
41 39 14 88 |    cmp     DWORD PTR [r8+rcx*4], edx
7E 04       |    jle     KeepGoing    ; jump if (pValues[i] <= pValues[pos])
3B D8       |    cmp     ebx, eax
77 02       |    ja      Next         ; jump if (count > temp)
            | KeepGoing:
8B C3       |     mov     eax, ebx    ; temp = count
            | Next:
8B D8       |     mov     ebx, eax    ; count = temp
E2 E3       |     loop    MainLoop    ; equivalent to dec ecx + jnz, but smaller (and slower)
            | 
            |     ; Return pValues[temp + pos]
03 C6       |     add     eax, esi
41 8B 04 80 |     mov     eax, DWORD PTR [r8+rax*4]
C3          /     ret
             FindNearestGreater ENDP

If you wanted to call it from C code, the prototype would be:

extern int FindNearestGreater(unsigned int count,
                              unsigned int pos,
                              const    int *pValues);

Answer 8

Ruby, 64 bytes

->a,i{a[(0...a.size).select{|j|a[j]>a[i]}.min_by{|j|(i-j).abs}]}

Try it online!

Answer 9

Ohm, 20 bytes

Basically a translation of this Ruby answer.

Dl#)░┼_ª┼┘ª>;╥┘_-A;ª

Try it online!

Explanation will come later when I'm not doing homework.

Answer 10

Pyth - 28 bytes

JEehf>@T1@JQo@NZm(adQ@Jd)UlJ

Try it

Answer 11

Haskell, 53 bytes

(#) takes an Int and a list of Ints or Integers (actually any Ord type), and returns an element of the list.

n#l=[x|i<-[1..],x:_<-(`drop`l)<$>[n-i,n+i],x>l!!n]!!0

How it works

• n is the given index and l is the given list/"array".
• i, taking on values from 1 upwards, is the distance from n currently being tested.
• For each i, we check indices n-i and n+i.
• x is the element of l being tested. If it passes the tests it will be an element of the resulting list comprehension.
  • Indexing arbitrary indices with !! could give an out of bounds error, while drop instead returns either the whole list or an empty list in that case. The pattern match with x:_ checks that the result is not empty.
  • x>l!!n tests that our element is greater than the element at index n (which is guaranteed to exist).
  • !!0 at the end returns the first match/element of the list comprehension.

Try it online!

Answer 12

Python, 62 bytes

lambda a,i:min((v<=a[i],abs(j-i),v)for j,v in enumerate(a))[2]

Try it online!

Answer 13

Brachylog, 17 bytes

hH&∋₎<.&t:I≜+:H∋₍

Try it online!

Explanation

hH                      Call the list H
  &∋₎<.                 Output is greater than the number at the specified index
       &t:I≜            Label I (0, then 1, then -1, then 2, then -2, …)
            +           Sum I with the input Index
             :H∋₍       Output is the element of H at index <the sum>

Answer 14

Java (OpenJDK 8), 98 bytes

int f(int n,int[]a){for(int s=1,i=1,x=a[n];;n+=i++*s,s=-s)if(0<=n&n<a.length&&a[n]>x)return a[n];}

Try it online!

Checks the indices in the order specified by the partial sums of the following sum:

initial value + 1 - 2 + 3 - 4 + 5 - 6 + ...

Answer 15

C, 69 bytes

t;b;f(*d,c,p){for(b=c;c--;)d[c]>d[p]&(t=abs(p-c))<b?b=t:0;*d=d[p+b];}

First argument is an in/out argument. Output is stored in its first element.

See it work online.

Answer 16

PHP, 73 bytes

function($i,$a){for(;$b<=$a[$i];)$b=max($a[++$d+$i],$a[$i-$d]);return$b;}

closure takes 0-based index and array from arguments. Verify all test cases.

Answer 17

R, 59 bytes

function(l,i)l[j<-l>l[i]][which.min(abs(1:length(l)-i)[j])]

returns an anonymous function. In the event that there are two elements greater at equal distances, will return the first (lesser index).

Try it online!

Answer 18

Pyth, 16 bytes

JEh>#@JQ@LJaDQUJ

Test suite.

Answer 19

C, 110 bytes

c,o;e(g,l,f)int*g;{for(o=g[l],c=1;c<f;c++)l+c<f&&g[l+c]>o?o=g[l+c],c=f:0,l-c>=0&&g[l-c]>o?o=g[l-c],c=f:0;g=o;}

Try it online

Answer 20

Java, 96 Bytes

int f(int n,int[]a){for(int s=1,i=1,x=a[n];0>(n+=i++*s)|n>=a.length||a[n]<=x;s=-s);return a[n];}

Identifiers are named like @Leaky Nun's answer. Furthermore, most parts have been aligned to be basically the same: In comparison, the if has been replaced by the for-condition (sacrificing the additional semicolon). A colon has been removed by moving increment-part into condition (so the parentheses of the previous if-statement practically "moved") - changing & to | did not have impact on character count.

Answer 21

Clojure, 95 bytes

#(%(nth(nth(sort-by first(for[i(range(count %)):when(>(% i)(% %2))][(Math/abs(- i %2))i]))0)1))

This is the shortest I could come up with :( I also tried playing around with this but couldn't bring it to the finish line:

#(map(fn[f c](f c))[reverse rest](split-at %2 %))