/*
PROBLEM:
Given:
- ratings[i]: Rating of movie i
- titles[i]: Title of movie i
- similar[i]: List of movies similar to movie i
- start: Starting movie
- k: Number of recommendations
Return up to K highest-rated reachable movies.
RULES:
1. Exclude the starting movie.
2. Higher rating comes first.
3. If ratings tie, lexicographically smaller title comes first.
4. If titles also tie, smaller movie ID comes first.
5. Avoid duplicate movies and handle cycles.
APPROACH: BFS + SORTING
1. Start BFS from the starting movie.
2. Use visited to avoid processing movies multiple times.
3. Collect all reachable movies except start.
4. Sort candidates:
- Rating descending
- Title ascending (using custom compareTitles)
- Movie ID ascending if both rating and title match
5. Return the first K movie IDs.
CUSTOM STRING COMPARISON:
1. Compare both titles character by character.
2. At the first different character:
- Smaller character comes first.
3. If all compared characters match:
- Shorter title comes first.
4. Return 0 if both titles are identical.
TIME COMPLEXITY:
O(V + E + R * log(R) * L)
V = number of movies
E = number of similarity edges
R = number of reachable movies excluding start
L = maximum movie title length
- BFS: O(V + E)
- compareTitles: O(L)
- Sorting: O(R log R * L)
SPACE COMPLEXITY:
O(V + R) auxiliary space, excluding sort internals.
- visited: O(V)
- BFS queue: O(V)
- candidates: O(R)
- compareTitles: O(1)
- Sorting may use additional implementation-dependent space.
*/
// ==========================================
// CUSTOM LEXICOGRAPHICAL COMPARISON
// ==========================================
function compareTitles(str1, str2) {
const minLen = Math.min(str1.length, str2.length);
// Compare characters one by one
for (let i = 0; i < minLen; i++) {
if (str1[i] < str2[i]) return -1;
if (str1[i] > str2[i]) return 1;
}
// If one title is a prefix of the other,
// the shorter title comes first.
if (str1.length < str2.length) return -1;
if (str1.length > str2.length) return 1;
// Both titles are identical
return 0;
}
// ==========================================
// SOLUTION: BFS + SORTING
// ==========================================
function topRatedSimilarMovies(
ratings, titles, similar, start, k
) {
if (k === 0) return [];
const visited = Array(ratings.length).fill(false);
const q = [start];
let head = 0;
const candidates = [];
visited[start] = true;
// STEP 1: BFS to find all reachable movies
while (head < q.length) {
const curr = q[head++];
// STEP 2: Explore neighboring movies
for (const next of similar[curr]) {
if (!visited[next]) {
visited[next] = true;
q.push(next);
// Exclude start (already marked visited)
candidates.push(next);
}
}
}
// STEP 3: Sort by rating, title, then ID
candidates.sort((a, b) => {
// Higher rating first
if (ratings[a] !== ratings[b]) {
return ratings[b] - ratings[a];
}
// Alphabetical title order
const titleComparison = compareTitles(
titles[a], titles[b]
);
if (titleComparison !== 0) {
return titleComparison;
}
// Same rating and same title:
// Smaller movie ID first
return a - b;
});
// STEP 4: Return top K movie IDs
return candidates.slice(0, k);
}
// ==========================================
// TEST CASES (IDEONE-READY)
// ==========================================
const tests = [
{
name: "Normal + alphabetical rating ties",
ratings: [80, 95, 95, 90],
titles: [
"Avatar",
"Titanic",
"Inception",
"Interstellar"
],
similar: [[1, 2, 3], [], [], []],
start: 0,
k: 2,
expected: [2, 1]
},
{
name: "Same rating and same title - smaller ID",
ratings: [50, 90, 90, 90],
titles: ["Start", "Avatar", "Avatar", "Batman"],
similar: [[2, 3, 1], [], [], []],
start: 0,
k: 3,
expected: [1, 2, 3]
},
{
name: "Cycles + duplicate edges + prefix titles",
ratings: [100, 95, 95, 95, 999],
titles: ["Start", "Avatar", "Av", "Avengers", "Other"],
similar: [
[1, 1, 2],
[0, 3],
[1],
[3],
[]
],
start: 0,
k: 3,
expected: [2, 1, 3]
},
{
name: "No reachable movies",
ratings: [100, 90],
titles: ["Start", "Avatar"],
similar: [[], []],
start: 0,
k: 1,
expected: []
}
];
for (const test of tests) {
const actual = topRatedSimilarMovies(
test.ratings,
test.titles,
test.similar,
test.start,
test.k
);
const passed =
JSON.stringify(actual) === JSON.stringify(test.expected);
console.log(
`${passed ? "PASS" : "FAIL"} - ${test.name}`
);
console.log("Expected:", JSON.stringify(test.expected));
console.log("Actual: ", JSON.stringify(actual));
console.log();
}
Ci8qClBST0JMRU06CkdpdmVuOgotIHJhdGluZ3NbaV06IFJhdGluZyBvZiBtb3ZpZSBpCi0gdGl0bGVzW2ldOiBUaXRsZSBvZiBtb3ZpZSBpCi0gc2ltaWxhcltpXTogTGlzdCBvZiBtb3ZpZXMgc2ltaWxhciB0byBtb3ZpZSBpCi0gc3RhcnQ6IFN0YXJ0aW5nIG1vdmllCi0gazogTnVtYmVyIG9mIHJlY29tbWVuZGF0aW9ucwoKUmV0dXJuIHVwIHRvIEsgaGlnaGVzdC1yYXRlZCByZWFjaGFibGUgbW92aWVzLgoKUlVMRVM6CjEuIEV4Y2x1ZGUgdGhlIHN0YXJ0aW5nIG1vdmllLgoyLiBIaWdoZXIgcmF0aW5nIGNvbWVzIGZpcnN0LgozLiBJZiByYXRpbmdzIHRpZSwgbGV4aWNvZ3JhcGhpY2FsbHkgc21hbGxlciB0aXRsZSBjb21lcyBmaXJzdC4KNC4gSWYgdGl0bGVzIGFsc28gdGllLCBzbWFsbGVyIG1vdmllIElEIGNvbWVzIGZpcnN0Lgo1LiBBdm9pZCBkdXBsaWNhdGUgbW92aWVzIGFuZCBoYW5kbGUgY3ljbGVzLgoKQVBQUk9BQ0g6IEJGUyArIFNPUlRJTkcKCjEuIFN0YXJ0IEJGUyBmcm9tIHRoZSBzdGFydGluZyBtb3ZpZS4KMi4gVXNlIHZpc2l0ZWQgdG8gYXZvaWQgcHJvY2Vzc2luZyBtb3ZpZXMgbXVsdGlwbGUgdGltZXMuCjMuIENvbGxlY3QgYWxsIHJlYWNoYWJsZSBtb3ZpZXMgZXhjZXB0IHN0YXJ0Lgo0LiBTb3J0IGNhbmRpZGF0ZXM6CiAgIC0gUmF0aW5nIGRlc2NlbmRpbmcKICAgLSBUaXRsZSBhc2NlbmRpbmcgKHVzaW5nIGN1c3RvbSBjb21wYXJlVGl0bGVzKQogICAtIE1vdmllIElEIGFzY2VuZGluZyBpZiBib3RoIHJhdGluZyBhbmQgdGl0bGUgbWF0Y2gKNS4gUmV0dXJuIHRoZSBmaXJzdCBLIG1vdmllIElEcy4KCkNVU1RPTSBTVFJJTkcgQ09NUEFSSVNPTjoKMS4gQ29tcGFyZSBib3RoIHRpdGxlcyBjaGFyYWN0ZXIgYnkgY2hhcmFjdGVyLgoyLiBBdCB0aGUgZmlyc3QgZGlmZmVyZW50IGNoYXJhY3RlcjoKICAgLSBTbWFsbGVyIGNoYXJhY3RlciBjb21lcyBmaXJzdC4KMy4gSWYgYWxsIGNvbXBhcmVkIGNoYXJhY3RlcnMgbWF0Y2g6CiAgIC0gU2hvcnRlciB0aXRsZSBjb21lcyBmaXJzdC4KNC4gUmV0dXJuIDAgaWYgYm90aCB0aXRsZXMgYXJlIGlkZW50aWNhbC4KClRJTUUgQ09NUExFWElUWToKTyhWICsgRSArIFIgKiBsb2coUikgKiBMKQoKViA9IG51bWJlciBvZiBtb3ZpZXMKRSA9IG51bWJlciBvZiBzaW1pbGFyaXR5IGVkZ2VzClIgPSBudW1iZXIgb2YgcmVhY2hhYmxlIG1vdmllcyBleGNsdWRpbmcgc3RhcnQKTCA9IG1heGltdW0gbW92aWUgdGl0bGUgbGVuZ3RoCgotIEJGUzogTyhWICsgRSkKLSBjb21wYXJlVGl0bGVzOiBPKEwpCi0gU29ydGluZzogTyhSIGxvZyBSICogTCkKClNQQUNFIENPTVBMRVhJVFk6Ck8oViArIFIpIGF1eGlsaWFyeSBzcGFjZSwgZXhjbHVkaW5nIHNvcnQgaW50ZXJuYWxzLgoKLSB2aXNpdGVkOiBPKFYpCi0gQkZTIHF1ZXVlOiBPKFYpCi0gY2FuZGlkYXRlczogTyhSKQotIGNvbXBhcmVUaXRsZXM6IE8oMSkKLSBTb3J0aW5nIG1heSB1c2UgYWRkaXRpb25hbCBpbXBsZW1lbnRhdGlvbi1kZXBlbmRlbnQgc3BhY2UuCiovCgovLyA9PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT0KLy8gQ1VTVE9NIExFWElDT0dSQVBISUNBTCBDT01QQVJJU09OCi8vID09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PQoKZnVuY3Rpb24gY29tcGFyZVRpdGxlcyhzdHIxLCBzdHIyKSB7CiAgICBjb25zdCBtaW5MZW4gPSBNYXRoLm1pbihzdHIxLmxlbmd0aCwgc3RyMi5sZW5ndGgpOwoKICAgIC8vIENvbXBhcmUgY2hhcmFjdGVycyBvbmUgYnkgb25lCiAgICBmb3IgKGxldCBpID0gMDsgaSA8IG1pbkxlbjsgaSsrKSB7CiAgICAgICAgaWYgKHN0cjFbaV0gPCBzdHIyW2ldKSByZXR1cm4gLTE7CiAgICAgICAgaWYgKHN0cjFbaV0gPiBzdHIyW2ldKSByZXR1cm4gMTsKICAgIH0KCiAgICAvLyBJZiBvbmUgdGl0bGUgaXMgYSBwcmVmaXggb2YgdGhlIG90aGVyLAogICAgLy8gdGhlIHNob3J0ZXIgdGl0bGUgY29tZXMgZmlyc3QuCiAgICBpZiAoc3RyMS5sZW5ndGggPCBzdHIyLmxlbmd0aCkgcmV0dXJuIC0xOwogICAgaWYgKHN0cjEubGVuZ3RoID4gc3RyMi5sZW5ndGgpIHJldHVybiAxOwoKICAgIC8vIEJvdGggdGl0bGVzIGFyZSBpZGVudGljYWwKICAgIHJldHVybiAwOwp9CgovLyA9PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT0KLy8gU09MVVRJT046IEJGUyArIFNPUlRJTkcKLy8gPT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09CgpmdW5jdGlvbiB0b3BSYXRlZFNpbWlsYXJNb3ZpZXMoCiAgICByYXRpbmdzLCB0aXRsZXMsIHNpbWlsYXIsIHN0YXJ0LCBrCikgewogICAgaWYgKGsgPT09IDApIHJldHVybiBbXTsKCiAgICBjb25zdCB2aXNpdGVkID0gQXJyYXkocmF0aW5ncy5sZW5ndGgpLmZpbGwoZmFsc2UpOwogICAgY29uc3QgcSA9IFtzdGFydF07CiAgICBsZXQgaGVhZCA9IDA7CiAgICBjb25zdCBjYW5kaWRhdGVzID0gW107CgogICAgdmlzaXRlZFtzdGFydF0gPSB0cnVlOwoKICAgIC8vIFNURVAgMTogQkZTIHRvIGZpbmQgYWxsIHJlYWNoYWJsZSBtb3ZpZXMKICAgIHdoaWxlIChoZWFkIDwgcS5sZW5ndGgpIHsKICAgICAgICBjb25zdCBjdXJyID0gcVtoZWFkKytdOwoKICAgICAgICAvLyBTVEVQIDI6IEV4cGxvcmUgbmVpZ2hib3JpbmcgbW92aWVzCiAgICAgICAgZm9yIChjb25zdCBuZXh0IG9mIHNpbWlsYXJbY3Vycl0pIHsKICAgICAgICAgICAgaWYgKCF2aXNpdGVkW25leHRdKSB7CiAgICAgICAgICAgICAgICB2aXNpdGVkW25leHRdID0gdHJ1ZTsKICAgICAgICAgICAgICAgIHEucHVzaChuZXh0KTsKCiAgICAgICAgICAgICAgICAvLyBFeGNsdWRlIHN0YXJ0IChhbHJlYWR5IG1hcmtlZCB2aXNpdGVkKQogICAgICAgICAgICAgICAgY2FuZGlkYXRlcy5wdXNoKG5leHQpOwogICAgICAgICAgICB9CiAgICAgICAgfQogICAgfQoKICAgIC8vIFNURVAgMzogU29ydCBieSByYXRpbmcsIHRpdGxlLCB0aGVuIElECiAgICBjYW5kaWRhdGVzLnNvcnQoKGEsIGIpID0+IHsKICAgICAgICAvLyBIaWdoZXIgcmF0aW5nIGZpcnN0CiAgICAgICAgaWYgKHJhdGluZ3NbYV0gIT09IHJhdGluZ3NbYl0pIHsKICAgICAgICAgICAgcmV0dXJuIHJhdGluZ3NbYl0gLSByYXRpbmdzW2FdOwogICAgICAgIH0KCiAgICAgICAgLy8gQWxwaGFiZXRpY2FsIHRpdGxlIG9yZGVyCiAgICAgICAgY29uc3QgdGl0bGVDb21wYXJpc29uID0gY29tcGFyZVRpdGxlcygKICAgICAgICAgICAgdGl0bGVzW2FdLCB0aXRsZXNbYl0KICAgICAgICApOwoKICAgICAgICBpZiAodGl0bGVDb21wYXJpc29uICE9PSAwKSB7CiAgICAgICAgICAgIHJldHVybiB0aXRsZUNvbXBhcmlzb247CiAgICAgICAgfQoKICAgICAgICAvLyBTYW1lIHJhdGluZyBhbmQgc2FtZSB0aXRsZToKICAgICAgICAvLyBTbWFsbGVyIG1vdmllIElEIGZpcnN0CiAgICAgICAgcmV0dXJuIGEgLSBiOwogICAgfSk7CgogICAgLy8gU1RFUCA0OiBSZXR1cm4gdG9wIEsgbW92aWUgSURzCiAgICByZXR1cm4gY2FuZGlkYXRlcy5zbGljZSgwLCBrKTsKfQoKLy8gPT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09Ci8vIFRFU1QgQ0FTRVMgKElERU9ORS1SRUFEWSkKLy8gPT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09Cgpjb25zdCB0ZXN0cyA9IFsKICAgIHsKICAgICAgICBuYW1lOiAiTm9ybWFsICsgYWxwaGFiZXRpY2FsIHJhdGluZyB0aWVzIiwKICAgICAgICByYXRpbmdzOiBbODAsIDk1LCA5NSwgOTBdLAogICAgICAgIHRpdGxlczogWwogICAgICAgICAgICAiQXZhdGFyIiwKICAgICAgICAgICAgIlRpdGFuaWMiLAogICAgICAgICAgICAiSW5jZXB0aW9uIiwKICAgICAgICAgICAgIkludGVyc3RlbGxhciIKICAgICAgICBdLAogICAgICAgIHNpbWlsYXI6IFtbMSwgMiwgM10sIFtdLCBbXSwgW11dLAogICAgICAgIHN0YXJ0OiAwLAogICAgICAgIGs6IDIsCiAgICAgICAgZXhwZWN0ZWQ6IFsyLCAxXQogICAgfSwKICAgIHsKICAgICAgICBuYW1lOiAiU2FtZSByYXRpbmcgYW5kIHNhbWUgdGl0bGUgLSBzbWFsbGVyIElEIiwKICAgICAgICByYXRpbmdzOiBbNTAsIDkwLCA5MCwgOTBdLAogICAgICAgIHRpdGxlczogWyJTdGFydCIsICJBdmF0YXIiLCAiQXZhdGFyIiwgIkJhdG1hbiJdLAogICAgICAgIHNpbWlsYXI6IFtbMiwgMywgMV0sIFtdLCBbXSwgW11dLAogICAgICAgIHN0YXJ0OiAwLAogICAgICAgIGs6IDMsCiAgICAgICAgZXhwZWN0ZWQ6IFsxLCAyLCAzXQogICAgfSwKICAgIHsKICAgICAgICBuYW1lOiAiQ3ljbGVzICsgZHVwbGljYXRlIGVkZ2VzICsgcHJlZml4IHRpdGxlcyIsCiAgICAgICAgcmF0aW5nczogWzEwMCwgOTUsIDk1LCA5NSwgOTk5XSwKICAgICAgICB0aXRsZXM6IFsiU3RhcnQiLCAiQXZhdGFyIiwgIkF2IiwgIkF2ZW5nZXJzIiwgIk90aGVyIl0sCiAgICAgICAgc2ltaWxhcjogWwogICAgICAgICAgICBbMSwgMSwgMl0sCiAgICAgICAgICAgIFswLCAzXSwKICAgICAgICAgICAgWzFdLAogICAgICAgICAgICBbM10sCiAgICAgICAgICAgIFtdCiAgICAgICAgXSwKICAgICAgICBzdGFydDogMCwKICAgICAgICBrOiAzLAogICAgICAgIGV4cGVjdGVkOiBbMiwgMSwgM10KICAgIH0sCiAgICB7CiAgICAgICAgbmFtZTogIk5vIHJlYWNoYWJsZSBtb3ZpZXMiLAogICAgICAgIHJhdGluZ3M6IFsxMDAsIDkwXSwKICAgICAgICB0aXRsZXM6IFsiU3RhcnQiLCAiQXZhdGFyIl0sCiAgICAgICAgc2ltaWxhcjogW1tdLCBbXV0sCiAgICAgICAgc3RhcnQ6IDAsCiAgICAgICAgazogMSwKICAgICAgICBleHBlY3RlZDogW10KICAgIH0KXTsKCmZvciAoY29uc3QgdGVzdCBvZiB0ZXN0cykgewogICAgY29uc3QgYWN0dWFsID0gdG9wUmF0ZWRTaW1pbGFyTW92aWVzKAogICAgICAgIHRlc3QucmF0aW5ncywKICAgICAgICB0ZXN0LnRpdGxlcywKICAgICAgICB0ZXN0LnNpbWlsYXIsCiAgICAgICAgdGVzdC5zdGFydCwKICAgICAgICB0ZXN0LmsKICAgICk7CgogICAgY29uc3QgcGFzc2VkID0KICAgICAgICBKU09OLnN0cmluZ2lmeShhY3R1YWwpID09PSBKU09OLnN0cmluZ2lmeSh0ZXN0LmV4cGVjdGVkKTsKCiAgICBjb25zb2xlLmxvZygKICAgICAgICBgJHtwYXNzZWQgPyAiUEFTUyIgOiAiRkFJTCJ9IC0gJHt0ZXN0Lm5hbWV9YAogICAgKTsKICAgIGNvbnNvbGUubG9nKCJFeHBlY3RlZDoiLCBKU09OLnN0cmluZ2lmeSh0ZXN0LmV4cGVjdGVkKSk7CiAgICBjb25zb2xlLmxvZygiQWN0dWFsOiAgIiwgSlNPTi5zdHJpbmdpZnkoYWN0dWFsKSk7CiAgICBjb25zb2xlLmxvZygpOwp9Cg==