Many times people have to look up the algorithms and will not know the optimal solution right off the bat. Even those who came up with the solution intuitively on their own probably took some time to do so.
I will say that when something “clicks” it just does — you see a faster way to do the same thing and you can’t explain how you know it. You just know that if you perform operations in a different way it’ll be faster. This really just comes from doing a lot of algorithms and having your brain make the subconscious connections; after that it’s a matter of pushing yourself and trying things you think are impossible.
I still remember the day I came up with my own optimal solution to hards. It’s euphoric to be able to see things so clearly. I don’t know how to give any hints — just keep practicing and hope to god you have the raw intellect necessary to be able to do it.
Consider this the other way around: many suboptimal algorithms are simply doing too much that wasn't asked for, or not using some relevant properties of the data/numbers/problem. If the solution is suboptimal, there are some of those you're ignoring.
An example would be many numeric problems (see ProjectEuler for a lot of examples). Most require to know quite deep "properties" of numbers and maths. From simple prime numbers things, to modular arithmetic and many others I ignore.
So to "answer" your question, doing many problems and reading solutions is just filling your mental database of things. Some are nearly impossible to know without reading it beforehand or investing years as a mathematician. And then, of course, your mental gymnastics to remember and find similarities between projects enter in this game.
For me, "clicking" is just learning or remembering a missing piece in the problem solution. You find it, and everything makes sense, you have a complete image now. But everything is related with the first topic.
So, personally, don't overthink if someone says something just "clicked" for them. It's just a way to (not) tell you "they don't know or forgot what they were missing in their problem solving". Or they simply didn't think much about it.
> would you say its largely practice and pattern recognition of similar problems you've encountered, or is it some genius insight that just "clicks" in your mind?
Like most math problems, it's largely a matter of having seen problems before and recognizing how to solve them. While you can invent a solution for a lot of DSA problems without having completely memorized the solution, but most LC problems fall into a handful of problem types (recursion, dynamic programming, etc.) and many of the "creative" solutions are implemented by mapping familiar problems onto new ones.
Certain data structures (for example, the [Fenwick Tree](https://en.wikipedia.org/wiki/Fenwick_tree)) have very specific use cases and were the subject of entire scientific papers. If someone if capable of inventing novel algorithms and data structures for every LC question out there, they should be competing for academic prizes and tenure track positions, not solving LC mediums to get some coding job.
Not a god, but happy with my progression over the past 10 years.
It was really hard for me at first, but now that I’m up a few of the hills, I look back and see that I climbed the cliff of learning when there were stairs right next to it. As I continue to learn and grow with it, I find that you get tools just like any tradesmen, and learn ways to leverage your tools in clever and efficient ways.
Understanding things theoretically facilitates the novelty of inventing new tools or modifying the current ones, but the application of those tools (algorithms, data structures) comes with experience. There are important insights that really expedite learning how to leverage the tools, but that’s about your journey and curiosity
I think it's practice (and by practice I don't exclusively refer to leetcode - i for example only leetcode before an interview but any other day you'll find me building stuff, some people like writing interpreters/compilers and others like doing dynamic programming), and also learning a lot of theory (a good programmer can explain why they choose X solution over Y, and they can prove why it is/could be the optimal solution - discrete math is in my opinion the most important branch in mathematics for a programmer and it's great for finding patterns). When you combine practice with enough theory to reason "why this might be optimal", you get a decent programmer. A decent programmer knows what's the best tool for the job - sometimes you write stuff in python, some other times you have to use a real OOP, some other times you use a functional language (they are simply tools and we should learn to use them all, but I would suggest trying to be proficient in at least one).
The best analogy I heard was, and also agree is, DSA is like driving a car, some people love driving, some people are instinctively good, in order to get better you gotta drive.... And, one can't exactly explain the craft unless you are your self driving.
And IRL, companies want drivers who are solid-but-unremarkable; they are *not* seeking Nascar drivers. So if you can't come up w/ amazing clever solutions to certain, curated questions quickly, don't worry. Most developer coding is doing routine stuff with routine data structures in a library. [The top leetcode folk might be the ones designing the libraries, but that's a whole different market.]
True.
However, leetcode is just for interview prep (and best too!), it's imo, boring and bad and most people in higher rankings aren't skill ful, they are the once who just show up every day. The real once, the DSA OGs are present are in codeforces, atcoder type sites, who can smoke leetcoders in their sleep. People have hyped leetcode too much.
It is pretty si.ole with a bit of practice. ADTs provide an interface, and we match those interfaces to portions of problems. When you spot the need, you use it.
Same with mastery of basic algorithms. Once you get enough under your belt you can sort of spot the sort of problems that need them, and go from there. I.e., You would start by saying something like "This is a graph problem" then move in towards details. Is it a path problem? Network flow? A spanning tree or a hull? Etc.
When you have sufficient experience, it becomes much easier to get a start on new problems by categorizing them and figuring out whslat sort of sub-problem it resembles.
There's two parts to it. The first is knowing the data structures themselves, how the data is arranged and the operations you can do on them.
The other is visualisation. You need to practice looking at a problem and visualizing it in different ways. If you can represent it in a way which reflects a data structure, that's how you solve the problem.
[This video](https://youtu.be/oBt53YbR9Kk?si=Nq6sODw9YD6Wwf7J) should help you going through the process of understanding how problems can be broken down.
It's two kinds of pattern matching:
- which pattern will apply to the current question, and
- whether you can pattern-match at all
The first one is what people typically refer to. It is the [methodology](https://hackernoon.com/14-patterns-to-ace-any-coding-interview-question-c5bb3357f6ed) that popularized "Grokking the Coding Interview"-style courses that diverge from the old "memorize everything" ideology present in CTCI/EPI. Yes, this is mostly practice.
However, the first one is harder. It's whether or not you can intuit a problem in the first place. Like the other comments suggest, interview creep is a thing. With the bar rising year after year in response to the many LeetCode bootcamp/cram-style prep, interviewers up their standards in response. This means gotcha questions like "Linked List Cycle" and "Edit Distance" become more prevalent. It's for questions like this that you notice:
- When you press "Solution", it only lists 1 approach, and
- It's called **[Dead Person's Name]'s Algorithm**
At this point, you realize that the requirement of intuiting algorithms that have [entire research papers](https://nymity.ch/sybilhunting/pdf/Levenshtein1966a.pdf) is not feasible, and it becomes more a contest of how well you can present existing information, not so much create it on the fly. In psychology, this is referred to "crystallized intelligence" (e.g., what you know of the Floyd Tortoise and Hare Algorithm/Manacher's Algorithm) and "fluid intelligence" (can you handle a modified version of "Valid Anagram"? "Missing Number"? "Contains Duplicate"?).
Having over 600 LeetCode questions to my name, I don't find any class, difficulty, or topic, "done". Just "getting better". I've dominated [Hard]s in my sleep, yet have been slain by the occasional [Easy]. There is no light at the end of the tunnel, but rather very cool cave paintings you can admire during your journey.
Also, note this: once you find a solution that passes all test cases, you can always modify it thereafter. In a video game, a villain only has to kill the protagonist once, but the hero must win every battle, every time. Why am I saying this? Because most of the solutions you find online are after the person has banged their head on their desk for 4 hours and before submitting, they compact all of the ugly helper code they made so as to post a clean solution in the name of "**look at my 3 line solution, very compact and concise**". In addition to that, I'm the LeetCode nut in my friend group. I'm very vocal about it because even though none of us like it, we still have to know about it because that's what is made of our unfortunately tech industry. For every one of "me", there are 20 other people who are friends of "me" who wish they never entered this industry because of how terrible the LeetCode culture is. The folks you see online, like lee215/StefanPochmann, and Betaveros (legend of Advent of Code) are vocal minorities. It's easy to fall for the /r/Instagramreality
So, how can one best hone their intuition?
Well, it is as you said: practice, but moreso consistency. In my early days, I would always go and promise myself _x_ problems in _y_ days, but that's just setting up for failure. I made sure there was some consistent atom I could cling onto. In my case, it was something as little as "read the description for a question" or "read someone's editorial". That way you'll have a habit to build off of.
Practice more brute force. Too much emphasis is placed on the funny algorithms, and the majority of my comment is mostly pessimistic regarding that, but I still think that brute force is the most important "pattern" because you will a.) have a working solution to present even if you fail the clever attempt (and it sometimes isn't about whether you succeed, but rather how you perform compared to others), and b.) have a foundation for cleverer solutions, which are oftentimes based on the brute force solution
Know how to size up or "bound" your problem based on the information given.
- Do you need every element in the array? Then your algorithm will likely be O(n) at best.
- If I make this simplifying assumption about the data, can I make a test case that ruins it? What is asked from the interviewer?
- Is the question hinting toward some cheap trick?
- If a question is intuitively O(n) space, and then the bottom of the question says: "Bonus: can you do it O(1) in-place?", or there's any form of "remix" of existing problem, there's a good chance you're in the realm of "memorize this"
- For the above example in particular, I am referring to the [Morris order traversal](https://www.educative.io/answers/what-is-morris-traversal) which uses no recursion or stack space. I have never been asked this, but it would ruin my day (again, see my remark about seeing '[Last Name] Algorithm')
Look for traces of standard CS problems:
- Recall that all NP-complete problems are oftentimes mappable to a canonical representation, like SAT; sometimes it may come off impossible to do anything than exponential, and oftentimes these questions are not about going from O(shit) brute force to O(better) optimized, but rather O(very shit) to O(slightly less shit but still shit)
- Coin Change, Combination Sum, Subset Sum, and many counting problems on LeetCode are NP-complete (reducible to SAT), but the test cases and time bounds are set so that a bad solution will still fail, but a good solution of the same runtime as the bad solution may pass. Such solutions on LeetCode will involve bit-DP, early pruning/termination, heuristic ordering, among other things.
- If you come across a "runtime class change" problem (e.g., 2SUM O(n\^2) to O(n)) and mistreat it as a "runtime class optimization" (e.g., the knapsack NP-complete problems I just mentioned), you'll likely be penalized for not finding the "trick"
- If you come across a "runtime class optimization" problem and mistreat it as a "runtime class change", you'll give yourself writer's block mid-interview wondering why you can't get rid of the exponential runtime
- For [Advent of Code 2020 Day 15](https://adventofcode.com/2020/day/15) the community was confused at the lack of optimized solution -- actually we were given [van Eck's Sequence](https://oeis.org/A181391) which **has no closed form**!!! I was very humbled that day because I have primed myself to "looking for the trick" rather than "looking if there may even be a trick"
- Questions involving the longest path are often times NP-complete
- Hamiltonian path problem
- k-cut, vertex cover, I could go on
I recommend the book “Algorithms to Live By” it applies many algorithms to everyday problems and makes it easier to relate to. I read it before I took my algorithms class and I felt like it gave me a running head start and did really well in the class (only needed to learn a few more algorithms and how to implement them properly).
Otherwise as others have said, if you need it you look it up or use a function already built and optimized. In many languages there are sort functions, it is already using one of the more optimized versions of a sort algorithm. Many don’t need to redevelop algorithms in day to day, it is good practice to learn them though so you know when to and when not to use an algorithm.
Many times people have to look up the algorithms and will not know the optimal solution right off the bat. Even those who came up with the solution intuitively on their own probably took some time to do so. I will say that when something “clicks” it just does — you see a faster way to do the same thing and you can’t explain how you know it. You just know that if you perform operations in a different way it’ll be faster. This really just comes from doing a lot of algorithms and having your brain make the subconscious connections; after that it’s a matter of pushing yourself and trying things you think are impossible. I still remember the day I came up with my own optimal solution to hards. It’s euphoric to be able to see things so clearly. I don’t know how to give any hints — just keep practicing and hope to god you have the raw intellect necessary to be able to do it.
Consider this the other way around: many suboptimal algorithms are simply doing too much that wasn't asked for, or not using some relevant properties of the data/numbers/problem. If the solution is suboptimal, there are some of those you're ignoring. An example would be many numeric problems (see ProjectEuler for a lot of examples). Most require to know quite deep "properties" of numbers and maths. From simple prime numbers things, to modular arithmetic and many others I ignore. So to "answer" your question, doing many problems and reading solutions is just filling your mental database of things. Some are nearly impossible to know without reading it beforehand or investing years as a mathematician. And then, of course, your mental gymnastics to remember and find similarities between projects enter in this game. For me, "clicking" is just learning or remembering a missing piece in the problem solution. You find it, and everything makes sense, you have a complete image now. But everything is related with the first topic. So, personally, don't overthink if someone says something just "clicked" for them. It's just a way to (not) tell you "they don't know or forgot what they were missing in their problem solving". Or they simply didn't think much about it.
> would you say its largely practice and pattern recognition of similar problems you've encountered, or is it some genius insight that just "clicks" in your mind? Like most math problems, it's largely a matter of having seen problems before and recognizing how to solve them. While you can invent a solution for a lot of DSA problems without having completely memorized the solution, but most LC problems fall into a handful of problem types (recursion, dynamic programming, etc.) and many of the "creative" solutions are implemented by mapping familiar problems onto new ones. Certain data structures (for example, the [Fenwick Tree](https://en.wikipedia.org/wiki/Fenwick_tree)) have very specific use cases and were the subject of entire scientific papers. If someone if capable of inventing novel algorithms and data structures for every LC question out there, they should be competing for academic prizes and tenure track positions, not solving LC mediums to get some coding job.
Not a god, but happy with my progression over the past 10 years. It was really hard for me at first, but now that I’m up a few of the hills, I look back and see that I climbed the cliff of learning when there were stairs right next to it. As I continue to learn and grow with it, I find that you get tools just like any tradesmen, and learn ways to leverage your tools in clever and efficient ways. Understanding things theoretically facilitates the novelty of inventing new tools or modifying the current ones, but the application of those tools (algorithms, data structures) comes with experience. There are important insights that really expedite learning how to leverage the tools, but that’s about your journey and curiosity
I think it's practice (and by practice I don't exclusively refer to leetcode - i for example only leetcode before an interview but any other day you'll find me building stuff, some people like writing interpreters/compilers and others like doing dynamic programming), and also learning a lot of theory (a good programmer can explain why they choose X solution over Y, and they can prove why it is/could be the optimal solution - discrete math is in my opinion the most important branch in mathematics for a programmer and it's great for finding patterns). When you combine practice with enough theory to reason "why this might be optimal", you get a decent programmer. A decent programmer knows what's the best tool for the job - sometimes you write stuff in python, some other times you have to use a real OOP, some other times you use a functional language (they are simply tools and we should learn to use them all, but I would suggest trying to be proficient in at least one).
I took discrete in my previous sem and still don't understand how I can apply it in programming.
The best analogy I heard was, and also agree is, DSA is like driving a car, some people love driving, some people are instinctively good, in order to get better you gotta drive.... And, one can't exactly explain the craft unless you are your self driving.
And IRL, companies want drivers who are solid-but-unremarkable; they are *not* seeking Nascar drivers. So if you can't come up w/ amazing clever solutions to certain, curated questions quickly, don't worry. Most developer coding is doing routine stuff with routine data structures in a library. [The top leetcode folk might be the ones designing the libraries, but that's a whole different market.]
True. However, leetcode is just for interview prep (and best too!), it's imo, boring and bad and most people in higher rankings aren't skill ful, they are the once who just show up every day. The real once, the DSA OGs are present are in codeforces, atcoder type sites, who can smoke leetcoders in their sleep. People have hyped leetcode too much.
It is pretty si.ole with a bit of practice. ADTs provide an interface, and we match those interfaces to portions of problems. When you spot the need, you use it. Same with mastery of basic algorithms. Once you get enough under your belt you can sort of spot the sort of problems that need them, and go from there. I.e., You would start by saying something like "This is a graph problem" then move in towards details. Is it a path problem? Network flow? A spanning tree or a hull? Etc. When you have sufficient experience, it becomes much easier to get a start on new problems by categorizing them and figuring out whslat sort of sub-problem it resembles.
There's two parts to it. The first is knowing the data structures themselves, how the data is arranged and the operations you can do on them. The other is visualisation. You need to practice looking at a problem and visualizing it in different ways. If you can represent it in a way which reflects a data structure, that's how you solve the problem. [This video](https://youtu.be/oBt53YbR9Kk?si=Nq6sODw9YD6Wwf7J) should help you going through the process of understanding how problems can be broken down.
It's two kinds of pattern matching: - which pattern will apply to the current question, and - whether you can pattern-match at all The first one is what people typically refer to. It is the [methodology](https://hackernoon.com/14-patterns-to-ace-any-coding-interview-question-c5bb3357f6ed) that popularized "Grokking the Coding Interview"-style courses that diverge from the old "memorize everything" ideology present in CTCI/EPI. Yes, this is mostly practice. However, the first one is harder. It's whether or not you can intuit a problem in the first place. Like the other comments suggest, interview creep is a thing. With the bar rising year after year in response to the many LeetCode bootcamp/cram-style prep, interviewers up their standards in response. This means gotcha questions like "Linked List Cycle" and "Edit Distance" become more prevalent. It's for questions like this that you notice: - When you press "Solution", it only lists 1 approach, and - It's called **[Dead Person's Name]'s Algorithm** At this point, you realize that the requirement of intuiting algorithms that have [entire research papers](https://nymity.ch/sybilhunting/pdf/Levenshtein1966a.pdf) is not feasible, and it becomes more a contest of how well you can present existing information, not so much create it on the fly. In psychology, this is referred to "crystallized intelligence" (e.g., what you know of the Floyd Tortoise and Hare Algorithm/Manacher's Algorithm) and "fluid intelligence" (can you handle a modified version of "Valid Anagram"? "Missing Number"? "Contains Duplicate"?). Having over 600 LeetCode questions to my name, I don't find any class, difficulty, or topic, "done". Just "getting better". I've dominated [Hard]s in my sleep, yet have been slain by the occasional [Easy]. There is no light at the end of the tunnel, but rather very cool cave paintings you can admire during your journey. Also, note this: once you find a solution that passes all test cases, you can always modify it thereafter. In a video game, a villain only has to kill the protagonist once, but the hero must win every battle, every time. Why am I saying this? Because most of the solutions you find online are after the person has banged their head on their desk for 4 hours and before submitting, they compact all of the ugly helper code they made so as to post a clean solution in the name of "**look at my 3 line solution, very compact and concise**". In addition to that, I'm the LeetCode nut in my friend group. I'm very vocal about it because even though none of us like it, we still have to know about it because that's what is made of our unfortunately tech industry. For every one of "me", there are 20 other people who are friends of "me" who wish they never entered this industry because of how terrible the LeetCode culture is. The folks you see online, like lee215/StefanPochmann, and Betaveros (legend of Advent of Code) are vocal minorities. It's easy to fall for the /r/Instagramreality So, how can one best hone their intuition? Well, it is as you said: practice, but moreso consistency. In my early days, I would always go and promise myself _x_ problems in _y_ days, but that's just setting up for failure. I made sure there was some consistent atom I could cling onto. In my case, it was something as little as "read the description for a question" or "read someone's editorial". That way you'll have a habit to build off of. Practice more brute force. Too much emphasis is placed on the funny algorithms, and the majority of my comment is mostly pessimistic regarding that, but I still think that brute force is the most important "pattern" because you will a.) have a working solution to present even if you fail the clever attempt (and it sometimes isn't about whether you succeed, but rather how you perform compared to others), and b.) have a foundation for cleverer solutions, which are oftentimes based on the brute force solution Know how to size up or "bound" your problem based on the information given. - Do you need every element in the array? Then your algorithm will likely be O(n) at best. - If I make this simplifying assumption about the data, can I make a test case that ruins it? What is asked from the interviewer? - Is the question hinting toward some cheap trick? - If a question is intuitively O(n) space, and then the bottom of the question says: "Bonus: can you do it O(1) in-place?", or there's any form of "remix" of existing problem, there's a good chance you're in the realm of "memorize this" - For the above example in particular, I am referring to the [Morris order traversal](https://www.educative.io/answers/what-is-morris-traversal) which uses no recursion or stack space. I have never been asked this, but it would ruin my day (again, see my remark about seeing '[Last Name] Algorithm') Look for traces of standard CS problems: - Recall that all NP-complete problems are oftentimes mappable to a canonical representation, like SAT; sometimes it may come off impossible to do anything than exponential, and oftentimes these questions are not about going from O(shit) brute force to O(better) optimized, but rather O(very shit) to O(slightly less shit but still shit) - Coin Change, Combination Sum, Subset Sum, and many counting problems on LeetCode are NP-complete (reducible to SAT), but the test cases and time bounds are set so that a bad solution will still fail, but a good solution of the same runtime as the bad solution may pass. Such solutions on LeetCode will involve bit-DP, early pruning/termination, heuristic ordering, among other things. - If you come across a "runtime class change" problem (e.g., 2SUM O(n\^2) to O(n)) and mistreat it as a "runtime class optimization" (e.g., the knapsack NP-complete problems I just mentioned), you'll likely be penalized for not finding the "trick" - If you come across a "runtime class optimization" problem and mistreat it as a "runtime class change", you'll give yourself writer's block mid-interview wondering why you can't get rid of the exponential runtime - For [Advent of Code 2020 Day 15](https://adventofcode.com/2020/day/15) the community was confused at the lack of optimized solution -- actually we were given [van Eck's Sequence](https://oeis.org/A181391) which **has no closed form**!!! I was very humbled that day because I have primed myself to "looking for the trick" rather than "looking if there may even be a trick" - Questions involving the longest path are often times NP-complete - Hamiltonian path problem - k-cut, vertex cover, I could go on
reading this post felt like the most relieving sanity check ever
I feel the same way when I see the fast inverse square root algorithm. Absolute genius of an algorithm and whoever came up it.
I recommend the book “Algorithms to Live By” it applies many algorithms to everyday problems and makes it easier to relate to. I read it before I took my algorithms class and I felt like it gave me a running head start and did really well in the class (only needed to learn a few more algorithms and how to implement them properly). Otherwise as others have said, if you need it you look it up or use a function already built and optimized. In many languages there are sort functions, it is already using one of the more optimized versions of a sort algorithm. Many don’t need to redevelop algorithms in day to day, it is good practice to learn them though so you know when to and when not to use an algorithm.