0478MediumArrayHash TableStringSorting

Busiest Three-Screen Trail

Tracked in this browser only

Trains the technique from

LeetCode 1152Analyze User Website Visit Pattern

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

An app's analytics log has one row per screen opening. Row i says that viewer viewer[i] opened screen screen[i] at clock reading moment[i]. The rows arrive in no particular order.

Put each viewer's own rows into increasing order of clock reading; when two of that viewer's rows share a reading, the one listed earlier in the input goes first. That gives every viewer a single ordered walk through the app.

A trail is a sequence of exactly three screen names. A viewer follows a trail when three rows can be picked out of their walk, at strictly increasing places in it, whose screen names spell the trail in order. The three places need not be next to each other, and the same screen name may appear more than once in a trail if the viewer opened that screen more than once. A viewer either follows a trail or does not; the number of different ways they could pick the rows makes no difference.

Return the trail followed by the greatest number of viewers, as a list of its three screen names. When several trails are followed by that many viewers, return the alphabetically smallest of them, comparing the three names in order.

Examples

Example 1

Input: viewer = ["ana", "ana", "ana", "bo", "bo", "bo"], moment = [5, 2, 9, 4, 1, 7], screen = ["cart", "dash", "help", "dash", "cart", "help"]
Output: ["cart", "dash", "help"]

Each of the two viewers follows exactly one trail, and the two trails differ, so both are followed by one viewer and the alphabetical rule settles it.

Example 2

Input: viewer = ["ana", "ana", "ana", "bo", "bo", "bo", "cy", "cy"], moment = [1, 2, 3, 1, 2, 3, 1, 2], screen = ["dash", "cart", "help", "dash", "cart", "help", "dash", "cart"]
Output: ["dash", "cart", "help"]

Two viewers walk the same three screens in the same order. The third viewer has only two rows in the log, so no trail is credited to them.

Example 3

Input: viewer = ["cy", "cy", "cy", "cy", "cy"], moment = [1, 2, 3, 4, 5], screen = ["feed", "feed", "cart", "feed", "cart"]
Output: ["cart", "feed", "cart"]

One viewer owns the whole log, so every trail they follow is followed by exactly one viewer and the alphabetically smallest of those trails is returned.

Constraints

3 <= viewer.length <= 50
1 <= viewer[i].length <= 10
moment.length == viewer.length
1 <= moment[i] <= 10^9
screen.length == viewer.length
1 <= screen[i].length <= 10
viewer[i] and screen[i] consist of lowercase English letters.
At least one viewer has three or more rows in the log.
All the triples [viewer[i], moment[i], screen[i]] are distinct.
Two rows of the same viewer may share a clock reading; the earlier row in the input then comes first.

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def busiest_trail(viewer: list[str], moment: list[int], screen: list[str]) -> list[str]:

Java

public List<String> busiestTrail(String[] viewer, int[] moment, String[] screen)

The intended approach

Time O(sum over viewers of C(m, 3)), so O(n^3) when one viewer owns the whole logSpace O(number of distinct trails)

Order the row indices by clock reading with the input position as the tie-break, then append screen names into a per-viewer walk so each walk comes out in the right order. For one viewer, list every choice of three places in their walk, put those trails into a set so a viewer is only ever credited once for the same trail, and add one to that trail's tally. Finally scan the tallies keeping the largest, and on equal tallies keep the smaller trail as a tuple, which compares name by name in order.

Pythonentry point: busiest_trail

from itertools import combinations


def busiest_trail(viewer, moment, screen):
    # time O(sum over viewers of C(m, 3)), which is O(n^3) when one viewer owns the log
    # space O(number of distinct trails)
    order = sorted(range(len(viewer)), key=lambda i: (moment[i], i))
    walk = {}
    for i in order:
        walk.setdefault(viewer[i], []).append(screen[i])
    followers = {}
    for path in walk.values():
        for trail in set(combinations(path, 3)):
            followers[trail] = followers.get(trail, 0) + 1
    best = None
    top = -1
    for trail in followers:
        count = followers[trail]
        if count > top or (count == top and trail < best):
            best = trail
            top = count
    return list(best)

The obvious version

Build each viewer's ordered walk, then try every trail that can be spelled from the screen names present, running the three names in alphabetical order across all three slots. For each candidate, test each walk by scanning it once and advancing through the three names greedily. Because candidates are generated in alphabetical order and only a strictly better count replaces the leader, the alphabetical tie-break falls out for free.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_busiest_trail(viewer, moment, screen):
    order = sorted(range(len(viewer)), key=lambda i: (moment[i], i))
    walk = {}
    for i in order:
        walk.setdefault(viewer[i], []).append(screen[i])
    names = sorted(set(screen))
    best = None
    top = -1
    for a in names:
        for b in names:
            for c in names:
                want = (a, b, c)
                hits = 0
                for path in walk.values():
                    at = 0
                    for name in path:
                        if name == want[at]:
                            at += 1
                            if at == 3:
                                break
                    if at == 3:
                        hits += 1
                if hits > top:
                    top = hits
                    best = want
    return list(best)

How this problem was checked

Reference solution executed against 9 test cases — 9 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in