# Find the first element that equals its index

Can anyone help me improve the performance of my code.

Given a sorted array of distinct integers, write a function indexEqualsValue that returns the lowest index for which array[index] == index. Return -1 if there is no such index.

function indexEqualsValue(a) {
var arr =[]

a.forEach((el, i) => {
if( el==i){
arr.push(el)
}
})
if(arr.length==0){
return -1
}else{
return arr[0]
}

}

• can any one help me execution code time, please? This is right where trouble starts: this sentence looks incorrect, and I can't confidently guess what is meant. Why collect values into an array to just return the first one? Jun 11, 2020 at 22:38

Assuming the input is sorted in ascending order, if a[i] > i then a[j] > j for any j >= i, because the numbers in the input are supposed to be distinct.

There is also no reason to aggregate all values that satisfy the criterion to eventualy only return the first one. Just return the first one when encountered.

function indexEqualsValue(input)
{
const limit = input.length
for (let i = 0; i < limit; ++i) {
if (input[i] === i) {
return i
}

if (input[i] > i) {
return -1
}
}

return -1
}

console.log(indexEqualsValue([0,1,2])) // 0
console.log(indexEqualsValue([1,2,3])) // -1
console.log(indexEqualsValue([-1,1,2])) // 1


A bit of complexity analysis:

Your solution is O(n) in time and O(k) in space, where n is size of input, and k is number of elements that satisfy the criterion a[i]==i, k <= n.

My solution is O(b) in time, and O(1) in space, where b is number of elements that satisfy a similar criterion: a[i] < i, in words, the number of elements that are less then their index, b <= n. If input does not contain negative numbers, it is O(1) in time (thats actually because in that case the result must be zero, or -1).

PS: Next time, please, take your time to write a good quality question. Succint algorithm definition without any additional information makes up for a very poor question. You're lucky I'm in mood.