This content originally appeared on DEV Community and was authored by DEV Community
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.
1560. Most Visited Sector in a Circular Track
Difficulty: Easy Language: JavaScript
Given an integer n and an integer array rounds. We have a circular track which consists of n sectors labeled from 1 to n. A marathon will be held on this track, the marathon consists of m rounds. The ith round starts at sector rounds[i - 1] and ends at sector rounds[i]. For example, round 1 starts at sector rounds[0] and ends at sector rounds[1]
Return an array of the most visited sectors sorted in ascending order.
Notice that you circulate the track in ascending order of sector numbers in the counter-clockwise direction (See the first example).
Example 1:
Input: n = 4, rounds = [1,3,1,2]
Output: [1,2]
Explanation: The marathon starts at sector 1. The order of the
visited sectors is as follows:
1 --> 2 --> 3 (end of round 1) --> 4 --> 1 (end of round 2) --> 2
(end of round 3 and the marathon)
We can see that both sectors 1 and 2 are visited twice and they
are the most visited sectors. Sectors 3 and 4 are visited only
once.
Example 2:
Input: n = 2, rounds = [2,1,2,1,2,1,2,1,2]
Output: [2]
Example 3:
Input: n = 7, rounds = [1,3,5,7]
Output: [1,2,3,4,5,6,7]
Constraints:
2 <= n <= 1001 <= m <= 100rounds.length == m + 11 <= rounds[i] <= nrounds[i] != rounds[i + 1] for 0 <= i < m
Solution:
It took me a while to understand the key to this solution, 'rudenjay' explaned it well on leetcode discussion section with illustrations. I attached linked below. My take away to this is skip the completed loop(s) in the given array and the answer is in the incompleted loop. And that incompleted loop can be acessed by comparing the first and last element in the array. *Senario 1: first element is smaller or equal to last element of the given array. * In this senario, we will ignore all the elements in between; no matter how many are there and what they are. Because at the end, we will take the first and last element to find out the incomplete loop and the numbers in this incomplete loop will be the numbers that are repeated the most. In a array with n = 4, if the first element is 2 and last element is 4 then the incompleted loop is [2,3,4] *Senario 2: first element is greater than last element of the given array. * we are still going to ignore the elements in between because they only help form the completed loop. And to access the incompleted loop, with same example from senario 1, we will get [4,1,2]. And because the problem want the output in ascending order, it's [1,2,4].
var mostVisited = function(n, rounds) {
const first = rounds[0];
const last = rounds[rounds.length - 1];
//access first and last element of the given array (note 4)
const result = [];
if (first <= last) {
for (let i = last; i >= first; i--) result.unshift(i)
//This is the code for senario 1. The loop note 1 starts from the
//last element and end on the first element.The unshift() method
//(note 3) adds one or more elements to the beginning of an array
//and returns the new length of the array. That will give us an
//output in ascending order.
} else {
for (let i = 1; i <= last; i++) result.push(i);
for (let i = first; i <= n; i++) result.push(i);
//These is the code for senario 2. Since the output needs to be in
//ascending order. We will store (note 2) i two difference ways.
//Because last element is smaller than the first, we will store
//the loop that starts at 1 and ends at the last element. Then
//store the loop that starts with first element and ends at n.
}
return result;
};
Solution Submission detail as of 2/24/2022
(Data below could vary since there are new tests/submissions daily)
- Runtime: 64 ms
- Memory Usage: 42.4 mb
References:
LeetCode Problem Link
LeetCode Discussion:rudenjay
Note 1: Loop and Iteration
Note 2: Array.push()
Note 3: Array.unshift()
Note 4: Access an array item by its index
Blog Cover Image Credit
This content originally appeared on DEV Community and was authored by DEV Community
DEV Community | Sciencx (2022-02-24T20:24:49+00:00) Day 12 of Studying LeetCode Solution until I Can Solve One on My Own: Problem1560. Most Visited Sector in a Circular Track(E/JS). Retrieved from https://www.scien.cx/2022/02/24/day-12-of-studying-leetcode-solution-until-i-can-solve-one-on-my-own-problem1560-most-visited-sector-in-a-circular-tracke-js/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.