Find index of the nearest larger number of a number

Given an array of numbers and an index i, return the index of the nearest larger number of the number at index i, where distance is measured in array indices.

For example, given [4, 1, 3, 5, 6] and index 0, you should return 3.

If two distances to larger numbers are the equal, then return any one of them. If the array at i doesn't have a nearest larger integer, then return null.

Follow-up: If you can preprocess the array, can you do this in constant time?

My solution:

const nearestLargestNumber = (arr, idx1) => {
const num = arr[idx1];
let nearestLargest;
const findIdxOfNearestLargest = (idxOfNearestLargest, item, idx2) => {
if (item > num &&
(idxOfNearestLargest === null || nearestLargest > item )) {
nearestLargest = item;
idxOfNearestLargest = idx2;
}
return idxOfNearestLargest;
};

return arr.reduce(findIdxOfNearestLargest, null);
};

console.log(nearestLargestNumber([4, 1, 3, 5, 6], 0));


You are iterating every item in the array a solution that is $$\O(n)\$$. The task is to find the "nearest larger". If the values are random and evenly distributed then the solution is $$\O(log(n))\$$ which is much better than $$\O(n)\$$

To get the best result start the search at the index and search outwards away from index. The first item larger than the starting item is at the index to return.

function findNearestLarger(arr, idx) {
const minVal = arr[idx], len = arr.length;
var down = idx;
while (++idx < len || --down >= 0) {
if (idx < len && arr[idx] > minVal) { return idx }
if (down >= 0 && arr[down] > minVal) { return down }
}
return null;
}

• I think your runtime estimate is too pessimistic. If the numbers are random, then half of them are larger than idx and each element inspected is a coinflip opportunity to return an answer. Amortized runtime will be $\sum_{i=1}^n \frac{i}{2^i}$ which converges to $2 - \frac{1}{2^n}$, giving $O(1)$. Mar 22, 2019 at 11:22

EDIT: I mistook "nearest" to mean "numerically closest" but the problem asks for minimum distance from the index. As the other answer points out, there are faster methods than visiting every element.

The answer to the followup question is "yes."

"Larger" is ambiguous: if you ask someone for a "large negative number" they probably don't answer "negative one." Attribute this to sloppiness on the author's part, unless you've reason to suspect trickery.

I'm not a fan of these variable names: idx1 should be idx0, or i0 or initialIndex. nearestLargest isn't the largest anything and nearestLarger would be more accurate. num is a number, but so is everything else—maybe minimum or baseline or mustBeGreaterThan. nearestLargestNumber contains an index, not a number, while the number is held in nearestLargest.

I suggest one common prefix for your index variables and another prefix for value variables (though you don't really need more than one).

const nearestGreater = (arr, i0) => arr.reduce(
(iNearestGreater, val, i) =>
( val > arr[i0] && ( iNearestGreater===null || val < arr[ iNearestGreater ] ) ) ?
i : iNearestGreater,
null
);


I ran your code and got the following results:

console.log(nearestLargestNumber([4, 1, 3, 5, 6], 0));
> 3
console.log(nearestLargestNumber([4, 1, 3, 5, 6], 1));
> 2
console.log(nearestLargestNumber([4, 1, 3, 5, 6], 2));
> 0
console.log(nearestLargestNumber([4, 1, 3, 5, 6], 3));
> 4
console.log(nearestLargestNumber([4, 1, 3, 5, 6], 4));
> null


I believe the result for index 2 is incorrect. At index 2 the number is 3 so the closest larger number is 5 at index 3. Why it returns index 0 I do not know.

My solution is:

let nearestLargerNumber = (array, index) => {

let indexNum = array[index];

// Get position of index.
let distToEnd = (array.length - 1) - index;

if(distToEnd > index){
// If index is in the left half.

for(let i = index + 1; i < (index + 1) * 2; i ++){
if(array[i] > indexNum){
return i;
}else if(array[index - (i - index)] > indexNum){
return index - (i - index);
}
}

// Check remaining elements at the end of the array.
for(; i < array.length; i ++){
if(array[i] > indexNum){
return i;
}
}

}else if(distToEnd < index){
// If index is in the right half.

for(let i = index + 1; i < array.length; i ++){
if(array[i] > indexNum){
return i;
}else if(array[index - (i - index)] > indexNum){
return index - (i - index);
}
}

// Check remaining elements at the beginning of the array
for(let i = index - ((array.length - 1) - index); i >= 0; i --){
if(array[i] > indexNum){
return i;
}
}

}else{
// If index is the exact middle (only if array has an odd length).

for(let i = index + 1; i < array.length; i ++){
if(array[i] > indexNum){
return i;
}else if(array[index - (i - index)] > indexNum){
return index - (i - index);
}
}
}

return null;
}


Given an array of numbers and an index i, return the index of the nearest larger number of the number at index i, where distance is measured in array indices.

I'm a bit confused to be honest. Reading this description, for input [1, 5, 4], 0 I would expect 1 as output instead of 2 returned by the program. Because arr[1] = 5 is larger than arr[0] = 1, and it's closer in distance than arr[2] = 4. Similarly, for input [4, 5, 1], 2 I would expect 1 instead of 0.

In other words, the program seems to be implementing a more precisely worded problem statement:

Given an array of numbers and an index i, return the index of the nearest smallest larger number of the number at index i, where distance is measured in array indices.

Follow-up: If you can preprocess the array, can you do this in constant time?

The posted code doesn't address the follow-up question.

I think this follow-up question is not specified well enough, because it doesn't impose any limits on the preprocessing time and space. You could certainly "preprocess" the array, using nearestLargestNumber to compute the answer for all valid indexes, store in another array. With the current implementation, computing a single answer takes linear time, therefore computing all answers up-front would take quadratic time. Since no limits were imposed, that may be fine and well.

This follow-up question would become a lot more interesting if preprocessing was limited to linear time and space.

Complexity: $$\O(\log n)\$$
It worked. It gave me correct answers for many testcases:

i/p:[1, 5, 4] ,0
o/p:1

i/p:[4, 1, 3, 5, 6] ,0
o/p:3

l=list(map(int,input().split()))
n=int(input())
p=n-1
q=n+1
while(p>=0 or q<len(l)):
if(p>=0 and l[p]>l[n]):
print(p)
break
elif(q<len(l) and l[q]>l[n]):
print(q)
break
p=p-1
q=q+1
if(p<0 and q>=len(l)):
print("null")

• Welcome to Code Review! Please Check out our Help center pages specifically the How to write a good answer page. we look for explanations of why you would use a specific technique or code structure.
– Malachi
Apr 29, 2021 at 18:50