Problem Description

Given a list of people, each with a name, gender (either "male" or "female"), and a score (integer), compute the running total (cumulative sum) of scores for each gender as you iterate through the list in order. The result should be a list where each entry contains the person's name, gender, score, and the running total of scores so far for that person's gender up to and including that entry.

Constraints:

• Each entry in the input list is a dictionary/object or record with fields name, gender, and score.
• The order of the list must be preserved in the output.
• For each person, the running total is the sum of all score values for people of the same gender encountered so far (including the current person).
• Do not reuse or skip elements; process the list in order.

Thought Process

Initially, we might consider recalculating the sum for each gender every time we process a new person. However, that would be inefficient, especially for large lists, as it would require repeatedly traversing the list for each entry.

Instead, a more efficient approach is to keep a running tally for each gender as we process the list. This way, when we process a new person, we simply add their score to the current total for their gender and record the result. This approach ensures we only need a single pass through the list and constant-time updates per entry.

The key insight is to maintain a mapping from gender to its current running total, updating it as we go.

Solution Approach

The algorithm can be broken down into the following steps:

1. Initialize a data structure (such as a dictionary or map) to store the running total for each gender.
2. Iterate through the list of people in order.
3. For each person:
   • Look up the current running total for their gender (default to 0 if not present).
   • Add their score to the running total for their gender.
   • Record the person's data along with the updated running total for their gender.
4. Return the new list with the additional running total field for each entry.

We use a map/dictionary for gender because lookups and updates are O(1), making the process efficient even for large lists.

Example Walkthrough

Suppose the input is:

• {name: "Alice", gender: "female", score: 5}
• {name: "Bob", gender: "male", score: 3}
• {name: "Carol", gender: "female", score: 7}
• {name: "Dan", gender: "male", score: 2}

1. Alice (female): previous total = 0, new total = 0+5=5
   Output: {name: "Alice", gender: "female", score: 5, running_total: 5}
2. Bob (male): previous total = 0, new total = 0+3=3
   Output: {name: "Bob", gender: "male", score: 3, running_total: 3}
3. Carol (female): previous total = 5, new total = 5+7=12
   Output: {name: "Carol", gender: "female", score: 7, running_total: 12}
4. Dan (male): previous total = 3, new total = 3+2=5
   Output: {name: "Dan", gender: "male", score: 2, running_total: 5}

The result is a list of the same length, where each entry includes the running total for that gender up to that point.

Time and Space Complexity

Brute-force approach: For each person, if we recalculated the sum of scores for their gender by scanning all previous elements, this would be O(N^2) time, where N is the number of people.

Optimized approach: By maintaining a running total per gender in a dictionary/map:

• Time Complexity: O(N), since we process each person once and dictionary operations are O(1).
• Space Complexity: O(N) for the output list, plus O(1) for the running totals map (since the number of genders is constant and small).

Summary

The problem is elegantly solved by maintaining a running total for each gender as we process the list. By using a dictionary or map for quick updates, we achieve linear time complexity and preserve the input order. This approach avoids redundant calculations and demonstrates how a simple data structure can optimize a seemingly repetitive task.

Code Implementation

def running_total_by_gender(people):
    gender_totals = {}
    result = []
    for person in people:
        gender = person['gender']
        score = person['score']
        prev_total = gender_totals.get(gender, 0)
        new_total = prev_total + score
        gender_totals[gender] = new_total
        result.append({
            'name': person['name'],
            'gender': gender,
            'score': score,
            'running_total': new_total
        })
    return result
      

#include <vector>
#include <string>
#include <unordered_map>

struct Person {
    std::string name;
    std::string gender;
    int score;
};

struct PersonWithTotal {
    std::string name;
    std::string gender;
    int score;
    int running_total;
};

std::vector<PersonWithTotal> runningTotalByGender(const std::vector<Person>& people) {
    std::unordered_map<std::string, int> gender_totals;
    std::vector<PersonWithTotal> result;
    for (const auto& person : people) {
        int prev_total = gender_totals[person.gender];
        int new_total = prev_total + person.score;
        gender_totals[person.gender] = new_total;
        result.push_back({person.name, person.gender, person.score, new_total});
    }
    return result;
}
      

import java.util.*;

class Person {
    String name;
    String gender;
    int score;
    Person(String name, String gender, int score) {
        this.name = name;
        this.gender = gender;
        this.score = score;
    }
}

class PersonWithTotal {
    String name;
    String gender;
    int score;
    int running_total;
    PersonWithTotal(String name, String gender, int score, int running_total) {
        this.name = name;
        this.gender = gender;
        this.score = score;
        this.running_total = running_total;
    }
}

public List<PersonWithTotal> runningTotalByGender(List<Person> people) {
    Map<String, Integer> genderTotals = new HashMap<>();
    List<PersonWithTotal> result = new ArrayList<>();
    for (Person person : people) {
        int prevTotal = genderTotals.getOrDefault(person.gender, 0);
        int newTotal = prevTotal + person.score;
        genderTotals.put(person.gender, newTotal);
        result.add(new PersonWithTotal(person.name, person.gender, person.score, newTotal));
    }
    return result;
}
      

function runningTotalByGender(people) {
    const genderTotals = {};
    const result = [];
    for (const person of people) {
        const gender = person.gender;
        const score = person.score;
        const prevTotal = genderTotals[gender] || 0;
        const newTotal = prevTotal + score;
        genderTotals[gender] = newTotal;
        result.push({
            name: person.name,
            gender: gender,
            score: score,
            running_total: newTotal
        });
    }
    return result;
}