Problem overview
The function canJump receives an IntArray of hurdle heights, hurdleHeights, and the jumper's height, jumperHeight. It returns true if the jumper can clear every hurdle and false if any hurdle is too tall. A hurdle is cleared when the jump height is greater than or equal to the hurdle height, so a jump of 5 clears a hurdle of height 5.
Take hurdles [5, 5, 3, 4, 5] and a jump height of 3. The first hurdle has height 5, which is above 3, so the answer is false. With hurdles [1, 2, 3, 4, 5] and a jump height of 5, every hurdle is at most 5, so the answer is true. An empty array of hurdles also gives true: with nothing to jump over, any height is enough.
Approach: reject on the first hurdle that is too tall
This is the mirror image of searching an array for a value. The jumper clears the course only if every hurdle passes the test, and a single failure is enough to answer false. So the code looks for a counterexample:
- If some hurdle is taller than
jumperHeight, returnfalseimmediately. The other hurdles can't change that. - If the loop ends without finding such a hurdle, every hurdle passed, so return
true.
Be careful with the comparison. A hurdle exactly as tall as the jump height is cleared, so the test for failure is a strict "taller than", not "taller than or equal to".
Step by step
- Loop over the hurdles. Use a
forloop with a variable namedheightso each hurdle is inspected in order. The values are all that matter, so no index is needed. - Return
falsefor a hurdle that is too tall. Ifheightis greater thanjumperHeight, the answer is settled. Thereturnleaves the function, and the remaining hurdles are skipped. - Return
trueafter the loop. Getting there means no hurdle was too tall. It also covers the empty array, where the loop body never runs.
The solution in Kotlin
class Solution {
fun canJump(hurdleHeights: IntArray, jumperHeight: Int): Boolean {
for (height in hurdleHeights) {
if (height > jumperHeight) {
return false
}
}
return true
}
}
Kotlin notes:
- Return type and paths. The function is declared to return a
Boolean, so the compiler requires every path to end with a value. The finalreturn trueprovides it for the case where the loop finishes. - Looping directly over an array.
for (height in hurdleHeights)gives each element in order. The loop variable is read-only inside the body. - Comparison operators.
>works onIntvalues. Writing>=by mistake would reject a hurdle exactly as tall as the jump, which the task says is clearable. - A shorter form exists. Kotlin has a built-in
allfunction for arrays, which expresses "every element passes this test". The loop shows what it does underneath.
Complexity
Time: O(n), where n is the number of hurdles. In the worst case, when every hurdle can be cleared or only the last one is too tall, each hurdle is compared once. If the first hurdle is too tall, the function stops after one comparison.
Space: O(1). Only the loop variable is stored.
Edge cases and common mistakes
- Empty array. No hurdles means the loop is skipped and the function returns
true, as the task requires. - Hurdle equal to the jump height.
[1, 2, 1]with a jump of1returnsfalsebecause of the hurdle of height2. But[1, 1]with a jump of1returnstrue, since equal heights can be cleared. - Returning
trueinside the loop. Writingif (height <= jumperHeight) return truewould stop at the first clearable hurdle. For[1, 9]and a jump of3it would answertrueafter seeing the1, ignoring the9. - Checking only the first or last hurdle. The tallest hurdle can be anywhere. Every element must be examined unless a failure ends the search earlier.
- Negative values. They aren't expected, but the code handles them like any other number.
Testing
hurdleHeights = [1, 2, 3, 4, 5],jumperHeight = 5givestrue.hurdleHeights = [5, 5, 3, 4, 5],jumperHeight = 3givesfalse.hurdleHeights = [5, 4, 5, 6],jumperHeight = 10givestrue.hurdleHeights = [1, 2, 1],jumperHeight = 1givesfalse.hurdleHeights = [],jumperHeight = 1givestrue.