Find the users with the most total steps who missed no day
A step-count contest runs over several days. statistics[d] lists {userID, steps} entries for day d. Return the IDs of the users with the highest total steps among only those who appeared on every day, plus that total.
Constraints:
- A user who skipped any day is ineligible, regardless of total.
- There may be several winners (a tie) or none (empty input → empty result).
- Aim for one pass; do not use a nested membership scan or a sort.
type Entry struct {
UserID int
Steps int
}
type Result struct {
UserIDs []int
Steps int
}
func champions(statistics [][]Entry) Result {
// your code here
}Write the implementation.
Seed a map userID → {daysIn, stepsSum} from day 0 only — anyone not present on day 0 can never appear on every day. For each later day, increment daysIn and stepsSum only for users already in the map. Then over the map, keep users whose daysIn == len(statistics), find the max stepsSum among them, and collect every user matching that max. Empty input returns an empty Result.
- ✗Adding new users from later days, who cannot have been present on every day
- ✗Using a nested membership scan instead of a single accumulation pass
- ✗Returning one winner instead of collecting all tied maxima
- →Why is seeding from day 0 the key to avoiding a membership scan?
- →What is the time complexity in terms of the total number of entries?
Solution
func champions(statistics [][]Entry) Result {
if len(statistics) == 0 {
return Result{}
}
type acc struct {
daysIn int
stepsSum int
}
candidates := make(map[int]*acc)
// Day 0 sets the candidate pool: never add new users later.
for _, e := range statistics[0] {
candidates[e.UserID] = &acc{daysIn: 1, stepsSum: e.Steps}
}
// Later days: increment only already-known users.
for d := 1; d < len(statistics); d++ {
for _, e := range statistics[d] {
if a, ok := candidates[e.UserID]; ok {
a.daysIn++
a.stepsSum += e.Steps
}
}
}
total := len(statistics)
maxSteps := -1
for _, a := range candidates {
if a.daysIn == total && a.stepsSum > maxSteps {
maxSteps = a.stepsSum
}
}
if maxSteps < 0 {
return Result{}
}
var winners []int
for id, a := range candidates {
if a.daysIn == total && a.stepsSum == maxSteps {
winners = append(winners, id)
}
}
return Result{UserIDs: winners, Steps: maxSteps}
}Complexity. A single pass over all entries — O(N) where N is the total entry count; O(K) memory for the day-0 candidates. No nested membership scan and no sort.
Key idea. A winner must appear on every day, hence on day 0. Seeding the map from day 0 means you never add new users — which is exactly what removes the quadratic "was this user present that day" check.
