Hey folks! I’m working on this kata (https://www.codewars.com/kata/element-equals-its-index/train/javascript) and here is my attempt so far…
function indexEqualsValue(a) {
let currentLow = -1;
let helperFunction = (start, stop, currentLow, a) => {
if (start > stop) {
return currentLow;
}
let mid = Math.floor(start - ((start- stop) / 2));
if (a[mid] == mid) {
currentLow = mid;
helperFunction(start, mid-1, currentLow, a);
} else if (a[mid] > mid) {
helperFunction(start, mid-1, currentLow, a);
} else {
helperFunction(mid+1, stop, currentLow, a);
}
}
return helperFunction(0, a.length -1, currentLow, a);
}
I think that ultimately a recrusive function is going to yield the best runtime here but I need to get the function working first!
The helperFunction is included because the kata has one parameter passing in and I need to keep track of the start/stop and the lowest a[index] == a match… When I debug, for the arrays with an answer other than -1, my recursion has the currentLow set to the current index/value but when it completes the recursion, I always end up returning undefined after it goes through the base case. Thoughts?
Why wouldn’t you simply use the Array.filter()? If you assign to a new array the filtered results of your passed array ( Array.filter() will pass optional parameters: in addition to element, you can also pass index – simply return true if element === index ). Then, from that newly filtered array, simply return the value of the first member.
All told, two lines. And CRAZY efficient, as js itself is optimizing the filter().
Huh. Maybe not. I’ll have to investigate. My solution passes 1004, fails one, and that one with a “took too long” message.
[EDIT]: Well that’s interesting. Switching from using Array.filter() to a simple for loop reduced that time considerably. On test 1005, which allows 150ms, using Array.filter() took 3568ms, while a for loop took 311ms. Still not efficient enough, but WAY faster.
Ya, that was what I tried originally too but took too long. The best I was able to do was the for loop and have it stop at the first match. I even added a condition to check the 1000th element to see if it was > 1000 (implying that it would also being a - 1 result) to possibly shorten the search but it didn’t help much.
Recursion seems like the only option I have left but I can’t get the function to work…
I solved this with array.prototype.reduce(), but it took too long. I refactored the code into a simple for loop that wouldn’t waste iterationcycles, and it worked.
SPOILER ANSWER BELOW WITH COMMENTS.
function indexEqualsValue(a) {
let i = 0;
for (; i<a.length; i++){
if (i === a[i]){
break; //Once this condition is met, we can guarantee this i is smaller than any other i for which a[i] === i, so stop iterating.
}
}
return i === a.length ? -1 : i; // the loop above exits on two possible conditions: a match (the lowest) was found and it broke out, or it completed without finding a match, which means the test in the for loop failed, and i === a.length. Test the value of i, and return -1 or i accordingly.
}
Figured out why your recursive function is failing, fixed the error, blew the DOORS off the other algorithms I was trying. And I hate to say, be prepared to kick yourself…
When you call the recursive function, don’t forget to return its value. Every time you call it. It has to pass its value back, or it passes undefined (and yeah, the purists are gonna CRUCIFY me for that oversimplification). So, change each of your helperFunction(...) lines to return helperFunction(...)
1 Like
Passed in 149ms (max 150ms) 
The return was exactly what I was missing. Thank you sir!!
Looking at some of the other solutions, I’m surprised mine seems to be the only using recursion so going to dive into those solutions a bit to see what their logic ended up being…
1 Like
I’m doing the same. I think the recursion one works nicely. When I ran it, I was running 129ms, so I think the server varies some. 
The thing I enjoy about the katas is that you CAN review other people’s solutions, and compare what works and what doesn’t. I try to supplement time here in FCC with time there (and, of course, time IRL).
Whoops. I think I didn’t submit it correctly. You are correct about the complexity. Binary search on the arrays with 13K+ members is the optimal solution.
1 Like