TIP102 Unit 3 Session 2 Advanced (Click for link to problem statements)
Understand what the interviewer is asking for by using test cases and questions about the problem.
segments
, where each integer represents the width of a segment of the corridor.Plan the solution with appropriate visualizations and pseudocode.
General Idea: Use a two-pointer approach to evaluate all possible pairs of segments from both ends of the list and calculate the area for each pair. Keep track of the maximum area encountered during the process.
1. Initialize two pointers: `left` at the beginning of the list and `right` at the end of the list.
2. Initialize a variable `max_area` to store the maximum area found.
3. While `left` is less than `right`:
1. Calculate the width between the `left` and `right` pointers.
2. Calculate the area as the minimum of the segment widths at `left` and `right` multiplied by the width.
3. Update `max_area` if the calculated area is larger than the current `max_area`.
4. If the segment at `left` is less than or equal to the segment at `right`, move `left` pointer one step to the right.
5. Otherwise, move the `right` pointer one step to the left.
4. Return `max_area` as the maximum possible area.
⚠️ Common Mistakes
def max_corridor_area(segments):
left, right = 0, len(segments) - 1
max_area = 0
while left < right:
width = right - left
area = min(segments[left], segments[right]) * width
max_area = max(max_area, area)
if segments[left] < segments[right]:
left += 1
else:
right -= 1
return max_area
# Example usage
print(max_corridor_area([1, 8, 6, 2, 5, 4, 8, 3, 7])) # Output: 49
print(max_corridor_area([1, 1])) # Output: 1