Leetcode One Dimensional DP problems

Maximum Subarray

Problem Statement:

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

A subarray is a contiguous part of an array.

Solution:

Kadane's Algorithm:

Let's say we define maxSum(i) as the maximum sub-array sum for all sub-arrays ending at index i. This means that maxSum(i) = Math.max(subArraySum(0, i), subArraySum(1, i), ..., subArraySum(i, i)) where subArraySum(l, r) is the sum of the sub-array starting at index l and ending at index r.

Similarly, maxSum(i + 1) = Math.max(subArraySum(0, i + 1), subArraySum(1, i + 1), ..., subArraySum(i + 1, i + 1)). But since subArraySum(0, i + 1) = subArraySum(0, i) + nums[i + 1] we can write maxSum(i + 1) as Math.max(subArraySum(0, i) + nums[i + 1], subArraySum(1, i) + nums[i + 1], ..., nums[i + 1]).

Since Math.max(a + y, b + y, c + y) = Math.max(a, b, c) + y we can write maxSum(i + 1) as Math.max(Math.max(subArraySum(0, i), ..., subArraySum(i, i)) + nums[i + 1], 0 + nums[i + 1]). And since Math.max(subArraySum(0, i), ..., subArraySum(i, i)) = maxSum(i) we have our final recurrence relation as:

maxSum(i + 1) = Math.max(maxSum(i) + nums[i + 1], nums[i + 1]).

We can store this in a 1D array. Since we don't know at which index k our sub-array with maximum sum ends, we need to loop through all the indices and take max of all the maxSum(i) for all 0 <= i < nums.length

The above solution has O(N) time and space complexity. But we can cleverly get rid of the O(N) space and make its space complexity O(1).

Memory Optimiszation:

Since maxSum(i + 1) only depends on maxSum(i) we can keep a variable called prevMaxSum and have a global maxSum variable which will eventually store our answer. We initialise prevMaxSum and maxSum with nums[0]. Then we loop through all the elements from index 1 and calculate the currentSum as prevSum + nums[i]. We set maxSum as Math.max(maxSum, currentSum) and later assign prevMaxSum as currentSum.

The code for the above approach can be found here.

A greedy approach that leads to the same algorithm:

We want to find all the sub-arrays with positive sum and then find the maximum out of those sub-arrays. So, we keep a variable called sumSoFar and initialise it with nums[0]. When we are at the ith element, we check if sumSoFar < 0. If the sumSoFar is less than zero then there's no point in continuing that sub-array and we should start a new max sub-array candidate starting at index i. After updating the sumSoFar we check if the updated value of sumSoFar is the maximum we have seen so far or not and update our maxSum variable accordingly to update our answer.

This way, we will always have either:

• positive values of sumSoFar - corresponding to the sub-arrays with positive sum.
• or the least negative value out of nums array - if all elements of nums array were negative.

Jump Game

Problem Statement:

You are given an integer array nums. You are initially positioned at the array's first index, and each element in the array represents your maximum jump length at that position.

Return true if you can reach the last index, or false otherwise.

Solution:

Recursive Solution:

We can reach the last index from an index i if:

• we can reach the last index from (i + 1)th index or
• we can reach the last index from (i + 2)th index or ...
• we can reach the last index from (i + nums[i])th index

And we can get a nice recurrence relation as:

Copycopy code to clipboard
1canReachFrom(i) = canReachFrom(i + 1) || ... || canReachFrom(i + nums[i])

We can also see that while computing canReachFrom(i + 1) we might also end up computing canReachFrom(i + 2) which might also be needed for canReachFrom(i). So, we can also memoize the answers for each index so we don't end up doing duplicate work.

Recursively we can write the code as follows:

Copycopy code to clipboard
1const indexVsReachableMap = new Map<number, boolean>();
2
3function canReachFrom(currentIndex: number, nums: number[]): boolean {
4  if (indexVsReachableMap.has(currentIndex)) {
5    return indexVsReachableMap.get(currentIndex);
6  }
7
8  if (currentIndex >= nums.length - 1) return true;
9
10  let answer = false;
11  for (let offset = 1; offset <= nums[currentIndex]; offset++) {
12    const nextIndex = currentIndex + offset;
13    const isReachable = canReachFrom(nextIndex, nums);
14    if (isReachable) {
15      answer = true;
16      break;
17    }
18  }
19
20  indexVsReachableMap.set(currentIndex, answer);
21
22  return answer;
23}

The happy case will be if nums[i] >= (n - 1 - i) for every 0 <= i < n - 1. In this case, we will end up having only one branch of depth n. canReachFrom(0) will call canReachFrom(1) which will call canReachFrom(2) and it will go on till canReachFrom(n - 2) and we would have returned true since everything was reachable.

The worst case scenario will occurr when canReachFrom(n - 2) is false and nums[i] === (n - 2) - i meaning it is possible to reach (n - 2)th index from every idnex. In that case, from the bottom of the recursion callstack, we will have:

• canReachFrom(n - 3) which checks for canReachFrom(n - 2) and returns false
• canReachFrom(n - 4) which checks for canReachFrom(n - 3) and canReachFrom(n - 2) and returns false.
• canReachFrom(n - 5) which checks for canReachFrom(n - 4), canReachFrom(n - 3) and canReachFrom(n - 2) and returns false. ...
• canReachFrom(0) which checks for canReachFrom(1), canReachFrom(2), ..., canReachFrom(n - 2) and returns false

