Dream Building Layout - codepath/compsci_guides GitHub Wiki

TIP102 Unit 3 Session 2 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 s of even length n, containing exactly n / 2 left walls '[' and n / 2 right walls ']'.
  • Q: What is the output?
    • A: The output is an integer representing the minimum number of swaps needed to make the building layout balanced.
  • Q: What defines a balanced layout?
    • A: A layout is balanced if it is an empty space, can be divided into two separate balanced layouts, or can be surrounded by left and right walls that balance each other out.

P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Track the imbalance between left and right walls as you iterate through the string. When the imbalance exceeds what is currently balanced, you will need to swap walls. The goal is to minimize the imbalance and determine the minimum number of swaps needed.

1. Initialize variables `imbalance` and `max_imbalance` to 0.
2. Iterate through each character in the string `s`:
   1. If the character is a left wall '[', decrease the `imbalance` by 1.
   2. If the character is a right wall ']', increase the `imbalance` by 1.
   3. Update `max_imbalance` to the maximum of `max_imbalance` and `imbalance`.
3. The minimum number of swaps required is given by `(max_imbalance + 1) // 2`.
4. Return the result.

⚠️ Common Mistakes

  • Misunderstanding the calculation of the imbalance and how it relates to the necessary swaps.
  • Incorrectly calculating the number of swaps by not considering the maximum imbalance correctly.

I-mplement

def min_swaps(s):
    imbalance = 0
    max_imbalance = 0

    for char in s:
        if char == '[':
            imbalance -= 1
        else:
            imbalance += 1

        max_imbalance = max(max_imbalance, imbalance)

    return (max_imbalance + 1) // 2

# Example usage
print(min_swaps("][]["))  # Output: 1
print(min_swaps("]]][[["))  # Output: 2
print(min_swaps("[]"))  # Output: 0