Minimum Changes to Make Schedule Balanced - codepath/compsci_guides GitHub Wiki

TIP102 Unit 3 Session 1 Advanced (Click for link to problem statements)

U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

• Q: What is the input to the problem?
  • A: The input is a string schedule consisting of opening and closing parentheses representing events.
• Q: What is the output?
  • A: The output is the minimum number of moves required to make the schedule balanced.
• Q: What does it mean for the schedule to be balanced?
  • A: A balanced schedule means every opening parenthesis ( has a corresponding closing parenthesis ).

P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Use a stack to keep track of unmatched opening parentheses and a counter to track unmatched closing parentheses. The total number of unmatched parentheses (both opening and closing) will give the minimum number of changes required.

1. Initialize an empty stack to keep track of unmatched opening parentheses `(`.
2. Initialize a counter `close_needed` to keep track of unmatched closing parentheses `)`.
3. Iterate through each character in the `schedule` string:
   1. If the character is an opening parenthesis `(`, push it onto the stack.
   2. If the character is a closing parenthesis `)`:
      * If the stack is not empty, pop an opening parenthesis from the stack (this matches the closing parenthesis).
      * If the stack is empty, increment the `close_needed` counter (this indicates a closing parenthesis without a matching opening parenthesis).
4. After iterating through the string, the stack will contain unmatched opening parentheses, and `close_needed` will represent unmatched closing parentheses.
5. The minimum number of moves required to balance the schedule is the sum of the length of the stack and the `close_needed` counter.
6. Return the total number of moves.

⚠️ Common Mistakes

• Not correctly identifying unmatched opening and closing parentheses.
• Forgetting to account for both unmatched opening and closing parentheses in the final count.
• Misinterpreting the conditions for a balanced schedule.

I-mplement

def min_changes_to_make_balanced(schedule):
    stack = []
    close_needed = 0
    
    for ch in schedule:
        if ch == '(':
            stack.append(ch)  # Push the opening parenthesis onto the stack
        elif ch == ')':
            if stack:
                stack.pop()  # Pop the stack if there's an unmatched '('
            else:
                close_needed += 1  # No matching '(', so we need an extra ')'
    
    # The remaining items in the stack are unmatched '(' that need a ')'
    return len(stack) + close_needed

# Example usage
print(min_changes_to_make_balanced("())"))   # Output: 1
print(min_changes_to_make_balanced("((("))   # Output: 3