Remove Nth Node from End of List and Generate Parentheses

Let’s continue…

Problem Statement:

Remove Nth Node from End of List

Given a linked list, remove the n-th node from the end of list and return its head.

Example:

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.

Note:

Given n will always be valid.

Follow up:

Could you do this in one pass?


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:

Generate Parentheses

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, given n = 3, a solution set is:

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

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:TIM截图20181104004657As 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:

TIM截图20181104010757

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  ()(()).

TIM截图20181104012212

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

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

TIM截图20181104012441

  • 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…

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s