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.
dreams
, representing a sequence of dream elements.dreams
. If no greater element exists, return -1
for that element.Plan the solution with appropriate visualizations and pseudocode.
General Idea: Use a stack to keep track of indices of elements for which the next greater element has not been found. Iterate through the list twice (simulating the circular nature) and update the result for each element when a greater element is found.
1. Initialize a list `result` of the same length as `dreams`, filled with `-1`.
2. Initialize an empty stack to store indices of elements.
3. Iterate over the sequence twice (using modulo to simulate the circular nature):
1. For each element, check if it is greater than the element at the index stored on top of the stack.
2. If it is, pop the index from the stack and set `result` at that index to the current element.
3. If the current index is within the original list length (not during the second pass), push the current index onto the stack.
4. Return the `result` list.
⚠️ Common Mistakes
-1
is properly retained.def next_greater_dream(dreams):
n = len(dreams)
result = [-1] * n
stack = []
for i in range(2 * n):
while stack and dreams[stack[-1]] < dreams[i % n]:
result[stack.pop()] = dreams[i % n]
if i < n:
stack.append(i)
return result
# Example usage
print(next_greater_dream([1, 2, 1])) # Output: [2, -1, 2]
print(next_greater_dream([1, 2, 3, 4, 3])) # Output: [2, 3, 4, -1, 4]