Count Balanced Terrain Subsections - codepath/compsci_guides GitHub Wiki

TIP102 Unit 3 Session 2 Standard (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 binary string terrain, where 0 represents a valley and 1 represents a hill.
• Q: What is the output?
  • A: The output is an integer representing the number of non-empty subsections of the terrain that have an equal number of valleys (0s) and hills (1s), with all valleys and hills grouped consecutively.
• Q: How are the balanced subsections identified?
  • A: A balanced subsection has an equal number of 0s and 1s, and all 0s must appear before all 1s (or vice versa) within the subsection.

P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Traverse the terrain string and count consecutive groups of 0s and 1s. Use these counts to determine how many balanced subsections can be formed.

1. Initialize an empty stack and a variable `count` to track the number of balanced subsections.
2. Initialize a variable `curr_count` to 1 to count consecutive characters.
3. Iterate over the `terrain` string starting from the second character:
   1. If the current character is the same as the previous one, increment `curr_count`.
   2. If the current character is different, compare `curr_count` with the top of the stack:
      * Add the minimum of the top of the stack and `curr_count` to `count`.
      * Push `curr_count` onto the stack.
      * Reset `curr_count` to 1.
4. After the loop, check if there is any remaining value in the stack and update `count`.
5. Return the final value of `count`.

⚠️ Common Mistakes

• Not properly resetting curr_count after switching from 0s to 1s (or vice versa).
• Failing to correctly manage the stack, leading to incorrect counting of balanced subsections.
• Forgetting to account for the last group of consecutive characters after the loop.

I-mplement

def count_balanced_terrain_subsections(terrain):
    stack = []
    count = 0
    curr_count = 1

    for i in range(1, len(terrain)):
        if terrain[i] == terrain[i - 1]:
            curr_count += 1
        else:
            if stack:
                count += min(stack.pop(), curr_count)
            stack.append(curr_count)
            curr_count = 1

    if stack:
        count += min(stack.pop(), curr_count)

    return count

# Example usage
print(count_balanced_terrain_subsections("00110011"))  # Output: 6
print(count_balanced_terrain_subsections("10101"))     # Output: 4