Odd Even Jump

HardStackmonotonic stack

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

You play a jumping game on an integer array arr. From some start index you make jumps numbered 1, 2, 3, ..., and every jump goes strictly to the right. - On an **odd** jump from index i, go to the index j > i whose value is the **smallest** value with arr[j] >= arr[i]. If several indices share that value, pick the smallest such j. - On an **even** jump from index i, go to the index j > i whose value is the **largest** value with arr[j] <= arr[i], again preferring the smallest j on ties. - If no such j exists, you are stuck. A start index is *good* if you can reach the last index (possibly with zero jumps) by following these rules. Return the number of good start indices.

Examples

Input: arr = [10,13,12,14,15]
Output: 2
Index 3 jumps to 4, and index 4 is already at the end. Starts 0, 1 and 2 get stuck, so the answer is 2.
Input: arr = [2,3,1,1,4]
Output: 3
From index 1: odd jump to 4. From index 3: odd jump to 4. Index 4 counts too. From 0: 0 -> 1 (odd), then the even jump goes to 2 and the next odd jump goes to 3, but the even jump from 3 is stuck. Answer 3.
Input: arr = [5,1,3,4,2]
Output: 3
Starts 1, 2 and 4 reach the end.

Constraints

  • 1 <= arr.length <= 2 * 10^4
  • 0 <= arr[i] < 10^5

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More monotonic stack problems