/*
Follow up 1 - Single Highest-Rated Similar Movie (k = 1)
PROBLEM:
Given movie ratings, an adjacency list of similar movies,
and a starting movie, return the highest-rated reachable
movie, excluding the starting movie.
Tie-breaker: Smaller movie ID wins.
Return -1 if no other movie is reachable.
APPROACH: BFS + TRACK BEST
1. Start BFS from the starting movie.
2. Use visited to avoid cycles and duplicate processing.
3. Maintain a variable "best" initialized to -1.
4. For each reachable movie (excluding start):
- Update best if its rating is higher.
- If ratings tie, prefer the smaller movie ID.
5. Continue BFS to explore all reachable movies.
6. Return best.
WHY NO MIN-HEAP OR SORTING?
- We need only one recommendation (k = 1).
- A single variable is sufficient to track the best movie.
- BFS is still necessary to discover all reachable movies.
TIME COMPLEXITY: O(V + E)
- BFS visits each reachable vertex once.
- Each outgoing edge is examined once.
- Comparing with best takes O(1).
SPACE COMPLEXITY: O(V)
- visited array: O(V)
- BFS queue: O(V)
- best variable: O(1)
*/
function highestRatedSimilarMovie(ratings, similar, start) {
const visited = Array(ratings.length).fill(false);
const q = [start];
let head = 0;
let best = -1;
visited[start] = true;
// STEP 1: BFS
while (head < q.length) {
const curr = q[head++];
// STEP 2: Update best (exclude starting movie)
if (curr !== start) {
if (
best === -1 ||
ratings[curr] > ratings[best] ||
(ratings[curr] === ratings[best] && curr < best)
) {
best = curr;
}
}
// STEP 3: Explore neighbors
for (const next of similar[curr]) {
if (!visited[next]) {
visited[next] = true;
q.push(next);
}
}
}
return best;
}
// ==========================================
// TEST CASES
// ==========================================
const tests = [
{
name: "Normal + unreachable highest rating",
ratings: [60, 80, 95, 90, 100],
similar: [[1, 2], [3], [], [], []],
start: 0,
expected: 2
},
{
name: "Rating ties - smaller ID wins",
ratings: [50, 95, 95, 80],
similar: [[2, 3], [], [1], []],
start: 0,
expected: 1
},
{
name: "Cycles + duplicates + self-loop",
ratings: [100, 20, 90, 90],
similar: [[0, 1, 1], [0, 2, 3], [1], []],
start: 0,
expected: 2
},
{
name: "No reachable movies",
ratings: [100, 90, 80],
similar: [[], [2], []],
start: 0,
expected: -1
}
];
for (const test of tests) {
const actual = highestRatedSimilarMovie(
test.ratings,
test.similar,
test.start
);
const passed = actual === test.expected;
console.log(`${passed ? "PASS" : "FAIL"} - ${test.name}`);
console.log("Expected:", test.expected);
console.log("Actual: ", actual);
console.log();
}
Ci8qCkZvbGxvdyB1cCAxIC0gU2luZ2xlIEhpZ2hlc3QtUmF0ZWQgU2ltaWxhciBNb3ZpZSAoayA9IDEpClBST0JMRU06CkdpdmVuIG1vdmllIHJhdGluZ3MsIGFuIGFkamFjZW5jeSBsaXN0IG9mIHNpbWlsYXIgbW92aWVzLAphbmQgYSBzdGFydGluZyBtb3ZpZSwgcmV0dXJuIHRoZSBoaWdoZXN0LXJhdGVkIHJlYWNoYWJsZQptb3ZpZSwgZXhjbHVkaW5nIHRoZSBzdGFydGluZyBtb3ZpZS4KClRpZS1icmVha2VyOiBTbWFsbGVyIG1vdmllIElEIHdpbnMuClJldHVybiAtMSBpZiBubyBvdGhlciBtb3ZpZSBpcyByZWFjaGFibGUuCgpBUFBST0FDSDogQkZTICsgVFJBQ0sgQkVTVAoKMS4gU3RhcnQgQkZTIGZyb20gdGhlIHN0YXJ0aW5nIG1vdmllLgoyLiBVc2UgdmlzaXRlZCB0byBhdm9pZCBjeWNsZXMgYW5kIGR1cGxpY2F0ZSBwcm9jZXNzaW5nLgozLiBNYWludGFpbiBhIHZhcmlhYmxlICJiZXN0IiBpbml0aWFsaXplZCB0byAtMS4KNC4gRm9yIGVhY2ggcmVhY2hhYmxlIG1vdmllIChleGNsdWRpbmcgc3RhcnQpOgogICAtIFVwZGF0ZSBiZXN0IGlmIGl0cyByYXRpbmcgaXMgaGlnaGVyLgogICAtIElmIHJhdGluZ3MgdGllLCBwcmVmZXIgdGhlIHNtYWxsZXIgbW92aWUgSUQuCjUuIENvbnRpbnVlIEJGUyB0byBleHBsb3JlIGFsbCByZWFjaGFibGUgbW92aWVzLgo2LiBSZXR1cm4gYmVzdC4KCldIWSBOTyBNSU4tSEVBUCBPUiBTT1JUSU5HPwotIFdlIG5lZWQgb25seSBvbmUgcmVjb21tZW5kYXRpb24gKGsgPSAxKS4KLSBBIHNpbmdsZSB2YXJpYWJsZSBpcyBzdWZmaWNpZW50IHRvIHRyYWNrIHRoZSBiZXN0IG1vdmllLgotIEJGUyBpcyBzdGlsbCBuZWNlc3NhcnkgdG8gZGlzY292ZXIgYWxsIHJlYWNoYWJsZSBtb3ZpZXMuCgpUSU1FIENPTVBMRVhJVFk6IE8oViArIEUpCi0gQkZTIHZpc2l0cyBlYWNoIHJlYWNoYWJsZSB2ZXJ0ZXggb25jZS4KLSBFYWNoIG91dGdvaW5nIGVkZ2UgaXMgZXhhbWluZWQgb25jZS4KLSBDb21wYXJpbmcgd2l0aCBiZXN0IHRha2VzIE8oMSkuCgpTUEFDRSBDT01QTEVYSVRZOiBPKFYpCi0gdmlzaXRlZCBhcnJheTogTyhWKQotIEJGUyBxdWV1ZTogTyhWKQotIGJlc3QgdmFyaWFibGU6IE8oMSkKKi8KCmZ1bmN0aW9uIGhpZ2hlc3RSYXRlZFNpbWlsYXJNb3ZpZShyYXRpbmdzLCBzaW1pbGFyLCBzdGFydCkgewogICAgY29uc3QgdmlzaXRlZCA9IEFycmF5KHJhdGluZ3MubGVuZ3RoKS5maWxsKGZhbHNlKTsKICAgIGNvbnN0IHEgPSBbc3RhcnRdOwogICAgbGV0IGhlYWQgPSAwOwogICAgbGV0IGJlc3QgPSAtMTsKCiAgICB2aXNpdGVkW3N0YXJ0XSA9IHRydWU7CgogICAgLy8gU1RFUCAxOiBCRlMKICAgIHdoaWxlIChoZWFkIDwgcS5sZW5ndGgpIHsKICAgICAgICBjb25zdCBjdXJyID0gcVtoZWFkKytdOwoKICAgICAgICAvLyBTVEVQIDI6IFVwZGF0ZSBiZXN0IChleGNsdWRlIHN0YXJ0aW5nIG1vdmllKQogICAgICAgIGlmIChjdXJyICE9PSBzdGFydCkgewogICAgICAgICAgICBpZiAoCiAgICAgICAgICAgICAgICBiZXN0ID09PSAtMSB8fAogICAgICAgICAgICAgICAgcmF0aW5nc1tjdXJyXSA+IHJhdGluZ3NbYmVzdF0gfHwKICAgICAgICAgICAgICAgIChyYXRpbmdzW2N1cnJdID09PSByYXRpbmdzW2Jlc3RdICYmIGN1cnIgPCBiZXN0KQogICAgICAgICAgICApIHsKICAgICAgICAgICAgICAgIGJlc3QgPSBjdXJyOwogICAgICAgICAgICB9CiAgICAgICAgfQoKICAgICAgICAvLyBTVEVQIDM6IEV4cGxvcmUgbmVpZ2hib3JzCiAgICAgICAgZm9yIChjb25zdCBuZXh0IG9mIHNpbWlsYXJbY3Vycl0pIHsKICAgICAgICAgICAgaWYgKCF2aXNpdGVkW25leHRdKSB7CiAgICAgICAgICAgICAgICB2aXNpdGVkW25leHRdID0gdHJ1ZTsKICAgICAgICAgICAgICAgIHEucHVzaChuZXh0KTsKICAgICAgICAgICAgfQogICAgICAgIH0KICAgIH0KCiAgICByZXR1cm4gYmVzdDsKfQoKLy8gPT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09Ci8vIFRFU1QgQ0FTRVMKLy8gPT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09Cgpjb25zdCB0ZXN0cyA9IFsKICAgIHsKICAgICAgICBuYW1lOiAiTm9ybWFsICsgdW5yZWFjaGFibGUgaGlnaGVzdCByYXRpbmciLAogICAgICAgIHJhdGluZ3M6IFs2MCwgODAsIDk1LCA5MCwgMTAwXSwKICAgICAgICBzaW1pbGFyOiBbWzEsIDJdLCBbM10sIFtdLCBbXSwgW11dLAogICAgICAgIHN0YXJ0OiAwLAogICAgICAgIGV4cGVjdGVkOiAyCiAgICB9LAogICAgewogICAgICAgIG5hbWU6ICJSYXRpbmcgdGllcyAtIHNtYWxsZXIgSUQgd2lucyIsCiAgICAgICAgcmF0aW5nczogWzUwLCA5NSwgOTUsIDgwXSwKICAgICAgICBzaW1pbGFyOiBbWzIsIDNdLCBbXSwgWzFdLCBbXV0sCiAgICAgICAgc3RhcnQ6IDAsCiAgICAgICAgZXhwZWN0ZWQ6IDEKICAgIH0sCiAgICB7CiAgICAgICAgbmFtZTogIkN5Y2xlcyArIGR1cGxpY2F0ZXMgKyBzZWxmLWxvb3AiLAogICAgICAgIHJhdGluZ3M6IFsxMDAsIDIwLCA5MCwgOTBdLAogICAgICAgIHNpbWlsYXI6IFtbMCwgMSwgMV0sIFswLCAyLCAzXSwgWzFdLCBbXV0sCiAgICAgICAgc3RhcnQ6IDAsCiAgICAgICAgZXhwZWN0ZWQ6IDIKICAgIH0sCiAgICB7CiAgICAgICAgbmFtZTogIk5vIHJlYWNoYWJsZSBtb3ZpZXMiLAogICAgICAgIHJhdGluZ3M6IFsxMDAsIDkwLCA4MF0sCiAgICAgICAgc2ltaWxhcjogW1tdLCBbMl0sIFtdXSwKICAgICAgICBzdGFydDogMCwKICAgICAgICBleHBlY3RlZDogLTEKICAgIH0KXTsKCmZvciAoY29uc3QgdGVzdCBvZiB0ZXN0cykgewogICAgY29uc3QgYWN0dWFsID0gaGlnaGVzdFJhdGVkU2ltaWxhck1vdmllKAogICAgICAgIHRlc3QucmF0aW5ncywKICAgICAgICB0ZXN0LnNpbWlsYXIsCiAgICAgICAgdGVzdC5zdGFydAogICAgKTsKCiAgICBjb25zdCBwYXNzZWQgPSBhY3R1YWwgPT09IHRlc3QuZXhwZWN0ZWQ7CgogICAgY29uc29sZS5sb2coYCR7cGFzc2VkID8gIlBBU1MiIDogIkZBSUwifSAtICR7dGVzdC5uYW1lfWApOwogICAgY29uc29sZS5sb2coIkV4cGVjdGVkOiIsIHRlc3QuZXhwZWN0ZWQpOwogICAgY29uc29sZS5sb2coIkFjdHVhbDogICIsIGFjdHVhbCk7CiAgICBjb25zb2xlLmxvZygpOwp9Cg==