-2
\$\begingroup\$

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]
}
 
}

\$\endgroup\$
1
  • \$\begingroup\$ 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? \$\endgroup\$
    – greybeard
    Jun 11, 2020 at 22:38

1 Answer 1

2
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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