Time to Complete Each Dream 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 an array design_times, where each element represents the number of days required to complete a particular design.
• Q: What is the output?
  • A: The output is an array answer, where answer[i] represents the number of days you must wait after the i-th design until a more complex design (one that takes more days) begins. If no such design exists, answer[i] is 0.
• Q: How do you determine the waiting days?
  • A: For each design, you need to find the first subsequent design that takes more time to complete than the current one. The difference in their positions in the array gives the waiting days.

P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Use a stack to keep track of the indices of the designs in decreasing order of their completion times. For each design, check if there is a later design that takes more time to complete. If there is, calculate the difference in days and update the answer.

1. Initialize an array `answer` of the same length as `design_times`, filled with `0`.
2. Initialize an empty stack to store indices of designs.
3. Iterate through the `design_times` array:
   1. While the stack is not empty and the current design takes more time than the design at the index stored on top of the stack:
       - Pop the index from the stack.
       - Calculate the difference between the current index and the popped index.
       - Store this difference in `answer` at the popped index.
   2. Push the current index onto the stack.
4. Return the `answer` array.

⚠️ Common Mistakes

• Forgetting to update the answer array for designs with no subsequent more complex designs.
• Incorrectly calculating the waiting days by not properly managing the stack.

I-mplement

def time_to_complete_dream_designs(design_times):
    n = len(design_times)
    answer = [0] * n
    stack = []

    for i in range(n):
        while stack and design_times[i] > design_times[stack[-1]]:
            prev_index = stack.pop()
            answer[prev_index] = i - prev_index
        stack.append(i)

    return answer

# Example usage
print(time_to_complete_dream_designs([3, 4, 5, 2, 1, 6, 7, 3]))  # Output: [1, 1, 3, 2, 1, 1, 0, 0]
print(time_to_complete_dream_designs([2, 3, 1, 4]))  # Output: [1, 2, 1, 0]
print(time_to_complete_dream_designs([5, 5, 5, 5]))  # Output: [0, 0, 0, 0]