Leetcode 45: Jump Game II

1. Problem Statement (Simple Explanation):

You are given:

A 0-indexed array nums of length n.
You start at index 0.

Each nums[i] tells you the maximum forward jump length from index i:

From i, you can jump to any index i + j such that:

0 <= j <= nums[i]
i + j < n

You must return the minimum number of jumps needed to reach index n-1 (the last index).

You are guaranteed that this is always possible.

2. Examples:

Example 1:

Input: nums = [2,3,1,1,4]

One optimal strategy:

From index 0 (value 2), you can reach indices 1 or 2.
If you jump to index 1 (value 3), from there you can jump directly to index 4.

Total jumps: 2.

Output: 2

Example 2:

Input: nums = [2,3,0,1,4]

Again:

From index 0, jump to index 1.
From index 1, you can jump directly to index 4.

Total jumps: 2.

Output: 2

3. Intuition – Greedy "Level" / Interval Expansion:

Think of it like this:

You are expanding layers of reachable indices, similar to BFS levels in a graph, but you can do it in one pass with greedy.

Maintain:

jumps – number of jumps taken so far.
currentEnd – the furthest index you can reach with jumps jumps.
farthest – the furthest index you can reach with jumps + 1 jumps (while scanning within current range).

Idea:

Traverse from left to right (excluding last index):

For each index i:

Update farthest = max(farthest, i + nums[i]).
If you reach currentEnd:

You’ve just explored all indices reachable with the current jumps.
You now need one more jump:

jumps++
currentEnd = farthest

Once currentEnd reaches or passes the last index, you know the number of jumps.

This is analogous to:

currentEnd is the boundary of the current “layer” of BFS.
farthest is the maximum boundary for the next layer.

Example Walkthrough – [2,3,1,1,4]:

n = 5
Initialize:

jumps = 0
currentEnd = 0
farthest = 0

Iterate i from 0 to n - 2 (we don't need to process last index):

i = 0:

farthest = max(0, 0 + nums[0]=2) = 2
i == currentEnd (0):

jumps = 1
currentEnd = farthest = 2

i = 1:

farthest = max(2, 1 + nums[1]=3) = 4

i = 2:

farthest = max(4, 2 + nums[2]=1=3) = 4
i == currentEnd (2):

jumps = 2
currentEnd = farthest = 4 (which is last index)

Stop; answer = 2.

Pseudo-code (Greedy):

Complexity:

Let n = len(nums):

Time: O(n) – single pass.
Space: O(1) – constant extra storage.

4. Java code:

5. C code:

6. C++ code:

7. Python code:

8. JavaScript code:

Comments

Leetcode 1: Two Sum

Leetcode Link: https://leetcode.com/problems/two-sum/ 1. Problem Statement (Simple Explanation) You are given: An array of integers nums An integer target You need to return the indices of two numbers in the array such that: Conditions: Each input has exactly one solution . You cannot use the same element twice . You can return the answer in any order . 2. Examples Example 1 Input: nums = [2, 7, 11, 15], target = 9 Output: [0, 1] Explanation: nums[0]+nums[1]=2+7=9 So we return [0, 1]. Example 2 Input: ...

Leetcode 3: Longest Substring Without Repeating Characters

Leetcode Link 1. Problem Statement (Simple Explanation) You are given a string s. You need to find the length of the longest substring of s that does not contain any repeated characters. A substring is a contiguous sequence of characters in the string. You must return an integer length, not the substring itself. 2. Examples Example 1 Input: s = "abcabcbb" Output: 3 Explanation: Some substrings without repeating characters: "abc", "bca", "cab"The longest length is 3. Example 2 Input: s = "bbbbb" Output: 1 Explanation: All substrings that are valid are just "b". The longest length is 1. Example 3 Input: s = "pwwkew" Output: 3 Explanation: Possible substrings without repetition: "pw", "wke", "kew". "wke" or "kew" have length 3. "pwke" is not valid because it’s not contiguous in the original string (p and k are separated by ww). Constraints...

Leetcode 2: Add Two Numbers

Leetcode Link: https://leetcode.com/problems/add-two-numbers/ 1. Problem Statement (Simple Explanation) You are given two non-empty linked lists , l1 and l2, that represent two non-negative integers. Each node contains a single digit . The digits are stored in reverse order (i.e., the 1’s digit is at the head). You need to add the two numbers and return the sum as a linked list , also in reverse order. You can assume: There are no leading zeros , except when the number itself is 0. 2. Examples Example 1 Input: l1 = [2,4,3] l2 = [5,6,4] Interpreting linked lists as numbers (reverse order): l1 represents 342 l2 represents 465 Output: [7,0,8] Explanation: ...

codesprint with rishav

Search This Blog