How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at SoFi.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at SoFi during technical interviews.

Determine reachability and minimum jumps

Quick Overview

This interview question evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer for Determine reachability and minimum jumps states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.

Determine reachability and minimum jumps

Company: SoFi

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Technical Screen

Given an array of non-negative integers nums of length n, where nums[i] is the maximum number of steps you can move forward from index i: ( 1) Determine whether you can reach index n-1 starting from index 0. ( 2) If reachable, compute the minimum number of jumps required to reach index n-1. Aim for an O(n) time, O( 1) extra space solution if possible. Explain the algorithm, prove its correctness, analyze time/space complexity, and discuss edge cases (e.g., zeros that block progress, n=1, very large jump values, and cases where the last index is unreachable).

Quick Answer: This interview question evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer for Determine reachability and minimum jumps states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.

Jump Game: Reachability

Given an array of non-negative integers `nums` of length `n`, where `nums[i]` is the maximum number of steps you can move forward from index `i`, determine whether you can reach the last index `n-1` starting from index `0`. Return `true` if reachable, `false` otherwise. Aim for an O(n) time, O(1) extra space solution. **Approach (greedy):** Track the farthest index reachable so far. Scan left to right; at each index `i`, if `i` is already beyond the farthest reachable index, you are stuck and can never reach the end, so return `false`. Otherwise update `farthest = max(farthest, i + nums[i])`. If `farthest` ever reaches or passes `n-1`, return `true`. By convention an array of length 0 or 1 is trivially reachable (you are already at the last index). **Correctness:** Every index up to `farthest` is reachable (induction: index 0 is reachable; if index `i <= farthest` is reachable then so is every index in `[i, i+nums[i]]`). If the scan never gets stranded (`i > farthest`), the union of these intervals covers `[0, farthest]`, and once `farthest >= n-1` the last index lies in a covered interval. Conversely, getting stranded means a hard gap of zeros blocks all paths.

Constraints

1 <= n <= 10^4 (problem also defines the empty array as trivially reachable)
0 <= nums[i] <= 10^5
All values are non-negative integers

Examples

Input: ([2, 3, 1, 1, 4],)

Expected Output: True

Explanation: From index 0 (value 2) jump to index 1, which can reach index 4. Reachable.

Input: ([3, 2, 1, 0, 4],)

Expected Output: False

Explanation: The best you can do lands on index 3 (value 0), which blocks all progress; index 4 is unreachable.

Input: ([0],)

Expected Output: True

Explanation: n == 1: you start already on the last index, so it is trivially reachable even though nums[0] == 0.

Input: ([],)

Expected Output: True

Explanation: Empty array edge case: defined as trivially reachable (no last index to fall short of).

Input: ([1, 0, 1],)

Expected Output: False

Explanation: Index 0 reaches only index 1 (value 0), which is a dead end before index 2.

Input: ([2, 0, 0],)

Expected Output: True

Explanation: Index 0 (value 2) jumps straight over the zeros to the last index.

Input: ([5, 0, 0, 0, 0, 0],)

Expected Output: True

Explanation: A single very large jump from index 0 clears all trailing zeros to reach index 5.

Input: ([0, 1, 2],)

Expected Output: False

Explanation: Index 0 has value 0, so you are stranded at the start and cannot move at all.

Hints

You do not need to track every path. Track a single number: the farthest index reachable so far.
Scan left to right. If the current index i ever exceeds the farthest reachable index, you are stranded behind a wall of zeros and can never reach the end.
At each index update farthest = max(farthest, i + nums[i]); as soon as farthest >= n-1 you can stop early and return true.
Edge cases: n == 1 (already at the last index, return true) and a leading or interior run of zeros that the farthest reach cannot clear.

Jump Game II: Minimum Jumps

Given an array of non-negative integers `nums` of length `n`, where `nums[i]` is the maximum number of steps you can move forward from index `i`, compute the minimum number of jumps required to reach the last index `n-1` starting from index `0`. If the last index is unreachable, return `-1`. Aim for an O(n) time, O(1) extra space solution. **Approach (greedy / BFS-by-levels):** Treat the array as a layered BFS. Maintain `cur_end` (the farthest index reachable using the jumps taken so far) and `farthest` (the farthest index reachable using one more jump from anywhere in the current layer). Scan `i` from `0` to `n-2`. If `i` ever exceeds `farthest`, the end is unreachable, return `-1`. Update `farthest = max(farthest, i + nums[i])`. When `i == cur_end`, the current jump 'layer' is exhausted, so increment the jump count and advance `cur_end = farthest`; if `cur_end >= n-1` you can return the count immediately. **Correctness:** Each jump-count increment corresponds to expanding to the next BFS frontier, which by definition is the minimal number of jumps (BFS finds shortest paths in an unweighted reachability graph). We never overcount because we only increment when we are forced to leave the current frontier. By convention an array of length 0 or 1 needs 0 jumps.

Constraints

1 <= n <= 10^4 (problem also defines the empty array as needing 0 jumps)
0 <= nums[i] <= 10^5
All values are non-negative integers; return -1 when the last index cannot be reached

Examples

Input: ([2, 3, 1, 1, 4],)

Expected Output: 2

Explanation: Jump 0->1 (value 3), then 1->4. Two jumps is minimal.

Input: ([2, 3, 0, 1, 4],)

Expected Output: 2

Explanation: Jump 0->1, then 1->4, skipping the zero at index 2. Two jumps.

Input: ([0],)

Expected Output: 0

Explanation: n == 1: already at the last index, so zero jumps are needed.

