Jump Game
Finding the Maximum Subarray Sum
The Maximum Subarray Problem is a classic algorithmic challenge that frequently appears in coding interviews and real-world applications. The goal is to identify the contiguous subarray within a given array of integers that has the largest sum.
This article provides a clear and efficient approach to solve the problem using Kadane’s Algorithm.
Problem Description
You are given an integer array, nums, where each element nums[i] represents the maximum jump length you can take from that index. Starting from index 0, your goal is to determine whether it is possible to reach the last index.
Example 1
Input: nums = [1,2,0,1,0]
Output: true
Explanation:
The subarray [4,-2,2,1,-1,4] has the largest sum 8.
Example 2
Input: nums = [1,2,1,0,1]
Output: false
Constraints:
- 1 <= nums.length <= 1000
- 0 <= nums[i] <= 1000
Solution Approach: Greedy Algorithm
The key to solving this problem lies in determining the farthest index you can reach at any given point. Using a greedy algorithm,
we can iteratively update the farthest reachable index and check if it eventually encompasses the last index.
Steps
Initialize the Farthest Reachable Index:
Start with farthest = 0.Iterate Through the Array:
For each index i:- If i is greater than farthest, it means you cannot progress further, so return false.
- Update farthest to the maximum of its current value and i + nums[i].
Check Final Reach:
If you finish the loop and farthest is greater than or equal to the last index, return true.
There are mainly Four approach to solve this problem –
- Recursion
- Dynamic Programming (Top-Down)
- Dynamic Programming (Bottom-Up)
- Greedy
1. Recursion
- Time complexity: O(n!)
- Space complexity: O(n)
Python
C++
Java
JavaScript
Python
class Solution:
def canJump(self, nums: List[int]) -> bool:
def dfs(i):
if i == len(nums) - 1:
return True
end = min(len(nums) - 1, i + nums[i])
for j in range(i + 1, end + 1):
if dfs(j):
return True
return False
return dfs(0)C++
class Solution {
public:
bool canJump(vector& nums) {
return dfs(nums, 0);
}
private:
bool dfs(vector& nums, int i) {
if (i == nums.size() - 1) {
return true;
}
int end = min((int)nums.size() - 1, i + nums[i]);
for (int j = i + 1; j <= end; ++j) {
if (dfs(nums, j)) {
return true;
}
}
return false;
}
}; Java
public class Solution {
public boolean canJump(int[] nums) {
return dfs(nums, 0);
}
private boolean dfs(int[] nums, int i) {
if (i == nums.length - 1) {
return true;
}
int end = Math.min(nums.length - 1, i + nums[i]);
for (int j = i + 1; j <= end; j++) {
if (dfs(nums, j)) {
return true;
}
}
return false;
}
}JavaScript
class Solution {
/**
* @param {string} num1
* @param {string} num2
* @return {string}
*/
multiply(num1, num2) {
if (num1 === "0" || num2 === "0") return "0";
if (num1.length < num2.length) {
return this.multiply(num2, num1);
}
let res = "";
let zero = 0;
for (let i = num2.length - 1; i >= 0; i--) {
const cur = this.mul(num1, num2[i], zero);
res = this.add(res, cur);
zero++;
}
return res;
}
/**
* @param {string} s
* @param {Character} d
* @param {number} zero
* @return {string}
*/
mul(s, d, zero) {
let i = s.length - 1;
let carry = 0;
const digit = Number(d);
let cur = "";
while (i >= 0 || carry) {
const n = i >= 0 ? Number(s[i]) : 0;
const prod = n * digit + carry;
cur = (prod % 10) + cur;
carry = Math.floor(prod / 10);
i--;
}
return cur + "0".repeat(zero);
}
/**
* @param {string} num1
* @param {string} num2
* @return {string}
*/
add(num1, num2) {
let i = num1.length - 1, j = num2.length - 1, carry = 0;
let res = "";
while (i >= 0 || j >= 0 || carry) {
const n1 = i >= 0 ? Number(num1[i]) : 0;
const n2 = j >= 0 ? Number(num2[j]) : 0;
const total = n1 + n2 + carry;
res = (total % 10) + res;
carry = Math.floor(total / 10);
i--;
j--;
}
return res;
}
}2. Dynamic Programming (Top-Down)
Time & Space Complexity
- Time complexity: O(n^2)
- Space complexity: O(n)
Where m is the length of the array queries and n is the length of the array intervals.
C++
Java
Python
JavaScript
C++
class Solution {
public:
bool canJump(vector& nums) {
unordered_map memo;
return dfs(nums, 0, memo);
}
private:
bool dfs(vector& nums, int i, unordered_map& memo) {
if (memo.count(i)) {
return memo[i];
}
if (i == nums.size() - 1) {
return true;
}
if (nums[i] == 0) {
return false;
}
int end = min((int)nums.size(), i + nums[i] + 1);
for (int j = i + 1; j < end; j++) {
if (dfs(nums, j, memo)) {
memo[i] = true;
return true;
}
}
memo[i] = false;
return false;
}
}; Java
public class Solution {
public boolean canJump(int[] nums) {
Map memo = new HashMap<>();
return dfs(nums, 0, memo);
}
private boolean dfs(int[] nums, int i, Map memo) {
if (memo.containsKey(i)) {
return memo.get(i);
}
if (i == nums.length - 1) {
return true;
}
if (nums[i] == 0) {
return false;
}
int end = Math.min(nums.length, i + nums[i] + 1);
for (int j = i + 1; j < end; j++) {
if (dfs(nums, j, memo)) {
memo.put(i, true);
return true;
}
}
memo.put(i, false);
return false;
}
}
Python
class Solution:
def canJump(self, nums: List[int]) -> bool:
memo = {}
def dfs(i):
if i in memo:
return memo[i]
if i == len(nums) - 1:
return True
if nums[i] == 0:
return False
end = min(len(nums), i + nums[i] + 1)
for j in range(i + 1, end):
if dfs(j):
memo[i] = True
return True
memo[i] = False
return False
return dfs(0)JavaScript
class Solution {
/**
* @param {number[]} nums
* @return {boolean}
*/
canJump(nums) {
const memo = new Map();
const dfs = (i) => {
if (memo.has(i)) {
return memo.get(i);
}
if (i == nums.length - 1) {
return true;
}
if (nums[i] === 0) {
return false;
}
const end = Math.min(nums.length - 1, i + nums[i]);
for (let j = i + 1; j <= end; j++) {
if (dfs(j)) {
memo.set(i, true);
return true;
}
}
memo.set(i, false);
return false;
}
return dfs(0);
}
}3. Dynamic Programming (Buttom-Up)
Time & Space Complexity
- Time complexity: O(n^2)
- Space complexity: O(n)
C++
Java
Python
JavaScript
C++
class Solution {
public:
bool canJump(vector& nums) {
int n = nums.size();
vector dp(n, false);
dp[n - 1] = true;
for (int i = n - 2; i >= 0; i--) {
int end = min((int)nums.size(), i + nums[i] + 1);
for (int j = i + 1; j < end; j++) {
if (dp[j]) {
dp[i] = true;
break;
}
}
}
return dp[0];
}
}; Java
public class Solution {
public boolean canJump(int[] nums) {
int n = nums.length;
boolean[] dp = new boolean[n];
dp[n - 1] = true;
for (int i = n - 2; i >= 0; i--) {
int end = Math.min(nums.length, i + nums[i] + 1);
for (int j = i + 1; j < end; j++) {
if (dp[j]) {
dp[i] = true;
break;
}
}
}
return dp[0];
}
}
Python
class Solution:
def canJump(self, nums: List[int]) -> bool:
n = len(nums)
dp = [False] * n
dp[-1] = True
for i in range(n - 2, -1, -1):
end = min(n, i + nums[i] + 1)
for j in range(i + 1, end):
if dp[j]:
dp[i] = True
break
return dp[0]JavaScript
class Solution {
/**
* @param {number[]} nums
* @return {boolean}
*/
canJump(nums) {
const n = nums.length;
const dp = new Array(n).fill(false);
dp[n - 1] = true;
for (let i = n - 2; i >= 0; i--) {
const end = Math.min(nums.length, i + nums[i] + 1);
for (let j = i + 1; j < end; j++) {
if (dp[j]) {
dp[i] = true;
break;
}
}
}
return dp[0];
}
}4. Greedy
Time & Space Complexity
- Time complexity: O(n^2)
- Space complexity: O(n)
Where m is the length of the array queries and n is the length of the array intervals.
C++
Java
Python
JavaScript
C++
class Solution {
public:
bool canJump(vector& nums) {
int goal = nums.size() - 1;
for (int i = nums.size() - 2; i >= 0; i--) {
if (i + nums[i] >= goal) {
goal = i;
}
}
return goal == 0;
}
}; Java
public class Solution {
public boolean canJump(int[] nums) {
int goal = nums.length - 1;
for (int i = nums.length - 2; i >= 0; i--) {
if (i + nums[i] >= goal) {
goal = i;
}
}
return goal == 0;
}
}
Python
class Solution:
def canJump(self, nums: List[int]) -> bool:
goal = len(nums) - 1
for i in range(len(nums) - 2, -1, -1):
if i + nums[i] >= goal:
goal = i
return goal == 0JavaScript
class Solution {
/**
* @param {number[]} nums
* @return {boolean}
*/
canJump(nums) {
let goal = nums.length - 1;
for (let i = nums.length - 2; i >= 0; i--) {
if (i + nums[i] >= goal) {
goal = i;
}
}
return goal === 0;
}
}
