fork download
  1.  
  2. /*
  3. PROBLEM:
  4. Given:
  5. - ratings[i]: Rating of movie i
  6. - titles[i]: Title of movie i
  7. - similar[i]: Adjacency list of movie i
  8. - start: Starting movie ID
  9. - k: Number of recommendations
  10.  
  11. Return up to K highest-rated reachable movie IDs.
  12.  
  13. RULES:
  14. 1. Exclude the starting movie.
  15. 2. Higher rating comes first.
  16. 3. If ratings tie, lexicographically smaller title wins.
  17. 4. If titles also tie, smaller movie ID wins.
  18. 5. Handle cycles, duplicate edges, and self-loops.
  19.  
  20. APPROACH: BFS + SIZE-K MIN-HEAP
  21.  
  22. 1. Start BFS from the starting movie.
  23. 2. Use visited to avoid processing movies multiple times.
  24. 3. Maintain a min-heap of at most K movies.
  25. 4. Keep the WORST selected movie at the heap root:
  26.   - Lower rating is worse.
  27.   - If ratings tie, alphabetically larger title is worse.
  28.   - If titles tie, larger movie ID is worse.
  29. 5. For each reachable movie (excluding start):
  30.   - If heap size < K, insert it.
  31.   - Otherwise, compare it with the heap root.
  32.   - If the new movie is better, remove the root and insert it.
  33. 6. Extract all K movies from the heap.
  34. 7. Reverse the extracted order to get best to worst.
  35.  
  36. TIME COMPLEXITY:
  37. O(V + E + R * L * log(K+1) + K * L * log(K+1))
  38.  
  39. V = number of movies
  40. E = number of edges
  41. R = reachable movies excluding start
  42. K = min(k, R)
  43. L = maximum movie title length
  44.  
  45. - BFS: O(V + E)
  46. - Heap operations: O(L * log(K+1)) each
  47. - Processing R candidates: O(R * L * log(K+1))
  48. - Extracting K movies: O(K * L * log(K+1))
  49.  
  50. SPACE COMPLEXITY:
  51. O(V + K)
  52.  
  53. - visited: O(V)
  54. - BFS queue: O(V)
  55. - Min-heap: O(K)
  56. - Result: O(K)
  57. - Custom title comparator: O(1)
  58. */
  59.  
  60. // ==========================================
  61. // CUSTOM TITLE COMPARISON
  62. // ==========================================
  63.  
  64. // Returns:
  65. // -1 if str1 comes before str2
  66. // 1 if str1 comes after str2
  67. // 0 if both are identical
  68.  
  69. function compareTitles(str1, str2) {
  70. const minLen = Math.min(str1.length, str2.length);
  71.  
  72. for (let i = 0; i < minLen; i++) {
  73. if (str1[i] < str2[i]) return -1;
  74. if (str1[i] > str2[i]) return 1;
  75. }
  76.  
  77. if (str1.length < str2.length) return -1;
  78. if (str1.length > str2.length) return 1;
  79.  
  80. return 0;
  81. }
  82.  
  83. // ==========================================
  84. // GENERIC MIN-HEAP
  85. // ==========================================
  86.  
  87. class MinHeapPq {
  88. constructor(compareFn) {
  89. this.compareFn = compareFn;
  90. this.heap = [];
  91. }
  92.  
  93. size() {
  94. return this.heap.length;
  95. }
  96.  
  97. front() {
  98. return this.heap.length > 0 ? this.heap[0] : null;
  99. }
  100.  
  101. swap(i, j) {
  102. [this.heap[i], this.heap[j]] =
  103. [this.heap[j], this.heap[i]];
  104. }
  105.  
  106. enqueue(val) {
  107. this.heap.push(val);
  108.  
  109. let i = this.heap.length - 1;
  110.  
  111. while (i > 0) {
  112. const parent = Math.floor((i - 1) / 2);
  113.  
  114. if (
  115. this.compareFn(this.heap[i], this.heap[parent]) >= 0
  116. ) {
  117. break;
  118. }
  119.  
  120. this.swap(i, parent);
  121. i = parent;
  122. }
  123. }
  124.  
  125. dequeue() {
  126. if (this.heap.length === 0) return null;
  127.  
  128. if (this.heap.length === 1) {
  129. return this.heap.pop();
  130. }
  131.  
  132. const root = this.heap[0];
  133. this.heap[0] = this.heap.pop();
  134.  
  135. let i = 0;
  136.  
  137. while (true) {
  138. const left = 2 * i + 1;
  139. const right = 2 * i + 2;
  140. let smallest = i;
  141.  
  142. if (
  143. left < this.heap.length &&
  144. this.compareFn(
  145. this.heap[left],
  146. this.heap[smallest]
  147. ) < 0
  148. ) {
  149. smallest = left;
  150. }
  151.  
  152. if (
  153. right < this.heap.length &&
  154. this.compareFn(
  155. this.heap[right],
  156. this.heap[smallest]
  157. ) < 0
  158. ) {
  159. smallest = right;
  160. }
  161.  
  162. if (smallest === i) break;
  163.  
  164. this.swap(i, smallest);
  165. i = smallest;
  166. }
  167.  
  168. return root;
  169. }
  170. }
  171.  
  172. // ==========================================
  173. // SOLUTION: BFS + SIZE-K MIN-HEAP
  174. // ==========================================
  175.  
  176. function topRatedSimilarMoviesHeap(
  177. ratings, titles, similar, start, k
  178. ) {
  179. if (k === 0) return [];
  180.  
  181. const visited = Array(ratings.length).fill(false);
  182. const q = [start];
  183. let head = 0;
  184.  
  185. // Negative => a is worse than b
  186. // Positive => a is better than b
  187. // Zero => same movie ranking
  188.  
  189. const compareFn = (a, b) => {
  190. // Lower rating is worse
  191. if (ratings[a] !== ratings[b]) {
  192. return ratings[a] - ratings[b];
  193. }
  194.  
  195. // Alphabetically larger title is worse
  196. const titleComparison = compareTitles(
  197. titles[a], titles[b]
  198. );
  199.  
  200. if (titleComparison !== 0) {
  201. return -titleComparison;
  202. }
  203.  
  204. // Larger movie ID is worse
  205. return b - a;
  206. };
  207.  
  208. const minHeap = new MinHeapPq(compareFn);
  209.  
  210. visited[start] = true;
  211.  
  212. // STEP 1: BFS
  213. while (head < q.length) {
  214. const curr = q[head++];
  215.  
  216. // STEP 2: Maintain top K movies
  217. if (curr !== start) {
  218. if (minHeap.size() < k) {
  219. minHeap.enqueue(curr);
  220. } else if (
  221. compareFn(curr, minHeap.front()) > 0
  222. ) {
  223. // New movie is better than the worst
  224. minHeap.dequeue();
  225. minHeap.enqueue(curr);
  226. }
  227. }
  228.  
  229. // STEP 3: Explore neighbors
  230. for (const next of similar[curr]) {
  231. if (!visited[next]) {
  232. visited[next] = true;
  233. q.push(next);
  234. }
  235. }
  236. }
  237.  
  238. // STEP 4: Extract worst to best
  239. const result = [];
  240.  
  241. while (minHeap.size() > 0) {
  242. result.push(minHeap.dequeue());
  243. }
  244.  
  245. // STEP 5: Return best to worst
  246. return result.reverse();
  247. }
  248.  
  249. // ==========================================
  250. // TEST CASES (IDEONE-READY)
  251. // ==========================================
  252.  
  253. const tests = [
  254. {
  255. name: "Normal + alphabetical rating ties",
  256. ratings: [80, 95, 95, 90],
  257. titles: [
  258. "Avatar", "Titanic",
  259. "Inception", "Interstellar"
  260. ],
  261. similar: [[1, 2, 3], [], [], []],
  262. start: 0,
  263. k: 2,
  264. expected: [2, 1]
  265. },
  266. {
  267. name: "Same rating + same title",
  268. ratings: [50, 90, 90, 90],
  269. titles: [
  270. "Start", "Avatar",
  271. "Avatar", "Batman"
  272. ],
  273. similar: [[2, 3, 1], [], [], []],
  274. start: 0,
  275. k: 3,
  276. expected: [1, 2, 3]
  277. },
  278. {
  279. name: "Cycles + duplicates + prefix titles",
  280. ratings: [100, 95, 95, 95, 999],
  281. titles: [
  282. "Start", "Avatar", "Av",
  283. "Avengers", "Other"
  284. ],
  285. similar: [
  286. [1, 1, 2],
  287. [0, 3],
  288. [1],
  289. [3],
  290. []
  291. ],
  292. start: 0,
  293. k: 3,
  294. expected: [2, 1, 3]
  295. },
  296. {
  297. name: "No reachable movies",
  298. ratings: [100, 90],
  299. titles: ["Start", "Avatar"],
  300. similar: [[], []],
  301. start: 0,
  302. k: 1,
  303. expected: []
  304. },
  305. {
  306. name: "k = 0",
  307. ratings: [50, 90],
  308. titles: ["Start", "Avatar"],
  309. similar: [[1], []],
  310. start: 0,
  311. k: 0,
  312. expected: []
  313. }
  314. ];
  315.  
  316. for (const test of tests) {
  317. const actual = topRatedSimilarMoviesHeap(
  318. test.ratings,
  319. test.titles,
  320. test.similar,
  321. test.start,
  322. test.k
  323. );
  324.  
  325. const passed =
  326. JSON.stringify(actual) ===
  327. JSON.stringify(test.expected);
  328.  
  329. console.log(
  330. `${passed ? "PASS" : "FAIL"} - ${test.name}`
  331. );
  332. console.log("Expected:", JSON.stringify(test.expected));
  333. console.log("Actual: ", JSON.stringify(actual));
  334. console.log();
  335. }
  336.  
Success #stdin #stdout 0.03s 5636KB
stdin
Standard input is empty
stdout
PASS - Normal + alphabetical rating ties
Expected: [2,1]
Actual:   [2,1]

PASS - Same rating + same title
Expected: [1,2,3]
Actual:   [1,2,3]

PASS - Cycles + duplicates + prefix titles
Expected: [2,1,3]
Actual:   [2,1,3]

PASS - No reachable movies
Expected: []
Actual:   []

PASS - k = 0
Expected: []
Actual:   []