Grokking the Coding Interview: Patterns for Coding Questions
Ask Author
Back to course home

0% completed

Vote For New Content
Jay Karlsven
Overly complex solution? (spoiler alert: solution code included)

Jay Karlsven

Jan 28, 2024

In all of the previous problems for Heaps in JavaScript, the recommended solutions involved using sorted arrays to essentially "simulate" a Heap.

So my solution to the problem involved an insertion function that inserted to a min heap array. To retrieve the median, I simply calculated the middle element of the array (or middle 2 if the array length was even).

This solution seems so much simpler to me and had WAY less code than the recommended solution. I realize this isn't like, the "Heap" solution, so writing out an entire Heap class might help better with long term understanding of Heaps but this seems so much less complex to me. Someone want to point out where I'm wrong here?

class Solution {   constructor() {     this.nums = [];   }   insertNum(num) {     let index = this.nums.length;     this.nums.push(num);     while (index > 0 && this.nums[index - 1] > num) {       this.nums[index] = this.nums[index - 1];       this.nums[index - 1] = num;       index--;     }   }   findMedian() {     const midPoint = Math.ceil(this.nums.length / 2) - 1;     if (this.nums.length % 2 === 0) {       return (this.nums[midPoint] + this.nums[midPoint + 1]) / 2;     } else {       return this.nums[midPoint];     }   } }

1

0

Comments
Comments
J
Jimmy 2 years ago

Your algorithm will work and is basically what was described in the first paragraph of the solution (implementing insertion sort in a sorted array). As mentioned in the solution, it will run in O(N) and is not the most optimal algorithm. Using the two heaps approach wil...

On this page