Dream Corridor Design - 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 list of integers segments, where each integer represents the width of a segment of the corridor.
• Q: What is the output?
  • A: The output is an integer representing the maximum possible area that can be achieved by selecting two segments.
• Q: How is the area calculated?
  • A: The area is defined as the minimum width of the two selected segments multiplied by the distance between them (i.e., the number of segments between the two selected segments, inclusive).

P-lan

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

• Forgetting to move the pointers correctly based on the segment widths.
• Not correctly calculating the area by using the minimum of the two segments.

I-mplement

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