Input: ([],)

Expected Output: 0

Explanation: Empty array edge case: defined as needing 0 jumps.

Input: ([3, 2, 1, 0, 4],)

Expected Output: -1

Explanation: The zero at index 3 blocks progress; index 4 is unreachable, so return -1.

Input: ([1, 1, 1, 1, 1],)

Expected Output: 4

Explanation: Every value is 1, forcing one jump per step: 0->1->2->3->4, four jumps.

Input: ([5, 0, 0, 0, 0, 0],)

Expected Output: 1

Explanation: A single large jump from index 0 reaches the last index directly.

Input: ([1, 2, 3],)

Expected Output: 2

Explanation: 0->1 (value 2 lets you overshoot but the end is index 2), then 1->2. Two jumps.

Input: ([2, 0, 0],)

Expected Output: 1

Explanation: Index 0 (value 2) jumps straight to the last index in one move.

Input: ([1, 0, 1],)

Expected Output: -1

Explanation: Index 1 has value 0, a dead end before index 2; unreachable, return -1.

Hints

Think of it as BFS in layers: every index reachable in k jumps forms one layer.
Track cur_end (farthest reachable with the jumps taken so far) and farthest (farthest reachable with one more jump from the current layer).
Only increment the jump count when i reaches cur_end — that is the moment you are forced to spend another jump to advance the frontier.
Guard against unreachable inputs: if i ever exceeds farthest you are stranded, return -1. Also handle n == 1 (0 jumps) up front.

Quick Overview

Determine reachability and minimum jumps

Company: SoFi

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Technical Screen

Jump Game: Reachability

Constraints

1 <= n <= 10^4 (problem also defines the empty array as trivially reachable)
0 <= nums[i] <= 10^5
All values are non-negative integers

Examples

Input: ([2, 3, 1, 1, 4],)

Expected Output: True

Explanation: From index 0 (value 2) jump to index 1, which can reach index 4. Reachable.

Input: ([3, 2, 1, 0, 4],)

Expected Output: False

Explanation: The best you can do lands on index 3 (value 0), which blocks all progress; index 4 is unreachable.

Input: ([0],)

Expected Output: True

Explanation: n == 1: you start already on the last index, so it is trivially reachable even though nums[0] == 0.

Input: ([],)

Expected Output: True

Explanation: Empty array edge case: defined as trivially reachable (no last index to fall short of).

Input: ([1, 0, 1],)

Expected Output: False

Explanation: Index 0 reaches only index 1 (value 0), which is a dead end before index 2.

Input: ([2, 0, 0],)

Expected Output: True

Explanation: Index 0 (value 2) jumps straight over the zeros to the last index.

Input: ([5, 0, 0, 0, 0, 0],)

Expected Output: True

Explanation: A single very large jump from index 0 clears all trailing zeros to reach index 5.

Input: ([0, 1, 2],)

Expected Output: False

Explanation: Index 0 has value 0, so you are stranded at the start and cannot move at all.

Hints

You do not need to track every path. Track a single number: the farthest index reachable so far.
Scan left to right. If the current index i ever exceeds the farthest reachable index, you are stranded behind a wall of zeros and can never reach the end.
At each index update farthest = max(farthest, i + nums[i]); as soon as farthest >= n-1 you can stop early and return true.
Edge cases: n == 1 (already at the last index, return true) and a leading or interior run of zeros that the farthest reach cannot clear.

Jump Game II: Minimum Jumps

Constraints

1 <= n <= 10^4 (problem also defines the empty array as needing 0 jumps)
0 <= nums[i] <= 10^5
All values are non-negative integers; return -1 when the last index cannot be reached

Examples

Input: ([2, 3, 1, 1, 4],)

Expected Output: 2

Explanation: Jump 0->1 (value 3), then 1->4. Two jumps is minimal.

Input: ([2, 3, 0, 1, 4],)

Expected Output: 2

Explanation: Jump 0->1, then 1->4, skipping the zero at index 2. Two jumps.

Input: ([0],)

Expected Output: 0

Explanation: n == 1: already at the last index, so zero jumps are needed.

Input: ([],)

Expected Output: 0

Explanation: Empty array edge case: defined as needing 0 jumps.

Input: ([3, 2, 1, 0, 4],)

Expected Output: -1

Explanation: The zero at index 3 blocks progress; index 4 is unreachable, so return -1.

Input: ([1, 1, 1, 1, 1],)

Expected Output: 4

Explanation: Every value is 1, forcing one jump per step: 0->1->2->3->4, four jumps.

Input: ([5, 0, 0, 0, 0, 0],)

Expected Output: 1

Explanation: A single large jump from index 0 reaches the last index directly.

Input: ([1, 2, 3],)

Expected Output: 2

Explanation: 0->1 (value 2 lets you overshoot but the end is index 2), then 1->2. Two jumps.

Input: ([2, 0, 0],)

Expected Output: 1

Explanation: Index 0 (value 2) jumps straight to the last index in one move.

Input: ([1, 0, 1],)

Expected Output: -1

Explanation: Index 1 has value 0, a dead end before index 2; unreachable, return -1.

Hints

Think of it as BFS in layers: every index reachable in k jumps forms one layer.
Track cur_end (farthest reachable with the jumps taken so far) and farthest (farthest reachable with one more jump from the current layer).
Only increment the jump count when i reaches cur_end — that is the moment you are forced to spend another jump to advance the frontier.
Guard against unreachable inputs: if i ever exceeds farthest you are stranded, return -1. Also handle n == 1 (0 jumps) up front.