Off-by-one on range boundaries
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.
Break down a hard problem into reliable checkpoints, edge-case handling, and complexity trade-offs.
Given an array of integers arr, you are initially positioned at the first index of the array.
In one step you can jump from index i to index:
i + 1 where: i + 1 < arr.length.i - 1 where: i - 1 >= 0.j where: arr[i] == arr[j] and i != j.Return the minimum number of steps to reach the last index of the array.
Notice that you can not jump outside of the array at any time.
Example 1:
Input: arr = [100,-23,-23,404,100,23,23,23,3,404] Output: 3 Explanation: You need three jumps from index 0 --> 4 --> 3 --> 9. Note that index 9 is the last index of the array.
Example 2:
Input: arr = [7] Output: 0 Explanation: Start index is the last index. You do not need to jump.
Example 3:
Input: arr = [7,6,9,6,9,6,9,7] Output: 1 Explanation: You can jump directly from index 0 to index 7 which is last index of the array.
Constraints:
1 <= arr.length <= 5 * 104-108 <= arr[i] <= 108Problem summary: Given an array of integers arr, you are initially positioned at the first index of the array. In one step you can jump from index i to index: i + 1 where: i + 1 < arr.length. i - 1 where: i - 1 >= 0. j where: arr[i] == arr[j] and i != j. Return the minimum number of steps to reach the last index of the array. Notice that you can not jump outside of the array at any time.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Array · Hash Map
[100,-23,-23,404,100,23,23,23,3,404]
[7]
[7,6,9,6,9,6,9,7]
jump-game-vii)jump-game-viii)maximum-number-of-jumps-to-reach-the-last-index)Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #1345: Jump Game IV
class Solution {
public int minJumps(int[] arr) {
Map<Integer, List<Integer>> g = new HashMap<>();
int n = arr.length;
for (int i = 0; i < n; i++) {
g.computeIfAbsent(arr[i], k -> new ArrayList<>()).add(i);
}
boolean[] vis = new boolean[n];
Deque<Integer> q = new ArrayDeque<>();
q.offer(0);
vis[0] = true;
for (int ans = 0;; ++ans) {
for (int k = q.size(); k > 0; --k) {
int i = q.poll();
if (i == n - 1) {
return ans;
}
for (int j : g.get(arr[i])) {
if (!vis[j]) {
vis[j] = true;
q.offer(j);
}
}
g.get(arr[i]).clear();
for (int j : new int[] {i - 1, i + 1}) {
if (0 <= j && j < n && !vis[j]) {
vis[j] = true;
q.offer(j);
}
}
}
}
}
}
// Accepted solution for LeetCode #1345: Jump Game IV
func minJumps(arr []int) int {
g := map[int][]int{}
for i, x := range arr {
g[x] = append(g[x], i)
}
n := len(arr)
q := []int{0}
vis := make([]bool, n)
vis[0] = true
for ans := 0; ; ans++ {
for k := len(q); k > 0; k-- {
i := q[0]
q = q[1:]
if i == n-1 {
return ans
}
for _, j := range g[arr[i]] {
if !vis[j] {
vis[j] = true
q = append(q, j)
}
}
g[arr[i]] = nil
for _, j := range []int{i - 1, i + 1} {
if 0 <= j && j < n && !vis[j] {
vis[j] = true
q = append(q, j)
}
}
}
}
}
# Accepted solution for LeetCode #1345: Jump Game IV
class Solution:
def minJumps(self, arr: List[int]) -> int:
g = defaultdict(list)
for i, x in enumerate(arr):
g[x].append(i)
q = deque([0])
vis = {0}
ans = 0
while 1:
for _ in range(len(q)):
i = q.popleft()
if i == len(arr) - 1:
return ans
for j in (i + 1, i - 1, *g.pop(arr[i], [])):
if 0 <= j < len(arr) and j not in vis:
q.append(j)
vis.add(j)
ans += 1
// Accepted solution for LeetCode #1345: Jump Game IV
use std::collections::{HashMap, VecDeque};
impl Solution {
// Time O(n) - Space O(n)
pub fn min_jumps(arr: Vec<i32>) -> i32 {
let n = arr.len();
// Handle a base case.
if n < 2 {
return 0;
}
// Use a dictionary of vertices indexed by value.
let mut d = HashMap::<i32, Vec<usize>>::new();
arr.iter()
.enumerate()
.for_each(|(i, num)| d.entry(*num).or_default().push(i));
// An array of flags of elements that we have processed already.
let mut seen = vec![false; n];
seen[0] = true;
// Use BFS to travel through the graph.
let mut steps = 0;
let mut queue = VecDeque::<usize>::from(vec![0]);
loop {
steps += 1;
// Process an entire level.
for _ in 0..queue.len() {
let cur = queue.pop_front().unwrap();
for nei in Self.get_unqueued_neighbors(cur, &n, &mut seen, &mut d, &arr) {
if nei == n - 1 {
return steps;
}
queue.push_back(nei);
}
}
}
}
// An internal function that computes the unvisited neighbors of a given node.
fn get_unqueued_neighbors(
self,
i: usize,
n: &usize,
seen: &mut Vec<bool>,
d: &mut HashMap<i32, Vec<usize>>,
arr: &Vec<i32>,
) -> Vec<usize> {
let mut adj = vec![];
// The element before is reachable.
if i > 0 && !seen[i - 1] {
seen[i - 1] = true;
adj.push(i - 1);
}
// The element after is also reachable.
if i < n - 1 && !seen[i + 1] {
seen[i + 1] = true;
adj.push(i + 1);
}
// And all nodes with the same value are also reachable.
if d.contains_key(&arr[i]) {
for node in d.entry(arr[i]).or_default() {
let node = *node;
if node != i {
adj.push(node);
seen[node] = true;
}
}
d.remove(&arr[i]);
}
adj
}
}
// Accepted solution for LeetCode #1345: Jump Game IV
function minJumps(arr: number[]): number {
const g: Map<number, number[]> = new Map();
const n = arr.length;
for (let i = 0; i < n; ++i) {
if (!g.has(arr[i])) {
g.set(arr[i], []);
}
g.get(arr[i])!.push(i);
}
let q: number[] = [0];
const vis: boolean[] = Array(n).fill(false);
vis[0] = true;
for (let ans = 0; ; ++ans) {
const nq: number[] = [];
for (const i of q) {
if (i === n - 1) {
return ans;
}
for (const j of g.get(arr[i])!) {
if (!vis[j]) {
vis[j] = true;
nq.push(j);
}
}
g.get(arr[i])!.length = 0;
for (const j of [i - 1, i + 1]) {
if (j >= 0 && j < n && !vis[j]) {
vis[j] = true;
nq.push(j);
}
}
}
q = nq;
}
}
Use this to step through a reusable interview workflow for this problem.
Two nested loops check every pair or subarray. The outer loop fixes a starting point, the inner loop extends or searches. For n elements this gives up to n²/2 operations. No extra space, but the quadratic time is prohibitive for large inputs.
Most array problems have an O(n²) brute force (nested loops) and an O(n) optimal (single pass with clever state tracking). The key is identifying what information to maintain as you scan: a running max, a prefix sum, a hash map of seen values, or two pointers.
Review these before coding to avoid predictable interview regressions.
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.
Wrong move: Zero-count keys stay in map and break distinct/count constraints.
Usually fails on: Window/map size checks are consistently off by one.
Fix: Delete keys when count reaches zero.