Running Sum - codepath/compsci_guides GitHub Wiki

TIP102 Unit 1 Session 1 Standard (Click for link to problem statements)

Problem Highlights

• 💡 Difficulty: Easy
• ⏰ Time to complete: 5 mins
• 🛠️ Topics: Lists, In-place Modification, Iteration

U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

• Q: What does the function need to return?

  • A: The function modifies the list in place to reflect the running sum of crimes stopped each month.

• Q: Can I create a new list to store the running sum?

  • A: No, the problem explicitly states that the list must be modified in place, and no new lists can be created.

• Q: What is the expected input format?

  • A: A list of integers representing the number of crimes stopped by Batman each month.

• Q: What should be returned by the function?

  • A: The function does not return anything; it modifies the input list in place.

• The function running_sum() should take a list of integers superhero_stats and modify it in place to return the running sum. The modified list should reflect the cumulative sum such that superhero_stats[i] = sum(superhero_stats[0]...superhero_stats[i]).

HAPPY CASE
Input: [1, 2, 3, 4]
Expected Output: [1, 3, 6, 10]

Input: [1, 1, 1, 1, 1]
Expected Output: [1, 2, 3, 4, 5]

EDGE CASE
Input: [3, 1, 2, 10, 1]
Expected Output: [3, 4, 6, 16, 17]
    
Input: [] (empty list)
Expected Output: []

P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Iterate through the list starting from the second element and modify each element to include the sum of itself and the previous element.

1. Define the function `running_sum(superhero_stats)`.
2. If the list is empty, return immediately.
3. Iterate through the list starting from index 1.
4. Update the current element by adding the previous element to it.

⚠️ Common Mistakes

• Forgetting to handle the case of an empty list.
• Modifying the list incorrectly or creating a new list instead of modifying in place.

I-mplement

Implement the code to solve the algorithm.

def running_sum(superhero_stats):
    # Iterate through the list starting from the second element
    for i in range(1, len(superhero_stats)):
        # Update the current element to be the sum of itself and the previous element
        superhero_stats[i] += superhero_stats[i - 1]