Terrain Elevation Match - 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 string terrain where each character is either 'I' or 'D', representing the relationship between consecutive elevations.
• Q: What is the output?
  • A: The output is a list of integers representing a valid elevation sequence that matches the given terrain string.
• Q: How is the elevation sequence determined?
  • A: Start with the smallest and largest possible elevations, and assign them based on whether the current terrain character is 'I' (increasing) or 'D' (decreasing).

P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Use two pointers, low and high, to track the smallest and largest remaining elevations. Iterate through the terrain string and construct the elevation sequence by assigning the appropriate value based on whether the terrain is increasing or decreasing.

1. Initialize two pointers, `low` to 0 and `high` to `len(terrain)`.
2. Initialize an empty list `elevation` to store the elevation sequence.
3. Iterate through the `terrain` string:
   1. If the current character is `'I'`, append `low` to `elevation` and increment `low`.
   2. If the current character is `'D'`, append `high` to `elevation` and decrement `high`.
4. After processing all characters in `terrain`, append the final remaining value (either `low` or `high` since they should be equal) to `elevation`.
5. Return the `elevation` list.

⚠️ Common Mistakes

• Forgetting to append the final remaining value after processing the entire terrain string.
• Mismanaging the low and high pointers, leading to incorrect elevation sequences.
• Not accounting for all characters in the terrain string, which could result in incomplete sequences.

I-mplement

def terrain_elevation_match(terrain):
    low, high = 0, len(terrain)
    elevation = []

    for char in terrain:
        if char == 'I':
            elevation.append(low)
            low += 1
        else:
            elevation.append(high)
            high -= 1

    elevation.append(low)  # or high, as low and high should be equal here
    return elevation

# Example usage
print(terrain_elevation_match("IDID"))  # Output: [0, 4, 1, 3, 2]
print(terrain_elevation_match("III"))   # Output: [0, 1, 2, 3]