Given an array, for each jump (odd or even) you can jump to next element as follows:

• for odd jump, jump ahead to the smallest element greater than or equal to current element
• for even jump, jump ahead to the largest element smaller than or equal to current element

For each element, find if its possible to jump to last element.

Here, odd or even is decided by jump number and not index from which jump takes place and array can contain duplicates.

e.g.

arr = [4, 3, 5, 1, 2]

for 4: 4->5->2 (Jump 1 (odd) 4 to 5, Jump 2 (even) 5 to 2)) - true
for 3: 3->5->2 (Jump 1 (odd) 3 to 5, Jump 2 (even) 5 to 2)) - true
for 5: 5->not possible - false
for 1: 1->2 (Jump 1 (odd) 1 to 2) - true
for 2: true always - true

outputArr = [true, true, false, true, true]

arr = [4, 7, 5, 1, 2]

for 4: 4->5->2 (Jump 1 (odd) 4 to 5, Jump 2 (even) 5 to 2)) - true
for 7: 7-> not possible - false
for 5: 5->not possible - false
for 1: 1->2 (Jump 1 (odd) 1 to 2) - true
for 2: true always - true

outputArr = [true, false, false, true, true]

arr = [4, 7, 6, 1, 2]

for 4: 4->6->2 (Jump 1 (odd) 4 to 6, Jump 2 (even) 6 to 2)) - true
for 7: 7-> not possible - false
for 6: 6->not possible - false
for 1: 1->2 (Jump 1 (odd) 1 to 2) - true
for 2: true always - true

outputArr = [true, false, false, true, true]

I gave an O(n^2) solution with memoization but the interviewer said that it could've been done better.