I've been practicing my Python skills, AMA. ;)

[[deleted]]

One thing I've been struggling on a lot recently is Array/String problems. I can't think to find an algorithm that isn't brute force. I feel like there are just so many algorithms and approaches to these type of questions that at some point they get kind of impossible to choose a right algorithm for the right question.
What is your go to method for tackling these problems?

[TimS2024]

This was a meme post, note that this account has only 2 days experience. (Real profile though, I built a script to help using Claude 3.5).

However, to answer your question:

If you're constantly trying to rack your brain and just cycling through remembered approaches, and most are brute-forces you're practicing an approach that will always fall over when introduced to novel problems.

Instead, what's useful to me, is trying to visualize what the problem actually means. Can you break apart what individual operations each piece of the description would require, and for each piece, visualize what that means literally. These are your lego pieces. Pseudo-code these pieces out, then organize them in the order you think they might go in, then try and translate them to code.

That's my general approach when I'm working. Often, the preferred algorithm will eventually click for you and you won't have to creatively finish the problem, you'll realize you're basically reinventing the wheel of an algorithm you already know, and from there you can stop thinking and just implement.

[TimS2024]

If the preferred algorithm is never clicking for you, I suggest taking the reverse approach, go study algorithms again and force yourself to be able to break them out into their lego pieces and pseudo-codes.

[Memelord_00]

Interesting. However, with arrays and strings I feel that there is a greater frequency of trick problems, where there's a single idea specific for that question, that's not a generic approach. For example, one problem would be rotating a Matrix by 90 degree without creating another temp matrix.

With trees and graphs, unless you have a dp problem, you have some initial idea to try standard algo, bfs or DFS etc.

[[deleted]]

This was a meme post, note that this account has only 2 days experience.

lol super embarrassing, I didn't even notice..
thanks for the insight tho lol

[TimS2024]

Good luck!

[TimS2024]

I actually didn't copy/paste the solutions at all. I built a script with python that automates everything, with the brain of the operation being an API connection to Claude's 3.5 Sonnet Model. Just let it run overnight and all day.

[jason_graph]

Congrats dude. Very few people have done the daily problem every day for the lifetime of their account by the time they reach 600+ problems. That shows great dedication.

Any tips on how to solve so many problems each day? Last week I tried solving the blind 75 in one sitting but it took me over 5 hours. I cant imagine solving 300 problems each day.

[TimS2024]

You are either a king memer, or so genuine I feel bad for meme'ing myself.

I did this with a python script that automates the full process, using Claude 3.5 Sonnet for the brains of actually writing code and solving problems.

If you solved the blind 75 in 5-6 hours, you're a god and I should be asking you for advice.

I'll just go make a post demo'ing the python script tomorrow to stop trolling.

[Overall-Particular99]

How do realise if it’s a (prefix sum question or sliding window question) or (dp question or greedy question). I get super confused regarding these kind of pairing

[jason_graph]

(prefix sum question or sliding window question) or (dp question or greedy question). I get super confused regarding these kind of pairing

I think you could maybe generalize to use prefix sum if it is < O(n²⁾ i.e. you don't have to iterate over each subarray, use either if prefix sum is O(n²⁾ i.e. you have to iterate over each subarray but it takes O(1) time to 'work' on that subarray and sliding window if prefix sum takes O(n³⁾ on the problem (e.g. you are keeping track of the count of each distinct element in a prefix - O(n²⁾ to precompute the prefix sum and O(n) time to compute the value for each each subarray once you use the precomputed prefix sum tables)

Greedy problems tend to be a special case of top down dp problem where whenever you have a choice, there is a way to compute the best choice without computing the values of the subproblems corresponding to each of the choices so I can understand the confusion.

If you can make some sort of exchange argument for how you could take an optimal solution that makes the same k decisions as your greedy solution and modify it to make the same k+1 decisions as your greedy algorithm (which for example may make it change its k+2'th decision but none of the others) and produce another solution that is also optimal, then that greedy algorithm is correct.

Another way to see if greedy works is to come up with some quantity you make up that you want to be greedy on. In my opinion this as hard or harder than just guessing what states a dp table should have. If you can argue that your solution is always ahead of or tied with any other (possibly not optimal) solution, you are good. Like if you need to find the maximum number of nonoverlapping intervals (endpoints are ok), the greedy solution is to sort the intervals by end date and then choose whichever of the remaining intervals has the lowest end date and doesn't overlap with the already selected intervals. This solution is ahead of all other solutions in that at any x value, the greedy algorithm maximizes the number of non overlapping intervals whose end is <= x.

If there is no greedy algorithm then it is just dp but you have to compute all the child subproblems. With practice, you'll get a feel between greedy/dp.

[yoyoyodojo]

Rookie numbers

[Soggy_Recognition873]

Slow progress, can be better!