Work out a solution

Every speedup should fix a specific problem in a slow solution that already works. "Too slow" isn't specific enough. Ask: does it search old elements again and again? Recompute a sum that overlaps the last one? Explore different paths that lead to the same place? Keep options that can never beat another option?

Take the problem of finding two values that add up to a target. Checking every pair is O(n²). But for each value x, the real question is "have I seen target − x before?" A hash map answers that without searching. The arithmetic gives you the key to look up, and the lookup tells you to use a hash map.

Now take the largest sum of a subarray. If the running sum so far is negative, adding it to anything that comes next only makes that smaller. Starting fresh is always at least as good. To justify dropping an option like this, compare it with the alternative under every possible future. If it's never better, you can drop it.

To show a loop is correct, name something it keeps true, then check three things:

1. It starts true before the first step.
2. Each step keeps it true.
3. When the loop ends, that fact gives you the answer.

"The window is valid" isn't enough to prove you found the best answer. You also have to explain why the windows you skipped couldn't have been better.

For recursion, say exactly what one call takes and returns. Assume smaller calls do their job, and show how their results give you this call's answer. For a greedy choice, show that swapping in your choice never makes the answer worse. For dynamic programming, show that your state holds everything the rest of the problem needs, that your transitions cover every case, and that you fill the table in an order where each value's inputs are ready.

Count the cost from what the code actually does. A loop inside a loop isn't always O(n²). If a pointer moves forward at most n times over the whole run, those moves add up to O(n). In the other direction, slicing, copying, hashing a long string, or copying a path adds work you can't see from the loops.

The limits in a problem rule out some approaches, but they don't pick one for you. No single operation count works as a cutoff across languages, machines, and judges. Remember to count the size of the output and the recursion stack too.