Balanced Parentheses

Balanced Parentheses: Balanced parentheses refer to an expression where each opening parenthesis has a corresponding closing parenthesis and they are correctly nested. For example, "(())", "{[]}", and "(({}[]))" are examples of balanced parentheses.

Now, let's solve a question "Valid Parentheses" using the concept of balanced parentheses.

Problem: Given a string containing only parentheses - '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

Here's the solution code in Python with proper comments explaining each step:

def is_valid_parentheses(s):
    stack = []  # Create an empty stack to store opening parentheses
    
    # Define a dictionary to map opening parentheses to their respective closing parentheses
    parentheses_map = {
        ')': '(',
        '}': '{',
        ']': '['
    }
    
    for char in s:
        if char in parentheses_map.values():
            # If the character is an opening parenthesis, push it onto the stack
            stack.append(char)
        elif char in parentheses_map.keys():
            # If the character is a closing parenthesis, check if it matches the top element of the stack
            if not stack or stack[-1] != parentheses_map[char]:
                # If the stack is empty or the top element doesn't match, the parentheses are not valid
                return False
            else:
                # If the parentheses match, pop the top element from the stack
                stack.pop()
    
    # After iterating through all characters, the parentheses are valid if the stack is empty
    return len(stack) == 0

In this code, we use a list stack as a stack to store the opening parentheses encountered in the input string s.

We also define a dictionary parentheses_map that maps each closing parenthesis to its respective opening parenthesis. This mapping will be used to check if a closing parenthesis matches the top element of the stack.

We iterate through each character in the input string s. If the character is an opening parenthesis, we push it onto the stack. If the character is a closing parenthesis, we check if it matches the top element of the stack. If they match, we pop the top element from the stack. If they don't match or the stack is empty, we return False as the parentheses are not valid.

After iterating through all the characters, we check if the stack is empty. If it is empty, it means all the parentheses are matched correctly, and we return True. Otherwise, we return False.

Time and Space Complexity

The time complexity of the is_valid_parentheses function is O(n), where n is the length of the input string s. We iterate through each character in s, and the operations performed in each iteration take constant time.

The space complexity of the implementation is O(n) in the worst case. This occurs when all the parentheses in s are opening parentheses, and they are pushed onto the stack.