TIP102 Unit 3 Session 2 Standard (Click for link to problem statements)
Understand what the interviewer is asking for by using test cases and questions about the problem.
terrain
, where 0
represents a valley and 1
represents a hill.0
s) and hills (1
s), with all valleys and hills grouped consecutively.0
s and 1
s, and all 0
s must appear before all 1
s (or vice versa) within the subsection.Plan the solution with appropriate visualizations and pseudocode.
General Idea: Traverse the terrain string and count consecutive groups of 0
s and 1
s. 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
curr_count
after switching from 0
s to 1
s (or vice versa).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