This content originally appeared on DEV Community and was authored by Corndog_com567
Intro: I am a former accountant turned software engineer graduated from coding bootcamp in January 2022. Algorithms and Data Structure is an unavoidable part of interviews for most of the tech companies now. And one of my friends told me that you need to solve a medium leetcode problem under 60 seconds in order to get into the top tech companies.So I thought I'd start learning how to do it while job searching.
Since I have no clue on how to solve any of the problems (even the easy ones), I thought there is no point for me to waste hours and can't get it figured out. Here is my approach:
- Pick a leetcode problem randomly or Online Assessment from targeted companies.
- Study 1-2 solutions from Youtube or LeetCode discussion section. One brute force solution, another one more optimal.
- Write a blog post with detailed explanation and do a verbal walk through to help understand the solutions better.
- Code out the solution in LeetCode without looking at the solutions
- Combat the forgetting curve: Re-do the question for the next three days. And come back regularly to revisit the problem.
Problem#56. Merge Intervals
Difficulty: Medium Language: JavaScript
Company: IBM Backend Developer OA
Given an array of intervals where intervals[i] = [starti,, merge all overlapping intervals, and return an array of
endi]
the non-overlapping intervals that cover all the intervals in the
input.
Example 1:
Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlaps, merge them
into [1,6].
Example 2:
Input: intervals = [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considered overlapping.
Constraints:
1 <= intervals.length <= 104intervals[i].length == 20 <= starti <= endi <= 104
Solution:
var merge = function(intervals) {
intervals.sort((a,b) => a[0] - b[0])
/*Sort (note 1) the array of 'intervals' by index 0 of each
element. This is an important step. If given array is
[[2,4],[1,3]], this line of code will give us a new array of
[[1,3],[2,4]]*/
for (let i = 1; i < intervals.length; i++) {
/*Loop (note 3) through each element in the array 'intervals'*/
let current = intervals[i]
let previous = intervals[i - 1]
/*Create variables so that we can compare two element: current one
and the previous one.*/
if(current[0] <= previous[1]) {
/*Look for two arrays that overlap each other by checking if index
0 of current array is less or equal to the index 1 of previous
array. If so, two arrays overlap since we have already sorted
array 'interval' at the beginning and it's guranteed that index 0
of previous array is larger than index 0 of current array. For
example, given sorted array [[1,3],[2,4]] from above step, two
arrays overlap since 2 ('current[0]')is less than 3
('previous[1]').*/
intervals[i] =[previous[0],Math.max(current[1],
previous[1])]
/*update 'current' array 'intervals[i]' to a new array that is
consist of smallest number from current[0] and previous[0] & the
biggest number from current[0] and previous[0] (note 4:
Math.max()). For example, with sorted array [[1,3],[2,4]], we will
get 'intervals[i]' as [1,4] */
intervals.splice(i-1,1)
/*remove 'previous' array with 'splice()' (note 2). Once we update
current array 'intervals[i]' from [2,4] to [1,4]. We can remove
previous array 'intervals[i - 1]' - [1,3].*/
i -= 1
}
}
return intervals
};
Solution Submission detail as of 2/15/2022
(Data below could vary since there are new submissions daily)
- Runtime: 160 ms
- Memory Usage: 49.7 MB
- Time complexity:Time complexity of the method is O(nLogn) which is for sorting. Once the array of intervals is sorted, merging takes linear time.
- Space complexity:O(1)
References:
LeetCode Problem Link
LeetCode Discussion: garyguan0713
Note 1: sort()
Note 2: splice()
Note 3: for loop
Note 4: Math.max()
Blog Cover Image Credit
This content originally appeared on DEV Community and was authored by Corndog_com567
Corndog_com567 | Sciencx (2022-02-15T21:55:10+00:00) Day 5 of Studying LeetCode Solution until I Can Solve One on My Own: Problem#56.Merge Intervals(Medium/JavaScript). Retrieved from https://www.scien.cx/2022/02/15/day-5-of-studying-leetcode-solution-until-i-can-solve-one-on-my-own-problem56-merge-intervalsmedium-javascript/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.