In the above case since we are going through all the elements at most n times and hence the time complexity is O(n ^ 2).

Iterative Solution:

Let's say we tried to write an iterative solution for the above recursive solution. We will keep an isReachableFrom array where isReachableFrom[i] indicates if it is possible to reach the last index from index i.

Copycopy code to clipboard
1isReachableFrom[i] = isReachableFrom[i + 1] || ... || isReachableFrom[i + nums[i]]

From above recurrence relation, we know that isReachableFrom[i] depends on the values of nums[i] and isReachableFrom[j] where i < j <= i + nums[i]. Hence, we will start filling this array backwards.

The code for the above approach can be found here.

Greedy Solution:

Since we are only interested in finding out if we can reach the last index or not, we can use a greedy solution. We start off with keeping a maxReach variable which any given index i during the iteration, indicates the maximum reachable index from all of the indices in the range [0, i]. So at the beginning we initialise it with 0 since the reach is zero before starting our iteration. Then we loop through all indices from 0 to (n - 2) and if a particular index i is reachable i.e., i <= maxReach, we update the maxReach by Math.max(maxReach, i + nums[i]). At last, we return true if maxReach >= n - 1 else false.

Proof of correctness:

We prove the correctness by invariant.

Before entering the loop, we have set our maxReach variable to 0. If there is only one element in the array, the last index is 0 and it is reachable. Setting maxReach to 0 satisfies that edge case.

Inside the loop, for given index i, maxReach indicates the largest reachable index from all the indices in the range [0, i - 1]. If the current index i is not reachable from the previous [0, (i - 1)] indices then i > maxReach and we cannot reach till the last index. So we break the loop and return false. Otherwise if i <= maxReach then our new maxReach is max of i + nums[i] or the previous maxReach.

If the loop terminates successfully then it means that we completed the last iteration for (n - 2)th index successfully and we know for sure that n - 2 is not greater than maxReach. Hence we know for sure that maxReach >= n - 2 and we eventually just need to check if maxReach >= n - 1 and return true if that's the case.

Climbing Stairs:

Problem Statement:

You are climbing a staircase. It takes n steps to reach the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Solution:

Let's say countSteps(i) denotes the number of ways we can climb to the ith step. We can climb to the ith step by taking 1 step after reaching (i - 1)th step or by taking 2 steps after reaching (i - 2)th step. If we know number of distinct ways of reaching (i - 1)th step and (i - 2)th step then continuing the path by adding 1 and 2 steps respectively in those paths should give us the number of distinct ways of reaching the ith step. This holds true because there won't be any path common between (i - 1)th and (i - 2)th step and a union of those paths with 1 and 2 appended respectively will give us distinct paths as well.

So basically, our recurrence relation boils down to countSteps(i) = countSteps(i - 1) + countSteps(i - 2) with following base conditions:

• countSteps(0) = 1 since there's only one way to climb level 0 and that consists of climbing no steps (if we were to enumerate steps sequence, it would be: [[]]).
• countSteps(1) = 1 since there's only one way to climb to level 1 and that consists of climbing 1 step (steps sequence: [[1]]).

The code for this approach can be found here.

Longest Increasing Subsequence (LIS)

Problem Statement:

Given an integer array nums, return the length of the longest strictly increasing subsequence (LIS).

A subsequence is a sequence that can be derived from an array by deleting some or no elements without changing the order of the remaining elements. For example, [3,6,2,7] is a subsequence of the array [0,3,1,6,2,2,7].

Initial Thoughts:

Dynamic Programming:

Suppose, we are at index i and we want to know the length of LIS ending at index i - lisLength(i). What do we mean by length of LIS ending at index i - it means that we want to find all the sub-sequences that will have nums[i] as their last element and we want to take the one which has maximum length.

To get the maximum length, we need to find an index j where 0<= j < i such that lisLength(j) is maximum. But lisLength(i) is not as simple as lisLength(j) + 1. nums[j] has to be smaller than nums[i], otherwise if we add nums[i] in the LIS ending at index j then LIS property will not be preserved.

So, our task is to find out of all indices j where 0<= j < i and nums[j] < nums[i] which one has maximum lisLength(j). If no such index is found then our answer for lisLength(i) is simply 1 as we cannot form any sub-sequence other than the trivial [nums[i]] that ends with nums[i].

Ultimately, our task is to find max(lisLength(i)) for all i such that 0 <= i < nums.length.

One may wonder why are we taking max(lisLength(i)) and the answer to that is lisLength(i) only says what is the length of LIS that contains nums[i]. It is very well possible that the actual LIS doesn't have nums[i] and it ends on some other index.

One may also wonder then why did we not define our sub-problem as lisLength(i) - length of LIS till index i. Had we defined our sub-problem that way then we would have just need to calculate lisLength(nums.length - 1), but with that notation we wouldn't have been able to relate lisLength(i) with any of the other lisLength(j). This is because we wouldn't know which element was the last element in lisLength(j) and whether it is possible to extend that sub-sequence or not. We can only build up on the sub-problem if we exactly know where the previous sub-sequence ended.

The code for the above approach can be found here.