[TINJ]

> For example, I've seen people write code which relies heavily on design patterns but then that same code uses an O(n^2) nested loop to find items that are common between two arrays. There is a simple 'pattern' you can use to store the items of the first array in a Set or HashMap and then finding common items is O(n) because Set and HashMap lookups are O(1)... Very useful pattern but I don't believe it has a name. I use it literally ALL the time. The idea of storing intermediate state in some kind of HashMap is a game-changer IMO but there's no name for that pattern of coding.

Isn't this called 'dynamic programming'? It's actually a habit people should pick up when grinding leetcode.

[viraptor]

No, dynamic programming is when you split your bigger problem into a smaller one + 1 step to get to your bigger size. Then apply that recursively until you solve the trivial problem at the end and get back the answer for your original problem size.

[salutis]

No, that is plain old recursion. Dynamic programming is recursive programming with a twist. The twist is that identical sub-problems are short-circuited with memoization.

[arethuza]

If you already have Sets handy - why not use the Set Intersection? (Assuming the Set implementation has that capability).

[zelphirkalt]

Putting both contents (lists, arrays, whatever you have) into sets, and then calculating the intersection might be more expensive than building the intersected set right away sourcing both non-set contents, I imagine. Though it would probably be easier to read and understand. But that can be solved by naming of functions that process the 2 non-set things.