LeetCode #155 - Min Stack

Ashley Nguyen — Thu, 08 Jun 2023 17:45:08 +0000

**Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

Implement the MinStack class:

MinStack() initializes the stack object.
void push(int val) pushes the element val onto the stack.
void pop() removes the element on the top of the stack.
int top() gets the top element of the stack.
int getMin() retrieves the minimum element in the stack. You must implement a solution with O(1) time complexity for each function.**

Another designing stack question - another version of the painful tricky Implementing queue from stack problem. The major difference here is that the stack will possess all functions like a normal stack - push, pop, top (peek), except that there must be another data structure to store and update the minimum value of the whole stack, and return it when getMin() is called.

My initial approach was rather focused on getMin(), in which I would dynamically change the position of elements in the main stack to make sure they are in ascending order from the top down. However, this approach will prove problematic and complicated regarding other operations.

So let's get started.

First, I initialize two empty stacks. The main stack is minStack, and the supplementary stack storing min value is stack (please excuse the naming).

Push

Since minStack acts like a normal stack, we simply push the element to minStack. With stack, we only add the element whenever it is less than stack's top element. This way, we can make sure that stack's top is always the current minimum element of the minStack.

Pop

Again, simply pop the head of minStack. If that value is equal to the head of stack, we pop the head of stack as well.

Top

Simply return the head of minStack, in which I use Stack.peek() operation. stack is not touched in this operation.

getMin

After tons of new additions and removal from our main stack, we are guaranteed that only smaller elements are added to stack. Therefore, return stack's head element.

LeetCode #128 - Longest Consecutive Sequence

Ashley Nguyen — Thu, 08 Jun 2023 17:44:40 +0000

A medium LeetCode problem after days of only easy or no LeetCode at all. I got all test cases passed after four trials (the time gaps were due to my dinner..), and all of them were necessary to solve my careless presumptions in understanding the problem - really reminding me to spend more time thoroughly digging into edge cases and the underlying purpose.

_Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence.

You must write an algorithm that runs in O(n) time.

Input: nums = [100,4,200,1,3,2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4

Input: nums = [0,3,7,2,5,8,4,6,0,1]
Output: 9
_
Understand the problem
The problem statement was quite straightforward (poor assumption!) and the given examples made it even more self-explanatory: we need to find out in the given array the longest sequence that contains consecutive numbers. It looks to me that we can sort the array for this question and then it becomes much easier: all we need to do left is to identify the longest subarray that contains consecutive integers.

What about edge cases? In the case that the array is empty or has only one element, the result will be the length of the array itself.

**Match the problem

One thing I could think of in the first place after sorting the array is that there can be multiple relevant subarrays in the sorted array. Therefore, we need to find all those subarrays, keep a variable that represent the subarray length, and keep updating the variable whenever we find a longer relevant sequence. This sounded to me like a sliding window problem.

The first thing to do after handling the edge case and sorting the array is creating two variables representing the start and end of the sliding window. I declare them both at 0.

One question at this point might be: Why do we declare maxLen at 1, not 0 or any other number? The reason is that we can consider each integer a relevant sequence to return; therefore, even if the array does not contain any more than 2-integer relevant sequence, the result returned will always be 1.

Another question is : Why don't we declare left at 0 and right at 1 - we need to compare two consecutive numbers, don't we? The answer is that we will not use both left and right variables to compare, but the left variable will rather be "static" while the right variable continues to increment in case we identify a possible relevant sequence.

The right variable is actually compared to its next [right + 1]. If their difference is 0, we continue to increment right and keep an eye for maxLen. If otherwise, that means we need to start considering a new sequence starting at where right currently is, so we summon left to represent the start of a new sequence.

BUT ...

One case I did not encounter for is.. what if the sorted array looks like this: [0,1,1,2]. The answer for this case should be 3, not 2, because the problem is not asking for a sequence of consecutive numbers that lie next to each other, but that the numbers only need to be in the array. So in case there is duplicates, we can simply count them as one and move on.

Final code (after rearrange if else statements):

The time complexity of Arrays.sort is O(nlogn), and the time complexity of the rest of the code is O(n) (since we iterate through all elements). Therefore the overall time complexity is O(nlogn).

DEV Community: Ashley Nguyen

LeetCode #155 - Min Stack

LeetCode #128 - Longest Consecutive Sequence