Tag: Coding

LeetCode 1249 – Minimum Remove To Make Valid Parentheses
This is one of the most asked questions by Meta in the past 3 months.

Given a string s of '(' , ')' and lowercase English characters.

Your task is to remove the minimum number of parentheses ( '(' or ')', in any positions ) so that the resulting parentheses string is valid and return any valid string.

Formally, a parentheses string is valid if and only if:
- It is the empty string, contains only lowercase characters, or
- It can be written as AB (A concatenated with B), where A and B are valid strings, or
- It can be written as (A), where A is a valid string.
Example 1:
```
Input: s = "lee(t(c)o)de)"
Output: "lee(t(c)o)de"
Explanation: "lee(t(co)de)" , "lee(t(c)ode)" would also be accepted.
```
The way to solve the problem is by using a combination of stack and a set.

You iterate through the string and check if the parentheses is valid with the help of a stack, as you do in the easy question Valid Parentheses. If you come across an invalid one, then you add the index to your set which tracks which indices to remove.

In the example lee(t(c)o)de) , we will initialise our stack to be empty and iterate through the array. Once we encounter a parenthesis, we check if its a closing or opening one. So we go through l,e,e, and we now have (, so we add the index to the stack. Our stack becomes [3], we continue and keep adding to the stack if it’s an open, otherwise we pop from the stack.

So our stack is [3,5] when we are at lee(t(c, now we see two closing brackets, so we pop twice from the stack. At the end of the string we see that we’ve a closing bracket and our stack is empty, so we will add this index to our set.

We then iterate through our string again and build our return string, skipping over characters which are part of our remove set.
The solution will work, but we’ve overlooked an edge case when our stack is non-empty, in that case all we’ve to do it do a union of the set and stack indices and keep track of it rather than only the set.

Here is the solution in python.
```
class Solution:
    def minRemoveToMakeValid(self, s: str) -> str:
        stack = []
        remove_set = set()
        for i,char in enumerate(s):
            if char not in "()":
                continue
            elif char == "(":
                stack.append(i)
            elif not stack:
                remove_set.add(i)
            else:
                stack.pop()

        indices_remove = remove_set.union(set(stack))
        output = []
        for i,char in enumerate(s):
            if i in indices_remove:
                continue
            else:
                output.append(char)
        return "".join(output)
            
```
The time complexity will be O(N) as we are doing a two pass solution and the space complexity is O(N) as in the worst case we might have the entire string as invalid.

Let me know in the comments if you want me to cover other leetcode problems. Thanks for reading.
March 24, 2025
LeetCode 270 – Closest Binary Search Tree Value
This question has been asked a lot by meta recently.
You can solve this question either by using a simple inorder traversal, which will take O(n) time and O(n) space complexity, or you can use the property of binary search and solve this in O(logn) time complexity and O(logn) space complexity due to the nature of the Binary Search Tree that values to the left of the node are always smaller than to the right.

Let’s take a look at the inorder traversal solution.
```
class Solution:
    def closestValue(self, root: Optional[TreeNode], target: float) -> int:
        

        self.closest = float("inf")
        def dfs(node):
            if not node:
                return 

            dfs(node.left)

            if abs(self.closest - target) > abs(node.val - target):
                self.closest = node.val

            if abs(self.closest - target) == abs(node.val - target):
                self.closest = min(node.val, self.closest)

            dfs(node.right)

        dfs(root)
        return self.closest
```
Here, we begin by creating a variable called closest. We then perform an inorder traversal of the binary search tree, evaluating whether the value of the current node is the closest to our target value. If we find that it is indeed closer, we update our closest variable accordingly. Additionally, we compare it with our previous estimate of closest. If they are equal, we then set our closest variable to the minimum of the two values, as specified in the problem statement.

Although this initial approach leads to a solution that is acceptable, it has a time complexity of O(n) and a space complexity of O(n). However, we can enhance our efficiency by halving our search space with each decision. In the worst-case scenario—where the tree is unbalanced from the root to the leaf—this method will still operate at O(n) time complexity. On average, though, we achieve a more efficient solution with a time complexity of O(log N).

By leveraging the properties of binary search trees, we ensure a more optimized search strategy. This not only improves performance but also ensures that our solution scales better with larger datasets.
```
class Solution:
    def closestValue(self, root: Optional[TreeNode], target: float) -> int:
        self.closest = float("inf")
        def dfs(node):
            if not node:
                return

            if abs(self.closest - target) > abs(node.val - target):
                self.closest = node.val

            if abs(self.closest - target) == abs(node.val - target):
                self.closest = min(node.val, self.closest)

            if target < node.val:
                dfs(node.left)
            else:
                dfs(node.right)

        dfs(root)
        return self.closest
```
Here, we reinitialize our variable closest. Instead of performing an inorder traversal, we check if the value of the current node is closer to the target. We then determine whether the target value is less than the value of the current node. If it is, we conduct a Depth-First Search (DFS) only on the left side of the tree; otherwise, we proceed with a DFS on the right side.

This approach effectively halves our search space, allowing us to achieve a time complexity of O(log N).
March 19, 2025
LeetCode 346. Moving Average from Data Stream (Python)
This is a premium problem on LeetCode and has also been asked by Meta as of the date of publishing almost 50 times.

The problem statement is pretty simple, given an incoming integer stream, you have to calculate the simple moving average. The size or the window is also given.
```
class MovingAverage:

    def __init__(self, size: int):
        

    def next(self, val: int) -> float:
        


# Your MovingAverage object will be instantiated and called as such:
# obj = MovingAverage(size)
# param_1 = obj.next(val)
```
Now a naive solution would be to initialise a data structure like an array and keep appending elements which are given in the next method and then compute the average of the last n elements, n being the size, every time.
```
from statistics import mean
class MovingAverage:

    def __init__(self, size: int):
        self.size = size
        self.nums = []

    def next(self, val: int) -> float:
        self.nums.append(val)
        return mean(self.nums[-self.size:len(self.nums)])
```
Now this will work, but there are two issues here. One we’re storing elements not required, meaning we only need to store the latest numbers till the dimension of size. Also, there is a lot of repeated work here, where we’re calculating the mean every time. Making this solution O(N) in time complexity and also O(N) in space complexity.

We can improve on both aspects. First, we will use a queue to store our numbers. The reason for doing so is that once the size of the queue becomes equal to our window size. We will pop elements from the left and add the numbers on the right. To do this efficiently, we will use the deque data structure in python.
We will also create a variable called sum, where we will track the running sum. This will allow us to compute the moving average in O(1) time complexity.
```
from collections import deque
class MovingAverage:

    def __init__(self, size: int):
        self.size = size
        self.sum = 0
        self.vals = deque()

    def next(self, val: int) -> float:
        if len(self.vals) >= self.size:
            self.sum -= self.vals.popleft()
        self.sum+=val
        self.vals.append(val)
        return self.sum/len(self.vals)
```
Here, you can see that we keep track of what the size of our self.vals is. If it exceeds the window size, we pop from the left and decrease our running sum.
No matter what the size is, we always increment our sum and also append the number to our queue.

There might be some minor improvements, but in terms of time and space complexity, this is the most optimal solution.

Let me know if you found this solution helpful. I’ll be posting more LeetCode solutions on the blog as I feel they are also an integral component to cracking Machine Learning jobs, especially at Meta, Google etc.
March 11, 2025
LeetCode #11 – Container With Most Water
Sometimes, coding questions are also part of data science interviews, so here is the solution to LeetCode #11 – the container with the most water problem.

The problem is very straightforward, you’re given a list with n integers, each representing the height of a tower, you’ve to find the maximum area that can be formed with these heights and the x-axis represents the index distance between the integers with a twist that since it represents a block containing water, you’ve to take the min of the two heights as the water has to contained within the towers.

For example, if the list of given heights is h = [1,1,4,5,10,1], the maximum area that can be formed will be 8. It will be between the tower with heights 4 and 10, with an index distance of 2. So the area will be min(4,10)*2 = 8.

Coming to the solution, the easiest solution will be to compare each combination of two tower heights, and return the maximum area that can be formed. This will have a time complexity of $O(n^{2})$
```
def maxArea(height: List[int]) -> int:
        max_vol = 0
        for i in range(len(height)):
            for j in range(1,len(height)):
                if j<=i:
                    continue
                else:
                    vol = min(height[i], height[j])*(j-i)
                    max_vol = max(max_vol, vol)
        return max_vol
```
Although the above solution will pass the sample test cases, it will eventually return Time Limit Exceeded as it is a very brute force solution, as it compares almost every possible combination. You can be a bit more clever in your approach and solve this problem in $O(n)$ time complexity.

The trick is using pointers, one for left and one for right, starting with the largest width and then storing the max area. Move the left pointer right if you encounter a higher tower in the left otherwise move the right pointer towards the left, and repeat till both pointers meet. In this way, you’ve traversed the list only once.
```
def maxArea(height: List[int]) -> int:
        l,r = 0,len(height) - 1
        max_vol = -1
        while l < r:
            #Calculating the shorter height of the two
            shorter_height = min(height[l], height[r])
            width = r-l
            vol = shorter_height * width
            max_vol = max(vol, max_vol)
            if height[l] < height[r]:
                l+=1
            else:
                r-=1
        return max_vol
```
Taking an example, if input is [1,4,5,7,4,1], then.

Step l r width min height area max area
1 0 5 5 1 5 5
2 0 4 4 1 4 5
3 1 4 3 4 12 12
4 1 3 2 4 8 12
5 2 3 1 5 5 12
The loop will exit after step 5 as in step 6 l = r = 3, and we get the max area as 12.
January 13, 2023