Problem Statement
This problem asks us to count the number of valid parentheses expressions of length n.
A valid parentheses expression must satisfy:
Observation
A valid parentheses expression must contain:
Therefore:
n must be even
If n is odd:
Answer = 0
Example
n = 3
It is impossible to have an equal number of opening and closing brackets.
Therefore, no valid expression can be formed.
Relation to Catalan Numbers
Let:
n = 2k
Then the number of valid parentheses expressions is the k-th Catalan Number.
Example: k = 1
()
Count:
1
Example: k = 2
(())
()()
Count:
2
Example: k = 3
((()))
(()())
(())()
()(())
()()()
Count:
5
These values are exactly:
Catalan(1) = 1
Catalan(2) = 2
Catalan(3) = 5
Catalan Numbers
The nth Catalan Number is given by:
C_n=\frac{(2n)!}{(n+1)!\cdot n!}
For efficient computation, we can use:
C_n=\prod_{i=0}^{n-1}\frac{2(2i+1)}{i+2}
This avoids computing large factorials directly.
Algorithm
If n is odd, return 0.
Compute:
pairs = n / 2
Calculate:
Catalan(pairs)
Return the result.
Example
Input
n = 6
Number of Pairs
pairs = 3
Catalan(3)
5
Valid Expressions
((()))
(()())
(())()
()(())
()()()
Output
5
Java Solution
class Solution {
int findWays(int n) {
// Odd length can never form valid parentheses
if (n % 2 != 0) {
return 0;
}
int pairs = n / 2;
long catalan = 1;
for (int i = 0; i < pairs; i++) {
catalan = catalan * (2L * (2 * i + 1)) / (i + 2);
}
return (int) catalan;
}
}
Why This Works
The count of valid parentheses arrangements with k pairs of brackets is a well-known combinatorial result called the Catalan Number.
Since the string length is n:
k = n / 2
Therefore:
Answer = Catalan(n / 2)
when n is even.
If n is odd:
Answer = 0
because a valid parentheses sequence must contain equal numbers of opening and closing brackets.
Complexity Analysis
Time Complexity
O(n)
The Catalan number is computed using a single loop.
Space Complexity
O(1)
Only a few variables are used.
Pattern Recognition
Whenever you encounter problems involving:
Valid Parentheses Counting
Balanced Bracket Sequences
Number of Binary Search Trees
Mountain Ranges
Non-Crossing Handshakes
Polygon Triangulation
think of:
Catalan Numbers
These problems often share the same recursive and combinatorial structure.
Key Takeaway
The most important observation is that a valid parentheses string of length n must contain exactly n/2 pairs of brackets. The number of such balanced arrangements is given directly by the Catalan Number corresponding to n/2. Recognizing this pattern converts an exponential counting problem into a simple mathematical solution.
Summary
To count valid parentheses expressions of length n, first check whether n is even. If it is odd, the answer is 0. Otherwise, let pairs = n/2. The number of valid balanced parentheses sequences is exactly the Catalan Number for pairs, which can be computed efficiently in O(n) time and O(1) space using the multiplicative Catalan formula.