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 each character is either 'I'
or 'D'
, representing the relationship between consecutive elevations.terrain
string.'I'
(increasing) or 'D'
(decreasing).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
terrain
string.low
and high
pointers, leading to incorrect elevation sequences.terrain
string, which could result in incomplete sequences.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]