Remove Nth Node from End of List and Generate Parentheses

Let’s continue…

Problem Statement:

Given linked list: 1->2->3->4->5, and n = 2.

After removing the second node from the end, the linked list becomes 1->2->3->5.

Solution One: Brute Force

The most straightforward way to solve this problem is iterate the whole list once, and we can calculate the length of the list. Then we can simply calculate the index of the node we want to remove. Then we can iterate again to remove it. This is a two-pass solution (It’s not good enough according to the requirement of the problem).

Time Complexity: O(2*L – n) L is the length of the list.

Space Complexity: O(1)

Solution Two: Two Pointers

We can do it in one pass by allocating two pointers, basically, first pointer will move forward n steps before second pointer moves. Then when the first pointer is ready, we iterate both pointers forward until the first pointer reaches the end. Then we can safely delete the nth node.

The only thing we need to care about is the boundary. However, it is not hard. Try to draw all the nodes on paper will help.

Time Complexity: O(L)

Space Complexity: O(1)

Problem Statement:

[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

Solution One: Back Tracing

OK, Let’s look at several situations. If the number of  left parenthesis is greater than n, then the formation will always be invalid. Another thing is when the number of right parenthesis is greater than the number of left parenthesis, the formation is always invalid as well.

Based on these two assumptions, we can use recursive function to do our job, first we need to set our base ground, when the string size equals to 2*n, which means our valid parentheses meets our goal, we append the temp string with ‘)’, and push the temp to our final result.

Then we recursively call the generate parentheses function. We specifically define the left part and right part. When the number of left parenthesis is less than n, we add left parenthesis; when the number of right parenthesis is less than left parenthesis, we add right parenthesis.

In order to better understanding the recursive call, you need to draw a call tree, with each function call you can draw a node. For example, if n = 2, a tree looks like below:As you can see from the graph, when n = 2, we have two possible solutions: (()) and ()(). The red mark means the condition does not meet, we will not do recursive call here. Each layer means the depth of the recursive function call. If you are struggling with recursion, you should try to draw a tree like this. This will help you understand the general structure of recursive function.

Time Complexity: O(2^(2*n)) We can see from the tree, the height of the tree is 2*n, and potentially we will have maximum 2^(2*n) nodes.

Space Complexity: O(n) The auxiliary space for this recursive function call is at maximum 2*n.

Solution Two: Permutation

Let’s look at this problem from another perspective.

We know that all the valid parentheses should start with “(” first and end with “)”. We can also clear say that we have an index c in between, when we first reach an index c, the number of  left parentheses and the right parentheses are both equal. Since the parentheses sequence is valid, which means the parentheses [1 : c-1] and parentheses [c+1: 2*n – 1] should both be valid. Look at the picture below:

We can say each valid parentheses sequence will exist a constant number c, which can divide the parentheses sequence into two parts. For a specific sequence, the c is determined. So, if we want to know all the possible valid permutations of n pairs of parentheses, we only need to know the valid permutations of a pairs parentheses (left part) and n-a-1 pairs parentheses (right part) and combine them with one extra pair of parentheses:

“(” + left + “)” + right

For example, if n = 3, we have several situations:

• left = 0; right = 2; At this time, c = 1 (determined)

The sequence should look like: ()()() or  ()(()).

• left = 1; right = 1; At this time, c = 3 (determined)

The sequence should look like: (())(). Only one possible solution.

• left = 2; right = 0; At this time, c = 5 (determined)

The sequence should look like: (()()) or ((())). Similar to situation left = 0, right = 2.

So based on this idea, we create a loop, and iterate c. You can see that c = left * 2 + 1 (1<=c<=2*n-1). This makes sense, because left should be valid parentheses in this case, which means it should be even number. And index start from 0, so c should be odd number.

Time Complexity: Unknown

Space Complexity: Unknown

Let’s see the code, the code is pretty concise:

That’s all for today. Thanks for reading…