Balanced expressions such that given positions have opening brackets
Given an integer n and an array of positions ‘position[]’ (1 <= position[i] <= 2n), find the number of ways of proper bracket expressions that can be formed of length 2n such that given positions have opening bracket.
Examples :
Input : n = 3, position[] = [2}
Output : 3
Explanation :
The proper bracket sequences of length 6 and
opening bracket at position 2 are:
[ [ ] ] [ ]
[ [ [ ] ] ]
[ [ ] [ ] ]
Input : n = 2, position[] = {1, 3}
Output : 1
Explanation: The only possibility is:
[ ] [ ]
Approach : This problem can be solved by Dynamic programming..
Let DPi, j be the number of valid ways of filling the first i positions such that there are j more brackets of type ‘[‘ than of type ‘]’. Valid ways would mean that it is the prefix of a matched bracket expression and that the locations at which enforced ‘[‘ brackets are enforced, have been satisfied. It is easy to see that DP2N, 0 is the final answer.
The base case of the DP is, DP0, 0=1. We need to fill the first position with a ‘[‘ bracket, and there is only way to do this.
If the position has a opening bracket sequence which can be marked by a hash array, then the recurrence occurs as :
if(j != 0) dpi, j = dpi-1, j-1
else dpi, j = 0;
If the position has no opening bracket sequence, then recurrence happens as :
if(j != 0) dpi, j = dpi - 1, j - 1 + dpi - 1, j + 1
else dpi, j = dpi - 1, j + 1
The answer will be DP2n, 0
Given below is the implementation of the above approach :
C++
// CPP code to find number of ways of // arranging bracket with proper expressions #include <bits/stdc++.h> using namespace std; #define N 1000 // function to calculate the number // of proper bracket sequence long long arrangeBraces( int n, int pos[], int k) { // hash array to mark the // positions of opening brackets bool h[N]; // dp 2d array int dp[N][N]; memset (h, 0, sizeof h); memset (dp, 0, sizeof dp); // mark positions in hash array for ( int i = 0; i < k; i++) h[pos[i]] = 1; // first position marked as 1 dp[0][0] = 1; // iterate and formulate the recurrences for ( int i = 1; i <= 2 * n; i++) { for ( int j = 0; j <= 2 * n; j++) { // if position has a opening bracket if (h[i]) { if (j != 0) dp[i][j] = dp[i - 1][j - 1]; else dp[i][j] = 0; } else { if (j != 0) dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j + 1]; else dp[i][j] = dp[i - 1][j + 1]; } } } // return answer return dp[2 * n][0]; } // driver code int main() { int n = 3; // positions where opening braces // will be placed int pos[] = { 2 }; int k = sizeof (pos)/ sizeof (pos[0]); cout << arrangeBraces(n, pos, k); return 0; } |
Java
// Java code to find number of ways of // arranging bracket with proper expressions public class GFG { static final int N = 1000 ; // function to calculate the number // of proper bracket sequence static long arrangeBraces( int n, int pos[], int k) { // hash array to mark the // positions of opening brackets boolean h[] = new boolean [N]; // dp 2d array int dp[][] = new int [N][N]; // mark positions in hash array for ( int i = 0 ; i < k; i++) { h[pos[i]] = true ; } // first position marked as 1 dp[ 0 ][ 0 ] = 1 ; // iterate and formulate the recurrences for ( int i = 1 ; i <= 2 * n; i++) { for ( int j = 0 ; j <= 2 * n; j++) { // if position has a opening bracket if (h[i]) { if (j != 0 ) { dp[i][j] = dp[i - 1 ][j - 1 ]; } else { dp[i][j] = 0 ; } } else if (j != 0 ) { dp[i][j] = dp[i - 1 ][j - 1 ] + dp[i - 1 ][j + 1 ]; } else { dp[i][j] = dp[i - 1 ][j + 1 ]; } } } // return answer return dp[ 2 * n][ 0 ]; } // Driver code public static void main(String[] args) { int n = 3 ; // positions where opening braces // will be placed int pos[] = { 2 }; int k = pos.length; System.out.print(arrangeBraces(n, pos, k)); } } // This code is contributed by 29AjayKumar |
Python3
# Python 3 code to find number of ways of # arranging bracket with proper expressions N = 1000 # function to calculate the number # of proper bracket sequence def arrangeBraces(n, pos, k): # hash array to mark the # positions of opening brackets h = [ False for i in range (N)] # dp 2d array dp = [[ 0 for i in range (N)] for i in range (N)] # mark positions in hash array for i in range (k): h[pos[i]] = 1 # first position marked as 1 dp[ 0 ][ 0 ] = 1 # iterate and formulate the recurrences for i in range ( 1 , 2 * n + 1 ): for j in range ( 2 * n + 1 ): # if position has a opening bracket if (h[i]): if (j ! = 0 ): dp[i][j] = dp[i - 1 ][j - 1 ] else : dp[i][j] = 0 else : if (j ! = 0 ): dp[i][j] = (dp[i - 1 ][j - 1 ] + dp[i - 1 ][j + 1 ]) else : dp[i][j] = dp[i - 1 ][j + 1 ] # return answer return dp[ 2 * n][ 0 ] # Driver Code n = 3 # positions where opening braces # will be placed pos = [ 2 ,]; k = len (pos) print (arrangeBraces(n, pos, k)) # This code is contributed # by sahishelangia |
C#
// C# code to find number of ways of // arranging bracket with proper expressions using System; class GFG { static int N = 1000; // function to calculate the number // of proper bracket sequence public static long arrangeBraces( int n, int [] pos, int k) { // hash array to mark the // positions of opening brackets bool [] h = new bool [N]; // dp 2d array int [,] dp = new int [N,N]; for ( int i = 0; i < N; i++) h[i] = false ; for ( int i = 0; i < N; i++) for ( int j = 0; j < N; j++) dp[i,j] = 0; // mark positions in hash array for ( int i = 0; i < k; i++) h[pos[i]] = true ; // first position marked as 1 dp[0,0] = 1; // iterate and formulate the recurrences for ( int i = 1; i <= 2 * n; i++) { for ( int j = 0; j <= 2 * n; j++) { // if position has a opening bracket if (h[i]) { if (j != 0) dp[i,j] = dp[i - 1,j - 1]; else dp[i,j] = 0; } else { if (j != 0) dp[i,j] = dp[i - 1,j - 1] + dp[i - 1,j + 1]; else dp[i,j] = dp[i - 1,j + 1]; } } } // return answer return dp[2 * n,0]; } // driver code static void Main() { int n = 3; // positions where opening braces // will be placed int [] pos = new int []{ 2 }; int k = pos.Length; Console.Write(arrangeBraces(n, pos, k)); } //This code is contributed by DrRoot_ } |
Javascript
<script> // Javascript code to find number of ways of // arranging bracket with proper expressions let N = 1000; // function to calculate the number // of proper bracket sequence function arrangeBraces(n, pos, k) { // hash array to mark the // positions of opening brackets let h = new Array(N); h.fill( false ); // dp 2d array let dp = new Array(N); for (let i = 0; i < N; i++) { dp[i] = new Array(N); for (let j = 0; j < N; j++) { dp[i][j] = 0; } } // mark positions in hash array for (let i = 0; i < k; i++) { h[pos[i]] = true ; } // first position marked as 1 dp[0][0] = 1; // iterate and formulate the recurrences for (let i = 1; i <= 2 * n; i++) { for (let j = 0; j <= 2 * n; j++) { // if position has a opening bracket if (h[i]) { if (j != 0) { dp[i][j] = dp[i - 1][j - 1]; } else { dp[i][j] = 0; } } else if (j != 0) { dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j + 1]; } else { dp[i][j] = dp[i - 1][j + 1]; } } } // return answer return dp[2 * n][0]; } let n = 3; // positions where opening braces // will be placed let pos = [2]; let k = pos.length; document.write(arrangeBraces(n, pos, k)); </script> |
3
Time Complexity: O(n^2)
Auxiliary Space: O(n^2)
Efficient approach: Space optimization
In previous approach, the dp[i][j] is depend upon the current and previous row of 2D matrix. So to optimize space we use two vectors curr and dp that keep track of current and previous row of DP.
Implementation Steps:
- Initialize a vectors dp of size N+1 to keep track of only previous row of Dp matrix with 0.
- Now iterative over subproblems and get the current computation.
- While Initialize a vectors curr of size N+1 to keep track of only current row of Dp matrix with 0.
- Now compute the current value by the help of dp vector and store that value in curr.
- After every iteration store values of curr vector in dp vector for further iteration.
- At last return the answer stored in dp[0].
Implementation:
C++
// CPP code to find number of ways of // arranging bracket with proper expressions #include <bits/stdc++.h> using namespace std; #define N 1000 // function to calculate the number // of proper bracket sequence long long arrangeBraces( int n, int pos[], int k) { // hash array to mark the // positions of opening brackets bool h[N]; // vector ot keep track of previous roe of Dp vector< int > dp(N + 1, 0); memset (h, 0, sizeof h); // mark positions in hash array for ( int i = 0; i < k; i++) h[pos[i]] = 1; // first position marked as 1 dp[0] = 1; // iterate and formulate the recurrences for ( int i = 1; i <= 2 * n; i++) { // value of current row of DP vector< int > curr(N + 1, 0); for ( int j = 0; j <= 2 * n; j++) { // if position has a opening bracket if (h[i]) { if (j != 0) curr[j] = dp[j - 1]; else curr[j] = 0; } else { if (j != 0) curr[j] = dp[j - 1] + dp[j + 1]; else curr[j] = dp[j + 1]; } } // assigning values to iterate further dp = curr; } // return answer return dp[0]; } // driver code int main() { int n = 3; // positions where opening braces // will be placed int pos[] = { 2 }; int k = sizeof (pos) / sizeof (pos[0]); cout << arrangeBraces(n, pos, k); return 0; } |
Java
import java.util.*; public class Main { static final int N = 1000 ; // function to calculate the number // of proper bracket sequence static long arrangeBraces( int n, int pos[], int k) { // hash array to mark the // positions of opening brackets boolean [] h = new boolean [N]; // vector ot keep track of previous roe of Dp List<Integer> dp = new ArrayList<>( Collections.nCopies(N + 1 , 0 )); Arrays.fill(h, false ); // mark positions in hash array for ( int i = 0 ; i < k; i++) { h[pos[i]] = true ; } // first position marked as 1 dp.set( 0 , 1 ); // iterate and formulate the recurrences for ( int i = 1 ; i <= 2 * n; i++) { // value of current row of DP List<Integer> curr = new ArrayList<>( Collections.nCopies(N + 1 , 0 )); for ( int j = 0 ; j <= 2 * n; j++) { // if position has a opening bracket if (h[i]) { if (j != 0 ) { curr.set(j, dp.get(j - 1 )); } else { curr.set(j, 0 ); } } else { if (j != 0 ) { curr.set(j, dp.get(j - 1 ) + dp.get(j + 1 )); } else { curr.set(j, dp.get(j + 1 )); } } } // assigning values to iterate further dp = curr; } // return answer return dp.get( 0 ); } // driver code public static void main(String[] args) { int n = 3 ; // positions where opening braces // will be placed int pos[] = { 2 }; int k = pos.length; System.out.println(arrangeBraces(n, pos, k)); } } |
Python3
# Function to arrange braces given the number of pairs (n) and the positions of fixed braces (pos) def arrange_braces(n, pos): # Initialize an array to represent whether a brace is fixed at a particular position h = [ False ] * 1001 # Initialize an array to store the dynamic programming results for each position dp = [ 0 ] * 1001 # Mark the positions of fixed braces as True in the 'h' array for i in range ( len (pos)): h[pos[i]] = True # Initialize the dynamic programming array for the starting position dp[ 0 ] = 1 # Iterate through each position in the sequence of braces for i in range ( 1 , 2 * n + 1 ): # Create a temporary array to store the updated dynamic programming values for the current position curr = [ 0 ] * 1001 # Iterate through each possible state at the current position for j in range ( 2 * n + 1 ): # Check if the current position has a fixed brace if h[i]: # If the current position has a fixed brace, update the value based on the previous position if j ! = 0 : curr[j] = dp[j - 1 ] else : curr[j] = 0 else : # If the current position does not have a fixed brace, update the value based on both previous and next positions if j ! = 0 : curr[j] = dp[j - 1 ] + dp[j + 1 ] else : curr[j] = dp[j + 1 ] # Update the dynamic programming array with the values for the current position dp = curr # Return the final result, representing the number of ways to arrange the braces return dp[ 0 ] # Driver function if __name__ = = "__main__" : # Example with n=3 pairs of braces and a fixed brace at position 2 n = 3 pos = [ 2 ] print (arrange_braces(n, pos)) |
C#
using System; public class BracketArrangement { const int N = 1000; // Function to calculate the number // of proper bracket sequence static long ArrangeBraces( int n, int [] pos, int k) { // Hash array to mark the positions of opening brackets bool [] h = new bool [N]; // Vector to keep track of the previous row of DP int [] dp = new int [N + 1]; Array.Fill(h, false ); // Mark positions in hash array for ( int i = 0; i < k; i++) { h[pos[i]] = true ; } // First position marked as 1 dp[0] = 1; // Iterate and formulate the recurrences for ( int i = 1; i <= 2 * n; i++) { // Value of the current row of DP int [] curr = new int [N + 1]; for ( int j = 0; j <= 2 * n; j++) { // If position has an opening bracket if (h[i]) { if (j != 0) curr[j] = dp[j - 1]; else curr[j] = 0; } else { if (j != 0) curr[j] = dp[j - 1] + dp[j + 1]; else curr[j] = dp[j + 1]; } } // Assigning values to iterate further dp = curr; } // Return answer return dp[0]; } // Driver code static void Main() { int n = 3; // Positions where opening braces will be placed int [] pos = { 2 }; int k = pos.Length; Console.WriteLine(ArrangeBraces(n, pos, k)); } } |
Javascript
// Function to arrange braces given the number of pairs (n) and the positions of fixed braces (pos) function arrangeBraces(n, pos) { // Initialize an array to represent whether a brace is fixed at a particular position let h = new Array(1001).fill( false ); // Initialize an array to store the dynamic programming results for each position let dp = new Array(1001).fill(0); // Mark the positions of fixed braces as true in the 'h' array pos.forEach(p => { h[p] = true ; }); // Initialize the dynamic programming array for the starting position dp[0] = 1; // Iterate through each position in the sequence of braces for (let i = 1; i <= 2 * n; i++) { // Create a temporary array to store the updated dynamic programming values for the current position let curr = new Array(1001).fill(0); // Iterate through each possible state at the current position for (let j = 0; j <= 2 * n; j++) { // Check if the current position has a fixed brace if (h[i]) { // If the current position has a fixed brace, update the value based on the previous position curr[j] = (j !== 0) ? dp[j - 1] : 0; } else { // If the current position does not have a fixed brace, update the value based on both previous and next positions curr[j] = (j !== 0) ? dp[j - 1] + dp[j + 1] : dp[j + 1]; } } // Update the dynamic programming array with the values for the current position dp = curr; } // Return the final result, representing the number of ways to arrange the braces return dp[0]; } // Driver function let n = 3; let pos = [2]; console.log(arrangeBraces(n, pos)); // This code is contributed by Dwaipayan Bandyopadhyay |
3
Time complexity: O(N^2)
Auxiliary Space: O(N)