Blog

Leetcode 962: Maximum Width Ramp

Oct 17, 2024

About

So this problem is basically asking about finding the longest distance between two indexs of an array such that the left index is lower then the right index, and that the value at the left index is smaller then the value at the right index.

Another way to look at this problem is to pick two indexs, I and J, such that the index I appears before index J, as well as the number at nums index of I being smaller then the value at nums index of J.

In other words, Number I must appear before J in the array, and number I must be smaller than number J in the array.

For example [(1),2,3,4,(5)] = Minimal distance between elements 5 and 1 is 4 [(1),0,2,(3)] = Minimal distance between elements 1 and 3 is 3 [6,3,(2),1,5,(3)] = Minimal distance between the last 3 and the middle 2 is 4

Thoughts

I immediately misread the questions and assumed it was talking about finding the largest increasing monotonic stack by traversing left to right in the test case array. However, even after realizing this wasn’t the case, I was still determined to use a monotomic stack for this problem.

Rethinking about the problem, I realized that for each right most index, the distance value that would be returned was the distance between itself and the leftmost index of any element that is smaller then the right most index’s value. For example, for a testcase like [200,5,4,3,2,1,100] at the index for element 100, you would consider only 5,4,3,2,1 since those are values that are smaller then 100. the 200 can then be ingnored.

Also I realized that the way to get a maximal distance would be using classic monostack popping until you reach a point where you can no longer pop. For example, with testcase [200,5,4,3,2,1,100], you could have a monostack like [200,5,4,3,2,1], and then pop elements 5,4,3,2,1 you are left with 200.

For testcases like [10,1,2,3,11], your monostack that you start with initally should just elements such that each element is less then its prevous elements. For example, you would only need to have [10,1] to evaluate from the 11 element. This is due to being 2 and 3 being larger then 1, but also appearing after 1 in the array. Since 1 is already smaller then the next elements, 2 and 3, and can greedily say that 2 and 3 are not good choices, since 1 is already smaller then thoose two values.

Lastly, with a problem like this I am sure that while my monoStack is going to use the values of the array for comparisons, I am storing indexs inside of the monoStack itself. This way, I am able to do a distance calculation between two different points in the array if certian conditions are meet.

Implementation

First, I use a for loop to form a decreasing monoStack in Javascript like I usually do. However, I dont preform any popping operations, only pushs when I find numbers that are smaller then the previous number on the top of the stack.

I then a second for loop, this time moving from right to left, to remove elements from my monoStack if they are smaller or equal to my current number. I also update my max varible with the max possible distance between the index. This is simply done my taking my current Rightmost index on my, and then subtracting the index on the top of the stack, which represents the rightmost index of the next element in the array that is smaller than my rightmost index’s value.

Finally, I just return max which after the second for loop runs, contains my maximal distance / maximal ramp width to leetcode.

Leetcode 921: Minimum Add To Make Parentheses Valid

Oct 7, 2024

DevGod

Elf Vtuber

About

This problem is very similar to yesterday’s problem. The main difference is instead of swapping characters that are already present in the string, we are appending either a ”(” or a ”)” anywhere we want in the string. However, we still have the same goal of finding the minimal number of operations needed to achieve a balanced string of () such that each opening symbol ( has a corresponding symbol ).

For example

((), needs 1 ) symbol at the end to become balanced
()()() is already balanced, so return 0
))) needs 3 opening symbols to become balanced

Thoughts

My thoughts immediately jumped to yesterday. The only difference is I ended up having two variables, one for the remainder of unmatched opening symbols, and one for the unmatched closing symbols. Once I was able to find these two values, at first I mistakenly thought it was some sort of find the max value between them. But in practice, it is the addition of both values together to get the minimal number of additions needed to balance the string.

Implementation

Here in JS, I use a for loop to iterate through the test case string, while also finding the leftmost character & the rightmost character. After I have these varibles, I am then able to move left to right to calculate the remainder of opening ( symbols, while also moving right to left to find the remainder of closing ) symbols. After my for loop is completed, I then return the amount of unmatched opening ( symbols plus the amount of matched closing symbols ) together.

Leetcode 1963: Minimum Number of Swaps to Make the String Balanced

Oct 6, 2024

DevGod

Elf Vtuber

About

This leetcode problem is basically us to find the minimum number of swap operations are needed to make a string of ”[]” symbols balanced. Balanced being if each opening ”["" symbol also has a closing ”]” symbol. For example, the following would be examples of balanced strings.

[]
[[]]
[][][]

Thoughts

One thing to notice off the bat is when considering certain testcases, it is already possible that a string already contains a balanced string. For example, testcase ]][][[ already has a balanced string in the middle, so it is the same as ]][[. For example, all testcases either eventually become testcases such as ][, ]][[, ]]][[[ ect.

After we see this, it is now about finding a remainder inside our testcase string of extra unmatched chars. For example, in ][ the remained would be one, which can be viewed either as having one unmatched opening char, or one unmatched closed char.

After drawing out these certain testcases, I saw a certain pattern involving the remaining total of unmatched charecters in the sring.

][ = 1 Swaps needed
]][[ = 1 Swaps needed
]]][[[ = 2 Swaps needed
]]]][[[[ = 2 Swaps needed
]]]]][[[[[ = 3 Swaps needed

The pattern being, that for the remaining amount of unmatched symbols at the end of the string is then Math Ceil (remaining amount of unmatched chars / 2) is the number of swaps needed.

Implementation

There are two ways you can solve this problem. One way is to use a stack data structure to keep track of previous symbols, and then pushing and popping accordingly. However, what I ended up doing to save memory usage was to simulate the stack size instead. Since we only need to return the minimal amount of swaps needed, we don’t need to have a stack, only the state of the would be stack’s size / length. Once I for loop to simulate the stack size, I simply just return the Math.ceil(remainder / 2) to return the minimal amount of swaps needed.

Leetcode 2696: Minimum String Length After Removing Substrings

Oct 5, 2024

DevGod

Elf Vtuber

About

This problem is basically asking after you replace every occurrence of a substring “AB” or “CD” in your testcase string, return the length of the new string. For example:

“ABCDZ” => “Z” => return 1;
“QABABABQ” => “QQ” => return 2;
“ACDB” => "" return 0;

Thoughts

The first two example testcases are pretty straight forward. Just remove “AB” substrings, then remove all “CD” substrings. However, the third testcase gets interesting where we remove “AB”, then remove “CD”. However, after removing the “CD” we are left with “AB”, which can then be removed again to return a blank string "" / a return string length of 0. After seeing this I immediately just wanted to use regular expressions, as that would be perfect for finding substrings present in my main string, as well as for preforming replaceAll operations to remove “AB” and “CD” substrings from the main testcase string.

Implementation

I simply just made a while loop that only ends once my given String s no longer has a “AB” or a “CD” substring present inside of itself. This is done by using the regular expression /AB|CD/, which just checks for any occurrence of an “AB” or “CD”. The .test(s) then just takes my regular expressions, searches the string using said regular expression, then returns true or false.

Inside my while loop, I then use s.repalceAll and /AB|CD/g to replace all occurrences of ABs and CDs from my current string. The regular expression is pretty similar to the top, I just use G to make sure its global since it’s a replace all.

Lastly, once my String S no longer has any occurrences of substrings “AB” or “CD”, I exit my while loop and then just return the length of my now AB and CD substring freed string.