### Remove nth Node from Last - Leet Code Solution

Problem Statement Given a linked list, remove the n-th node from the end of list…

August 27, 2020

Say you have an array prices for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete as many transactions as you like (i.e., buy one and sell one share of the stock multiple times).

**Examples**

```
Input: [7,1,5,3,6,4]
Output: 7
Explanation:
- buy on day-2, sell on day-3. Profit (5-1) = 4
- buy on day-4, sell on day-5. Profit (6-3) = 3
```

Lets try a brute force algorithm. Since we know the constraint that we need to buy the stock before selling it.

- We can traverse the array.
- For every price, we can find if there is any following high price.
- If high price exists. Calculate profit, and run same algorithm on remaining array.

```
private int maxProfit_simpleRecursive(int[] prices, int startIndex) {
if (startIndex >= prices.length) {
return 0;
}
int maxProfit = 0;
for (int i=startIndex; i<prices.length; i++) {
int max = 0;
for (int j=i+1; j<prices.length; j++) {
//when can we sell
if (prices[j] > prices[i]) {
int profit = (prices[j] - prices[i]) + this.maxProfit_simpleRecursive(prices, j+1);
if (max < profit) {
max = profit;
}
}
}
if (maxProfit < max) {
maxProfit = max;
}
}
return maxProfit;
}
public int maxProfit_simple(int[] prices) {
return this.maxProfit_simpleRecursive(prices, 0);
}
```

**Complexity**

Above code runs in `O(n^n)`

.

If we try to draw the input in some sort of graph or line chart. We can see some pattern.

If you look closely, we can keep track of low points, and following high point. And take a sum of such points. We can get the maximum profit.

In the above image, we can take following calculation:

```
Low-point=1, High-point=5, Profit=4
Low-point=3, High-point=6, Profit=3
Total Profit = 7
```

```
public int maxProfit_better(int[] prices) {
if (prices == null || prices.length == 0) {
return 0;
}
int max = 0;
int i=0;
int lowPrice = prices[i];
int highPrice = prices[i];
i++;
while (i < prices.length) {
//find low value
while (i < prices.length && prices[i-1] >= prices[i]) {
i++;
}
lowPrice = prices[i-1];
//find high value
while (i<prices.length && prices[i] >= prices[i-1]) {
i++;
}
highPrice = prices[i-1];
max += (highPrice - lowPrice);
}
return max;
}
```

The code runs in `O(n)`

time as we are running loop n times only.

Above solution worked and is way faster than our first solution. Lets think more about the second solution. We are just finding low peak and high peak, finding difference and take it.

Instead, can we just take the difference if two consecutive prices are in increasing order. Yes, definitely.

Lets look at the code:

```
public int maxProfit_better2(int[] prices) {
if (prices == null || prices.length == 0) {
return 0;
}
int max = 0;
for (int i=1; i<prices.length; i++) {
if (prices[i] > prices[i-1]) {
max += (prices[i] - prices[i-1]);
}
}
return max;
}
```

Its again `O(n)`

Problem Statement Given a linked list, remove the n-th node from the end of list…

Problem Statement Given an array nums of n integers and an integer target, are…

System design interview is pretty common these days, specially if you are having…

A Binary tree is a data structure which has two children nodes attached to it…

Problem Statement The string “PAYPALISHIRING” is written in a zigzag pattern on…

Max Priority Queue is a data structure which manage a list of keys(values). And…

Introduction Strapi is a backend system provides basic crud operations with…

Introduction I had to create many repositories in an Github organization. I…

Introduction I was trying to download some youtube videos for my kids. As I have…

Introduction In this post, we will explore some useful command line options for…

Introduction In this post, we will see how we can apply a patch to Python and…

Introduction We will introduce a Package Manager for Windows: . In automations…