This is the framework I’ll use for every post in my Competitive Programming series.

Instead of making each problem explanation long and complicated, I’ll follow the same simple process:

1. Understand the problem
2. Brute force
3. Extract the pattern
4. Design and optimize
5. Test

The goal is not just to show the final code. I want to show how we can go from “I don’t know how to solve this” to a clean solution step by step.

1. Understand the Problem

Before thinking about algorithms, first understand what the problem is asking.

I usually ask:

• What is the input?
• What should I return?
• What exactly counts as a valid answer?
• Are there any important constraints?
• What edge cases can happen?

Try a very small example by hand.

If you cannot explain the problem in simple words, you probably should not start coding yet.

2. Brute Force

Next, forget about optimization.

Ask:

What is the easiest solution I can think of?

Even if it is slow, that’s okay.

The brute-force solution helps us understand:

• what actually needs to happen
• what work is being repeated
• why the solution becomes slow

It also gives us something to compare our optimized solution against.

3. Extract the Pattern

Now look at the brute-force solution and ask:

What am I doing again and again?

This is usually where the real pattern appears.

Repeated work may point toward things like:

• HashMap
• Prefix Sum
• Sliding Window
• Two Pointers
• Dynamic Programming
• Memoization
• Stack
• BFS / DFS

Instead of trying to remember a random algorithm, we first understand why we need it.

4. Design and Optimize

Once the pattern is clear, we can design a better solution.

Ask:

• What information should I remember?
• What work can I avoid repeating?
• Which data structure helps me do that?
• Can I reduce the time complexity?

Then write the optimized solution.

The important part is understanding why the optimization works, not just memorizing the code.

5. Test

Finally, test the solution.

Start with the normal example, then try cases that might break your assumptions.

For example:

• empty input
• one element
• negative numbers
• duplicate values
• very large values
• minimum/maximum constraints

Then check the final:

• Time Complexity
• Space Complexity

Example: Path Sum III — LeetCode 437

1. Understand the Problem

We are given:

• a binary tree
• a target sum

We need to count how many downward paths have a sum equal to the target.

Important detail:

The path does not have to start from the root.

It also does not have to end at a leaf.

For example, if the target is 8, we want to count every downward path whose values add up to 8.

2. Brute Force

The simple idea is:

Start from every node.

From that node, explore every downward path and check whether the sum becomes the target.

Something like:

For every node:
    Start DFS from this node
    Keep adding values
    Count when sum == target

This works.

But there is a problem.

For every node, we may explore many of the same nodes again.

In the worst case:

Time: O(n²)

So now we ask:

What are we repeatedly calculating?

3. Extract the Pattern

While moving from the root to a node, we already know the sum of everything we have seen.

Suppose our current sum is:

currentSum

We want to know whether some previous point existed such that:

currentSum - previousSum = target

Rearrange it:

previousSum = currentSum - target

So if we know how many times:

currentSum - target

has appeared before, we know how many valid paths end at the current node.

This is the same idea as the classic:

Subarray Sum Equals K

pattern.

That tells us we can use:

Prefix Sum + HashMap

4. Design and Optimize

We keep:

currentSum

which is the sum from the root to our current node.

We also keep a HashMap:

Map<Long, Integer> map

The map tells us:

prefix sum → how many times we have seen it

We start with:

map.put(0L, 1);

Why?

Because if:

currentSum == target

then:

currentSum - target == 0

and the path starting from the root should be counted.

Now at every node:

currentSum += node.val;

Then check:

currentSum - target

inside the map.

int totalPath =
    map.getOrDefault(currentSum - targetSum, 0);

Then add the current prefix sum:

map.put(
    currentSum,
    map.getOrDefault(currentSum, 0) + 1
);

Explore the children:

totalPath += dfs(node.left, ...);
totalPath += dfs(node.right, ...);

And when leaving the node, remove the current prefix sum:

map.put(currentSum, map.get(currentSum) - 1);

This last step is very important.

Why?

Because the prefix sums from the left subtree should not affect the right subtree.

Each path must follow one valid parent-to-child direction.

So we add the prefix sum when entering a node and remove it when leaving.

This is backtracking.

Final Code

class Solution {

    public int pathSum(TreeNode root, int targetSum) {

        Map<Long, Integer> map = new HashMap<>();

        map.put(0L, 1);

        return dfs(root, 0L, targetSum, map);
    }

    private int dfs(
        TreeNode node,
        long currentSum,
        int targetSum,
        Map<Long, Integer> map
    ) {

        if (node == null) {
            return 0;
        }

        currentSum += node.val;

        int totalPath =
            map.getOrDefault(currentSum - targetSum, 0);

        map.put(
            currentSum,
            map.getOrDefault(currentSum, 0) + 1
        );

        totalPath += dfs(
            node.left,
            currentSum,
            targetSum,
            map
        );

        totalPath += dfs(
            node.right,
            currentSum,
            targetSum,
            map
        );

        // Backtrack
        map.put(
            currentSum,
            map.get(currentSum) - 1
        );

        return totalPath;
    }
}

5. Test

Single node

Tree: [8]
Target: 8

Answer:

1

Negative values

Negative numbers are allowed.

That is why we cannot use approaches that assume the sum only increases.

Prefix sums still work correctly.

Left and right subtrees

We must make sure prefix sums from the left subtree do not stay in the map when we move into the right subtree.

That is why this line is necessary:

map.put(currentSum, map.get(currentSum) - 1);

Large sums

We use:

long currentSum

instead of:

int currentSum

because adding many node values could overflow an int.

Complexity

Brute Force

Time:  O(n²)
Space: O(h)

where h is the height of the tree.

Optimized

Time:  O(n)
Space: O(n)

Each node is visited once.

The HashMap uses extra memory, but it saves us from repeating the same work.

The Main Pattern

For future problems, this is the process I want to follow:

Understand
    ↓
What are the inputs and outputs?
What are the edge cases?

Brute Force
    ↓
What is the simplest solution?

Extract the Pattern
    ↓
What work am I repeating?
What information should I remember?

Design and Optimize
    ↓
Which algorithm/data structure removes that repeated work?

Test
    ↓
Normal case
Edge cases
Time complexity
Space complexity

The most important question is usually:

What is the brute-force solution doing repeatedly?

Once you can answer that, the optimized pattern often becomes much easier to see.

Every Problem Breakdown in this series will follow this same structure:

Understand → Brute Force → Extract the Pattern → Design & Optimize → Test