fork download
  1.  
  2. /*
  3. Follow up 1 - Single Highest-Rated Similar Movie (k = 1)
  4. PROBLEM:
  5. Given movie ratings, an adjacency list of similar movies,
  6. and a starting movie, return the highest-rated reachable
  7. movie, excluding the starting movie.
  8.  
  9. Tie-breaker: Smaller movie ID wins.
  10. Return -1 if no other movie is reachable.
  11.  
  12. APPROACH: BFS + TRACK BEST
  13.  
  14. 1. Start BFS from the starting movie.
  15. 2. Use visited to avoid cycles and duplicate processing.
  16. 3. Maintain a variable "best" initialized to -1.
  17. 4. For each reachable movie (excluding start):
  18.   - Update best if its rating is higher.
  19.   - If ratings tie, prefer the smaller movie ID.
  20. 5. Continue BFS to explore all reachable movies.
  21. 6. Return best.
  22.  
  23. WHY NO MIN-HEAP OR SORTING?
  24. - We need only one recommendation (k = 1).
  25. - A single variable is sufficient to track the best movie.
  26. - BFS is still necessary to discover all reachable movies.
  27.  
  28. TIME COMPLEXITY: O(V + E)
  29. - BFS visits each reachable vertex once.
  30. - Each outgoing edge is examined once.
  31. - Comparing with best takes O(1).
  32.  
  33. SPACE COMPLEXITY: O(V)
  34. - visited array: O(V)
  35. - BFS queue: O(V)
  36. - best variable: O(1)
  37. */
  38.  
  39. function highestRatedSimilarMovie(ratings, similar, start) {
  40. const visited = Array(ratings.length).fill(false);
  41. const q = [start];
  42. let head = 0;
  43. let best = -1;
  44.  
  45. visited[start] = true;
  46.  
  47. // STEP 1: BFS
  48. while (head < q.length) {
  49. const curr = q[head++];
  50.  
  51. // STEP 2: Update best (exclude starting movie)
  52. if (curr !== start) {
  53. if (
  54. best === -1 ||
  55. ratings[curr] > ratings[best] ||
  56. (ratings[curr] === ratings[best] && curr < best)
  57. ) {
  58. best = curr;
  59. }
  60. }
  61.  
  62. // STEP 3: Explore neighbors
  63. for (const next of similar[curr]) {
  64. if (!visited[next]) {
  65. visited[next] = true;
  66. q.push(next);
  67. }
  68. }
  69. }
  70.  
  71. return best;
  72. }
  73.  
  74. // ==========================================
  75. // TEST CASES
  76. // ==========================================
  77.  
  78. const tests = [
  79. {
  80. name: "Normal + unreachable highest rating",
  81. ratings: [60, 80, 95, 90, 100],
  82. similar: [[1, 2], [3], [], [], []],
  83. start: 0,
  84. expected: 2
  85. },
  86. {
  87. name: "Rating ties - smaller ID wins",
  88. ratings: [50, 95, 95, 80],
  89. similar: [[2, 3], [], [1], []],
  90. start: 0,
  91. expected: 1
  92. },
  93. {
  94. name: "Cycles + duplicates + self-loop",
  95. ratings: [100, 20, 90, 90],
  96. similar: [[0, 1, 1], [0, 2, 3], [1], []],
  97. start: 0,
  98. expected: 2
  99. },
  100. {
  101. name: "No reachable movies",
  102. ratings: [100, 90, 80],
  103. similar: [[], [2], []],
  104. start: 0,
  105. expected: -1
  106. }
  107. ];
  108.  
  109. for (const test of tests) {
  110. const actual = highestRatedSimilarMovie(
  111. test.ratings,
  112. test.similar,
  113. test.start
  114. );
  115.  
  116. const passed = actual === test.expected;
  117.  
  118. console.log(`${passed ? "PASS" : "FAIL"} - ${test.name}`);
  119. console.log("Expected:", test.expected);
  120. console.log("Actual: ", actual);
  121. console.log();
  122. }
  123.  
Success #stdin #stdout 0.03s 5668KB
stdin
Standard input is empty
stdout
PASS - Normal + unreachable highest rating
Expected: 2
Actual:   2

PASS - Rating ties - smaller ID wins
Expected: 1
Actual:   1

PASS - Cycles + duplicates + self-loop
Expected: 2
Actual:   2

PASS - No reachable movies
Expected: -1
Actual:   -1