30:T836,/** * Definition for an interval. * function Interval(start, end) { * this.start = start; * this.end = end; * } */ /** * @param {Interval[]} intervals * @param {Interval} newInterval * @return {Interval[]} */ function insert(intervals, newInterval) { let usedNewInterval = false; if (newInterval.end < newInterval.start) return intervals; function merge(a, b) { return new Interval(Math.min(a.start, b.start), Math.max(a.end, b.end)); } for (let i = 0; i < intervals.length; i++) { // The new interval is entirely greater than the current one. if (newInterval.start > intervals[i].end) { continue; } // The new interval is entirely less than the current one; there // is no need to continue searching. if (newInterval.end < intervals[i].start) { break; } // The new interval is entirely contained in an existing interval. if (newInterval.start >= intervals[i].start && newInterval.end <= intervals[i].end) { return intervals; } // The new interval envelops the current interval. Remove current interval. if (newInterval.start <= intervals[i].start && newInterval.end >= intervals[i].end) { console.log("splice") intervals.splice(i, 1); i--; continue; } // Start or end of new interval intersects current interval. Merge. if (newInterval.start >= intervals[i].start && newInterval.start <= intervals[i].end || newInterval.end >= intervals[i].start && newInterval.end <= intervals[i].end) { intervals[i] = merge(intervals[i], newInterval); usedNewInterval = true; } } // Merge all intervals after possibly merging new interval with existing intervals. for (let i = 1; i < intervals.length; i++) { if (intervals[i - 1].end >= intervals[i].start) { intervals[i - 1] = merge(intervals[i - 1], intervals[i]); intervals.splice(i, 1); i--; } } if (!usedNewInterval) { intervals.push(newInterval); } intervals.sort((a, b) => a.start - b.start); return intervals; }31:[] 2e:{"title":"Array Problems","cells":[{"id":0,"value":"md`# Array Problems`","pinned":false,"hidden":false,"mode":"ojs"},{"id":18,"value":"md`## 1. Contained Water`","pinned":false,"hidden":false,"mode":"ojs"},{"id":23,"value":"md`[Taken from LeetCode](https://leetcode.com/problems/container-with-most-water/description/):\n\nGiven n non-negative integers a1, a2, ..., an , where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":20,"value":"md`### Solution`","pinned":false,"hidden":false,"mode":"ojs"},{"id":25,"value":"md`This is another one of those array problems that lends itself to a sliding window technique whereby two cursors are used and under certain conditions we advance one or the other.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":27,"value":"// We imagine our input array as a list of integers representing\n// heights of lines along the x-axis.\n// The water contained between bars at i and j is\n// (j - i + 1) x min(lines[i], lines[j])\nwater = (lines) => {\n let max = 0,\n i = 0,\n j = lines.length - 1;\n \n while (i < j) {\n let area = (j - i) * Math.min(lines[i], lines[j]);\n \n max = area > max ? area : max;\n \n if (lines[i] <= lines[j]) {\n i++;\n } else {\n j--;\n }\n }\n \n return max;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":32,"value":"input_1 = [1,8,6,2,5,4,8,3,7]","pinned":true,"hidden":false,"mode":"ojs"},{"id":31,"value":"water(input_1)","pinned":true,"hidden":false,"mode":"ojs"},{"id":44,"value":"md`## 2. Products of Array Except Self`","pinned":false,"hidden":false,"mode":"ojs"},{"id":58,"value":"md`\n[Taken from LeetCode:](https://leetcode.com/problems/product-of-array-except-self/description/)\n\nGiven an array nums of n integers where n > 1, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].`","pinned":false,"hidden":false,"mode":"ojs"},{"id":52,"value":"md`### Solution`","pinned":false,"hidden":false,"mode":"ojs"},{"id":61,"value":"md`A linear time solution can simulatenously build two arrays: one which represents the cumulative product of entries at indices less than index i and another which represents the cumulative product of entries at indices greater than i.\n\nThen, our return value will be an array where each index is the product of the value at the repspective indices in our two arrays we constructed.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":53,"value":"/**\n * O(n) time complexity solution.\n * @param {number[]} nums\n * @return {number[]}\n */\nproductExceptSelf = function(nums) {\n if (nums.length === 1) {\n return nums;\n }\n \n let prod = [],\n L = (new Array(nums.length)).fill(1),\n R = (new Array(nums.length)).fill(1),\n LeftProd = 1,\n RightProd = 1,\n n = nums.length;\n \n // Using one loop, fill in cumulative products from the\n // left and right.\n for (let i = 1; i < n; i++) {\n L[i] = LeftProd * nums[i - 1];\n R[n - 1 - i] = RightProd * nums[n - i];\n LeftProd = L[i];\n RightProd = R[n - 1 - i];\n }\n \n return L.map((_, i) => {\n return L[i] * R[i];\n });\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":68,"value":"md`## 3. Insert Interval`","pinned":false,"hidden":false,"mode":"ojs"},{"id":69,"value":"md`Interval problems are a particular breed of *array* problem. [Here's an interesting interval problem from LeetCode](https://leetcode.com/problems/insert-interval/):\n\nGiven a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).\n\nYou may assume that the intervals were initially sorted according to their start times.\n\nExample 1:\n\n\\`\\`\\`\nInput: intervals = [[1,3],[6,9]], newInterval = [2,5]\nOutput: [[1,5],[6,9]]\n\\`\\`\\`\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":74,"value":"function Interval(start, end) {\n this.start = start;\n this.end = end;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":72,"value":"$30","pinned":true,"hidden":false,"mode":"ojs"},{"id":80,"value":"input_intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]].map((d) => new Interval(d[0], d[1]))","pinned":true,"hidden":false,"mode":"ojs"},{"id":93,"value":"insert(input_intervals, new Interval(4, 8))","pinned":true,"hidden":false,"mode":"ojs"}],"files":"$W31","stdlib":"1","titling":"auto"}