who tf uses a string literal for arrays of 1s and 0s 😫
@@SVGc1993 `0`s and `1`s would work too, if you map 'em afterwards. Saves typing.
@@redestroyer7994 bruh I was kidding xD Obviously 1 and 0 as integers is the way to go, but still, true and false are a better approach than "1" and "0" xD
The question is "Find the number of connected components in a graph?", google for graph theory behind it.
WHY LIGHTMODE MY EYEEESS
It wouldn’t be as efficient as a series of DFS searches, but I think you can also solve this problem as a cellular automaton. Make it so that outside 1’s are set to zero until only one 1 remains for each island (then count number of ones when CA stops changing state). Some stopping condition would have to be checked to make sure that an island doesn’t disappear completely, but the idea’s correct and should work just as effectively, though not as efficiently.
It would be very helpful for you to define the question
you should explain how you came up with the solution first. Any fool can explain an already written code
That’s why I’ve attached the long form to the video for a more in-depth breakdown. Thanks for watching
Yea unfortunately this upload isnt about learning or solving anything, it’s about getting you to click a link.
@@AlgoJS Attached the long form solution where?
I can’t see a video description for shorts.
Is there a 2nd video?
Very interesting problem
@@robertweekes5783 Above the title of this short there is "Number of Island - Leetcode 200 - JavaScript". If you click that it'll direct you to the long form 👍
Love your stuff man, I get excited at every new upload no matter the wait or the topic. I just love engaging with your thought process and writing. Although the travel videos are my personal favorite
I'd kind of prefer doing a flood fill that when it hits land it circles it then continues flood filling. Should be less overall work....depending on I guess the average size of islands.
My favorite interview question: given a bunch of strings tell me all the galaxies!
Minesweeper comes to mind
Recursive is such a terrible way to solve this problem, it's just the easiest. Yeah, don't do it like that.
Yeah, this example is a steaming pile of shit. You can easily solve this by looping through the grid and just checking the cell before and above the current one in each iteration.
just use convolution, easy, solved
Those function names…
1. Calculate the size of a row.
2. Calculate the row number.
3. Count every '1' in the matrix (in one pass), simultaneously checking the values of nearby elements if needed.
4. ???
5. PROFIT
Using matrices is pretty slow, if you use dictionaries which as key has Vecoyr2Int you could talk about “offsets” concepts. Add a direction utility variable of the type u want that holds Vector2Int for offset ( (1,0) (-1,0) (0,1) (0,-1) ). At that point you don’t need any nested loop, you just check for neighbors existence within your utility of Vector2Int (assuming in your value you have some class of type Land or something, otherwise if you don’t need you can just use an HashSet). This way the code is much faster, also more elegant and small.
No no no. Indexing an array (and hence ”matrix” which is a nested array) is constant time and ridiculously fast. Introducing a hashmap here is just going to slow the code down a lot.
@@dominobuilder100it ends up depending on how big the matrix is. What determines the time at the end of the day is how long the loops are accessing dead space (not islands). Once the matrices get big enough, it becomes an issue, especially if the islands are sparse
@@thelaagernation9532 what are you talking about? You can solve the problem in O(N) with super fast constant time factor because accessing the tile type is just a matter of an array lookup. Lookups in arrays are ridiculously fast no matter how big they are. This is basic
@@dominobuilder100 it is also "basic" knowledge that using a matrix graph representation is not necessarily better than an adjacency list. It depends on the problem and in this case an adjacency list will probably work faster. Array lookups are fast, but your overall run time, believe it or not, still depends on size
Such a nice short wpwp.
It reminds me, long time ago a friend of mine called this as a "flood fill" problem. Because it works by "flooding" the "island". Not sure if that is a right terminology 😂😂😂😂
Why do you need to return anything from `dfs()`? Seems to me the outermost call, from `numIslands()`, will always return `true`. The recursive `dfs()` calls may return false but you don't even check those. Seems you are using it to clear out the rest of the island, instead of actually validating anything. Did I miss something? I like your approach btw
Yeah there’s essentially no point in having it return any value which leaves the inner if statement useless since you can just increment the numOfIslands and do DFS to clear out the island
use new standards, no longer counts in for loops.. just for (var index in array) {}
This was my Amazon interview question
Couldn't you convolve it with a kernel that has a -4 in the center and 1s in all 4 directions and then check for -4s in the answer? Basically just do a laplacian convolution.
Mutating the data from the original grid is a big no for me.
God, I hate these. All Algorithm questions get you are math experts and language experts, not people who know how to architect a system.
This is none of these examples. It doesn't require a math skill nor language specific expertise, just understanding of basic algorithms that faang developer should have
System design interviews are hard so before having one it is reasonable to weed out people who don't know basic stuff.
Interview problem: I'm trying to cache or store things on finite sized shards. How do I minimize the number of times individual shards need to get information from outside their local scope?
I would bet my left nut that some variant of this problem comes up in system architecture all the time.
This particular solution does assume that you're allowed to change the data in the matrix though... So be aware of that.
this question and all questions like this are stupid and terrible interview questions. Being able to solve code challenges is a practiced skill thats irrelevant to 99.9% of developers on the planet. Design, debugging and maintainability are much more important.
I wouldn’t say 99.99%. More like 80% maybe. It also improves reasoning skills, at least it did for me.
I've been a developer for 8 years at 2 enterprise companies. And I would have agreed with you for 7.9 of those years. (Started in front end web development, last place I was a full stack software engineer). I've recently bit the bullet and started actually looking at shit like this differently. The questions are being presented like this so that we don't have to do the abstraction ourselves, but there are PLENTY of real world scenarios for a lot of DSA stuff. The problem is, it's presented as theory first, and never tied to practicality (or usually way way way too late if at all). Example, going through my algorithm course for my 5th attempt at Learning this stuff I realized I need to Constantly ask myself how can this be applied to what I've come across either from a ticket or in our codebase. If I can't think of anything I'll literally Google "real world use case for X" and add a link and a screenshot to my notes. I didn't know that RingBuffers/ArrayQueues can be used for buffering video data, and the fact I heard Primeagen say he used it at netflix makes me that much more excited about knowing that.
The problem is that leetcode and these types of questions try to take the magic programmers are ACTUALLY responsible for which is taking a problem and finding a way to programmatically solve it, and this usually only happens after the first step in figuring out how to represent the data you have to work with as a starting point. Of course, there's no practicality without meaning and who gives a shit about whether or not I can invert a binary tree.... we'll the answer is those who are smart enough to see the opportunities to apply what they've learned
Exactly. I'd even say it is more likely to bias the process towards favoring students with no experience instead of senior developers.
Just a thought, could we use a hash set to keep track of our visited “1” positions. Then as we loop through the grid and find a 1 we check the position to the left and the position above our location against the visitedOnes hash set. If either position is found in the visitedOnes hash set then we know that our current location is connected to an island we have already counted, so add the current location to the visitedOnes hash set and just continue traversing. If the left and top positions are not in the vistedOnes hash set then we have run into a new island, so increment totalCount by 1 and add the current location to the visitedOnes hash set.
I think this would work because of the way we traverse over the grid
@@Turalcar It wouldn’t work anyway, but I think it’s quicker in the worst case. Worst case for dfs is O(2mn) I think. The worst case is it’s one big island. You would stop at [0][0] then you would recursively search the entire grid because everything is a 1 technically. Then when you return to the original nested look outside of dfs you still have to traverse the entire grid of water.
If the harshest did work (which my solution above does not work) it would technically run on O(mn) time. My particular solution doesn’t work, however a hash set would speed up things in the worst case if someone went overkill to make it work. But, again making it work is not very practical.
This doesn’t work btw. I left a comment on why the other day but it never showed.
@@sgetti4dinner They are the same O(mn) (constants are meaningless there). but 2 lookups are still less than one hash calculation.
@@Turalcar yeah constants are irrelevant in big O. This originally came from me just trying to apply a diff approach to the problem.
guys what coding app ? or program is used here
I deadass thought Billie joe Armstrong was about to start teaching me c
Nice!
And what if you cant modify map? Is there any better way do it than doing full copy of the map and then carry on modifying your own copy of it?
Haven't tested this to verify, but it might be faster to make a hashmap of already visited positions.
@nigh_anxiety time complexity is the same for hashmap, but memory wise it could be more effective if there are a lot of 0 on the map
You would need to somehow store if each tile has been visited or not, so you would need O(m*n) space. You could do it with a 'visited' HashSet.
Visit grid left to right top to bottom. If land doesnt have land left or top then its a new island
Based on that island definition the example has zero islands. Island NEED to be surrounded by water by that defination. There is only a continent there.
Isn't union-find is used for this kind of problems?
yup, however the DFS solution is more optimal since there is no underlying logic (union-find logic) other than traversing
the white background...
I am convinced that the people who come up with these coding challenges for interviews haven't actually worked as developers. Especially if you're not allowed to research online.
I'd take as a better proof of seniority if the developer researched the problem for a couple of hours, read papers and posts about different solutions, pitched to me what he concluded is the best one with the pros and cons, and then implemented it with best practices.
It's not really solely about if you are able to solve it. Often times, they'd want to hear your thought process on how you problem solve to find your way to a solution. Speaking out your thoughts significantly improves your chances of getting hired.
@Xynic48
Hearing our thought process without "let me read the docs" or "I bet there is a better solution" is barely representative of how we work day to day.
@@matheusadornidardenne8684 That's true if you are applying as a developer for a random company, but often times, these random companies care more about your stack and experience rather than if you can solve coding problems. But if you are applying for a big tech company like google or facebook, you will be making the documentation not the other way around. They might assign you more programming-related work instead of just developing, hence they need to know if you can solve problems related to data structures and algorithms.
ok
Other than a puzzling problem to solve... When will any of this be used in actual real life solution to a business problem?
Brother really. I'm not even a software engineer. I'm an electrician. But I took a few courses in college. Every island is a set of vertices in a graph connected with the rest in the island and not connected to any other vertices. If that doesn't immediately tell you that this could come up in something like network traffic routing you need to find a new career.
Edit: thought for another minute. Imagine the vectors and edges are mutual links in websites or retweets or something. Honestly. This should immediately strike you as the kind of problem an engineer should know how to solve, but more importantly, be able to see how real life problems are represented by basic graphs.
@@austinyun nice shaming tactics. Real nice. However your explanation of network traffic makes very little sense since a graph structure would be horribly unbalanced with clusters of islands - thus making search and traversal extremely inefficient, nor does it make sense in a website or frontend sense.
If your talking about a graph structure such as a tree, it also makes no sense for scalability. From an engineer point of view its impractical to do this.
Also as stated in the problem these are arrays of values being grouped, not vectors (which are dynamic). Not sure what engineering purpose your trying to solve.
Leetcode questions don't make you an engineer. These are more like puzzle questions
@@centripetal6157 if you can't even find real world examples of finding strongly connected components and connected graphs with Google I just feel sorry for you
seems inefficient. what if you start in the middle, and spread outward, give each land square a number, make it the lowest of any connected land pieces to the current square. do that recursively. needs 1 pass i think.
❤
Any interview with these kind of questions are completely stupid, because they measure absolutely nothing relevant, specialy when this is trivial for most LLMs today.
Horrible variable names though
This is way to complicated and non-performant. There's a much simpler non-recursive and more performant way of doing this using an array and an array index, with a single linear iteration over all cells top-left to bottom-right, applying a simple "look left" and "look up" rule.
Honestly, this problem is super easy.
@@simonwillover4175 Nothing more difficult as creating a thread for every row in the grid
This makes it more interesting, what are you thinking for a solution?
I'm thinking that to add parallelism, you split the entire grid into subgrids that each thread will work on, and basically have each thread do the standard solution on the subgrid.
However, a problem arises when islands span across subgrids. So, Each subgrid will be responsible for making sure islands aren't double counted by the subgrids directly below and to the right of it. When a thread visits a cell, it will mark it with a unique tag indicating what island it is apart of. So when a different thread reaches a boundary of its subgrid, and recognizes that one of its islands extends to the subgrid below / to the right of it, it can use the unique tag info to make the appropriate amount of decrements to the global amount of islands count.
You need a little extra logic to handle when a thread reaches a subgrid boundary, but the thread responsible for the adjacent subgrid hasnt tagged the relevant cells yet, and of course the nitty gritty of using atomics.
Idk if its a joke but your solution really does not make sense to me
You're not checking the diagonals. Also, there's no need for recursion at all. It's a simple linear problem. Study John Conway's "Life" algorithm.
The problem statement only assumes vertical or horizontal connections. Can you elaborate on your linear solution with the Life algorithm? I'm curious.
This was literally my Algorithm Analysis Homework last week lol. Out of body experience seeing this short
impractical nonsense.
This is way too easy
So if someone wants to be a half decent software developer he has to have a 150iq? Great, life is soooo fair…
No, you use problems you have learned as tools for similar problems. Imagine you were learning this and didn't understand;. Then you look up each line of code what it does and how it helpes you with your solution. You dont have to be a genius to understand things that you take time to study! Once you understand more concepts, you can identify the patterns in your new problem that may occurred in past problems you had to solve. A good example is learning how binary searches work. Once yo understand recursion and when its useful (divide part of divide and conquer) and understand how using a another function that uses pointers to compare values as a current index(conquer method) you can use this logic and patterns forever! You dont need to be a genius to implement it, you already studies the concept of binary search. You can think of this problem as similar. There is a pattern here you have yet to be exposed to. Of course you won't recognize what to do. And neither do i for that matter! But you can see that this problem builds on other concepts apparent in binary search algorithms and perhaps others. All it means is that you need to expose yourself to easier concepts at first and then keep building on those concepts. Good luck man! And remember, even experienced developers look up solutions or methods to solve problems,. You are, as a developer, expected to teach yourself things to solve new problems. Important to remember ! People in the comments who say its "easy" are jut people who have been exposed to this beefore and understand at a fundamental level what tools need to be used. It isn't "easy" because they are geniuses, it is easy because they recognize patterns they have used in previous problems and know how to implement them with this problem!
Life isn't fair. The faster you learn that, instead of whining making the best use of your abilities the faster you can succeed.
That’s not true, obviously. A good software dev would almost certainly have more than 100 IQ but 150 would make them desire to do more than software development.
Nope... you just need to be excellent at finding the information you need, just be an expert on how to use google/chatgpt and you'll be top tier dev in no time
Streamline your learning today - algojs.dev 🚀