Minimum Number of Removals to Make Mountain Array - Leetcode 1671 - Python

Love you Neet ❤

This was hard! but nice explanation.

Holy hard!

Papa Neetcode finally posted a new video after 3 days 🥹

Did it using 2 LIS arrays

Coders, is leetCode running so slowly right now ?? I can't even open my profile page
And thx a lot neetCode!!

This is not the most optimal solution I guess. Why didn't you use Binary search to reduce the time complexity to NlogN?

One of the best explanations out there! Thank you so much for doing this!

# was able to rewrite your solution that's more understandable to me

def minimumMountainRemovals(self, nums: List[int]) -> int:
n = len(nums)

lis = [1] * n
for r in range(1, n):
for l in range(r):
if nums[r] > nums[l]:
lis[r] = max(lis[r], lis[l] + 1)

lds = [1] * n
for r in range(n - 2, -1, -1):
for l in range(n - 1, r, -1):
if nums[r] > nums[l]:
lds[r] = max(lds[r], lds[l] + 1)


max_mountain = 0
for i in range(1, n - 1):
if lis[i] > 1 and lds[i] > 1:
cur_mountain = lis[i] + lds[i] - 1
max_mountain = max(max_mountain, cur_mountain)

return n - max_mountain

Thanks

Smooth

Additional optimization to papa NeetCode's solution would be to put the LIS and result loop together because their loop starts and ends on the same index.

def minimumMountainRemovals(self, nums: List[int]) -> int:
lds = [1 for i in nums]
lis = [1 for i in nums]
res = len(nums)

# Get lds
for i in range(len(nums)-2, 0, -1):
cur_max = 1
for j in range(i+1, len(nums)):
if nums[i] > nums[j] and lds[j]+1 > cur_max:
cur_max = lds[j]+1
lds[i] = cur_max

# Get lis and res
for i in range(1, len(nums)-1):
cur_max = 1
for j in range(i):
if nums[i] > nums[j] and lis[j]+1 > cur_max:
cur_max = lis[j]+1
lis[i] = cur_max

# Calc res
if cur_max != 1 and lds[i] != 1:
calc = len(nums)-cur_max-lds[i]+1
res = calc if calc < res else res

return res

And also because we loop only the required indexes, the resulting code runs faster on 936 ms (69%) on my end.

The peak of leetcode

appreciate your explanations as usual

Should have also included the O(Nlog(N)) solution using Binary Search.

I am thinking to include ur photo in my prayer room 😁, good explanattion bro

Similar to Longest Bitonic subsequence if anyone wants to practice similar kind of a problem.

im saving the neetcode 150 for when i actually get an interview

no binary search solution ? 😢

Good advice. Don't get discouraged -- there's always an opportunity to learn and appreciate.

The way I did it is by defining two right pointers and two left pointers (the left ones are from the nested loops themselves) and I updated the right ones as we went along. This way, you can use a single nested loop instead of doing it twice :)

It's a bit harder to read, but works faster

let rp1 = arr.length - 2;
let rp2 = arr.length - 1;


for (let lp1 = 1; lp1 < arr.length; lp1++) {
for (let lp2 = 0; lp2 < lp1; lp2++) {
if (arr[lp2] < arr[lp1]) { increase[lp1] = Math.max(increase[lp1], increase[lp2] + 1); }
if (rp1 >= 0 && rp2 > rp1 && arr[rp2] < arr[rp1]) { decrease[rp1] = Math.max(decrease[rp1], decrease[rp2] + 1)}
rp2--;
}
rp1--;
rp2 = arr.length - 1;
}

Complex codes made easy. Super sir.
Can you suggest some books to learn complete DSA ?
I wonder how you learnt DSA. could you please answer ?

It will be a pro gamer move if they let yesterday problem LIS

Hi Neetcode! I got an offer from Uber!
I would never be able to pass their interview without your videos. Keep it up!

Bruteforce would be backtracking, generating all subseq and checking each subseq if its mountain and return its size, but time complexity would be n * 2^n then we can try bottom up dp LIS / LDS and come up n*n solution.

wonderfull as always, thanks for gr8 explanation

thanks :)

Hi, Love your videos, they are very helpful!!!

Have you tried to use Open AI O1 model since it was released? I would like to hear your thoughts/comments on its code generation capabilities. Thanks!!

Hii Neetcode I has able to come up with LIS and LDS solution but in editorial there are other approaches also
do i really need to go through them or if i am able to solve it then it good go ahead ?
pls help me out !!!

That was mesmerzing.

Thank you❤

why are the code solutions removed form website?

How much time it took you to solve?

reaallyy appreciate your work nd passion!!! :)
Suggesting an optimization on this problem
You can do Binary search to find LIS at particular index

class Solution {
public:
int minimumMountainRemovals(vector<int>& nums) {
int sz = nums.size();
vector<int> pre(sz, 0), post(sz, 0);
vector<int> temp;
int tempSz=1, ans=0;
temp.push_back(nums[0]);
pre[0]=0;
for(int i=1;i<sz;i++)
{
if(nums[i] > temp[tempSz-1])
{
pre[i] = tempSz;
temp.push_back(nums[i]);
tempSz++;
continue;
}
int mid = lower_bound(temp.begin(), temp.end(), nums[i]) - temp.begin();
pre[i] = mid;
temp[mid] = nums[i];
}

post[sz-1]=0;
tempSz=1;
temp.clear();
temp.push_back(nums[sz-1]);
for(int i=(sz-2);i>=1;i--)
{
if(nums[i] > temp[tempSz-1])
{
post[i] = tempSz;
temp.push_back(nums[i]);
tempSz++;
if(pre[i]!=0 && post[i]!=0)
ans = max(ans, pre[i]+post[i]);
continue;
}
int mid = lower_bound(temp.begin(), temp.end(), nums[i]) - temp.begin();
post[i] = mid;
temp[mid] = nums[i];
if(pre[i]!=0 && post[i]!=0)
ans = max(ans, pre[i]+post[i]);
}
return sz-ans-1;
}
};

Just to skim thru the code for LIS portion,
1) temp is storing longest LIS till index i.
2) If arr[i] > temp.end(), means it is greater element and hence can be part of LIS in future.
3) If not, then we find index of number which is just greater than the arr[i]. All numbers before that index is LIS till index i and because we need LIS, we will store minimum number at particular index.
4) We reverse this process for decreasing sequence OR wwe traverse the sequence in reverse order

Hope it helps....any queries or suggestions are welcome
Just an FYI, it did beat 100% of users