Redirecting to
NADOS


  Prev   Next

Count Brackets







It does not matter how slowly you go as long as you do not stop.
~Confucius

Count Brackets

Welcome Back Reader!

In this article we will discuss about the next problem based on "Dynamic Programming" i.e. "Count Brackets".

Prerequisite of this problem is Catlan Number.

Before you move any further, it is advised that you give this problem a fair try.
Let's jump to the problem.

Importan Link : Problem Link, Solution Video Link

Understanding the problem:

In this problem you are given a number n, representing the number of opening brackets (and closing brackets).

All you are required to do is to find the number of ways in which you can arrange the brackets if the closing brackets should ever exceed opening brackets.

For example:

  • for 1, answer is 1 -> ()
  • for 2, answer is 2 -> ()(), (())
  • for 3, answer is 5 -> ()()(), () (()), (())(), (()()), ((()))

For more clarity of the question, watch this part of the video.

Moving On:
  • In this problem we need to find the number of ways in which you can arrange the brackets.
  • This problem is just another application of Catlan Number.
  • So we will use the Catlan Number approach to solve this problem.
  • For input 0, we assume that the output is 1.
  • For input 1, it implies that we have 1 opening bracket and 1 closing bracket i.e. one pair and we can arrange this in only one way (valid).
    • img
  • For input 2, we have 2 pairs. We can either put one pair inside another pair or not. This way we can arrange 2 pairs in two ways
    • img
  • For input 3, we have 3 pairs. We can arrange these 3 pairs in 3 ways.
    • To start with, we can place 2 pairs inside 1 pair.
    • We can also place 1 pair inside 1 pair and one outside it.
    • We can also place 0 pairs inside 1 pair and 2 pairs outside.
      • img
    • If we place 2 pairs inside one pair then we have two ways to do so.
    • If we place 1 pair inside 1 pair and one outside then we have only one way to do so.
    • And if we place 0 pairs inside 1 pair and 2 pairs outside then again we can do this in two ways.
    • In total we will have 5 different ways which is also the output for 3.
  • So from the above points, we can analyze that the problem is following catalan pattern.
    • img
  • Let's see for input 4.
  • For input 4, we have 4 pairs. We can arrange these 4 pairs in 4 ways.
    • To start with, we can place 3 pairs inside 1 pair and 0 outside it.
    • We can also place 2 pairs inside 1 pair and 1 outside it.
    • We can also place 1 pair inside 1 pair and 2 pairs outside it.
    • We can also place 0 pairs inside 1 pair and 3 pairs outside it.
      • img
    • If we place 3 pairs inside one pair then we have five ways to do so.
    • If we place 2 pairs inside 1 pair and 1 pair outside then we have only two ways to do so.
    • If we place 1 pair inside 1 pair and 2 pairs outside then we have only two ways to do so.
    • If we place 0 pairs inside one pair and 3 pairs outside it then we have five ways to do so.
    • And if we place 0 pairs inside 1 pair and 2 pairs outside then again we can do this in two ways.
      • img

For more clarity of this part; watch this part of the video.

WHAT'S THE REAL HACK?

So the real trick behind these types of problems i.e. based on Catlan Number is to observe the pattern. If you are able to observe it then I'm sure that even you find the logic pretty easy.

Let's try to code this!
img

//1 - Take input for n.
//2 - After that define an array, dp of long type and length n+1.
//3 - Then we place 1 at dp[0]
//4 - Then we apply a for loop on dp length, initializing i to 1.
//5 - Now we use a nested for loop to calculate the value for ith index of dp by travelling the filled dp array.
//6 - Then inside the nested for loop, at dp[i], keep adding dp[j] * dp[i - 1 - j].
//7 - At last, print dp[n].

For more clarity of the code, watch this part of the video.

Complexities:
Time Complexity: O(n)

A for loop is used 2 times, which condenses to O(n).

Space Complexity: O(n)

One n sized arrays are used which condense to O(n).

import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine()); long[] dp = new long[n + 1]; dp[0] = 1; for(int i = 1; i < dp.length; i++){ for(int j = 0; j < i; j++){ dp[i] += dp[j] * dp[i - 1 - j]; } } System.out.println(dp[n]); } }
java; true";

We hope that this article was helpful. If somehow you are finding it difficult to understand this problem then we advise you to watch our video lecture of this problem.

Trust me it will just get easier to understand after you have watched the solution video.

You can contact us via our website. Doubts, suggestions and feedback are always welcomed.

It is also advised that you follow the sequence of modules and questions which is there on our website.

Keep practicing more and more problems daily. Meditate enough on each step of each problem.

All the best for an exciting future!
Happy Coding!

Count Brackets
Author: Nikita Aggarwal
 
Run
Id Name