Problem Decomposition

Problem decomposition is the skill of turning a vague prompt into smaller, testable parts: constraints, input model, edge cases, invariants, and a step-by-step solution shape.

1. Definition

What is problem decomposition?

Problem decomposition means breaking a coding problem into smaller decisions before writing the full algorithm.

In interview-style problems, that usually means answering questions like:

• what is the exact input,
• what must the output contain,
• what constraints matter,
• what edge cases can break the logic,
• and what invariant should stay true while the algorithm runs.

Why does it exist?

Most wrong solutions are not wrong because the candidate cannot code.

They are wrong because the candidate started coding too early.

When the prompt is decomposed first, the solution space becomes smaller and more manageable.

Where does it fit?

Problem decomposition sits between reading the statement and choosing the algorithm.

The usual healthy sequence is:

1. parse the prompt,
2. model the inputs and outputs,
3. identify constraints,
4. list edge cases,
5. define the state or invariant,
6. only then implement.

What decomposition is NOT

Problem decomposition is not:

• writing pseudocode immediately,
• repeating the prompt in different words,
• guessing the pattern from the title alone,
• or overengineering the problem before understanding it.

It is a thinking discipline.

Why this matters in LeetCode and interviews

LeetCode-style questions reward the person who sees the structure of the task.

A strong candidate does not just ask, “Which pattern is this?”

A strong candidate also asks:

• what is the data shape,
• what information must be preserved,
• what can be processed locally,
• and what can be deferred or precomputed.

That is exactly what decomposition gives you.

2. Core Concepts

The key questions

Before solving, lock down five things:

1. Input model — size, value range, sorting, duplicates, and any character or structure assumptions.
2. Output model — one answer or many, index or value, preserved order or not, and what happens when no answer exists.
3. Constraints — the scale signals whether brute force, linear scans, sorting, or extra memory are realistic.
4. Edge cases — empty input, one item, repeated values, impossible answers, and boundary values should be named early.
5. Core state — the minimum information that must survive from one step to the next.

State, invariants, and transitions

Most clean solutions are built from three pieces:

• State: current index, running sum, minimum so far, window bounds, frequency map, or best answer so far.
• Invariant: the fact that remains true after every step, such as “best stores the best answer seen so far” or “the current window is valid”.
• Transition: the update rule that changes the state when the next element arrives.

If you can describe those three clearly, the final code is usually much easier to trust.

Reframing and subproblems

Many tasks unlock when rewritten as smaller operational questions:

• “find duplicates” → “have I seen this value before?”
• “maximize profit” → “what is the cheapest value seen so far?”
• “longest valid segment” → “how do I keep a valid window?”
• “count ways” → “how many ways reach this state?”

That reframing often reveals whether you need a prefix summary, local state, a complement lookup, or a dynamic-programming subproblem.

Information preservation and failure conditions

You usually do not need the full history. Ask what must survive:

• latest index,
• smallest value so far,
• seen-count map,
• or whether a boundary has already been crossed.

Also name what would break the approach:

• future information that a local greedy choice cannot see,
• sorted-input assumptions on unsorted data,
• one-pass logic when future context is required,
• or in-place updates when original values are still needed.

Practical decomposition checklist

1. Identify input and output shape.
2. Read constraints for scale.
3. List at least three edge cases.
4. Define the smallest useful state.
5. State the invariant.
6. Choose a baseline.
7. Optimize only if the constraints demand it.

3. Practical Usage

When to lean on decomposition

Use explicit decomposition when the prompt is wordy, has mixed conditions, contains hidden assumptions, or you are unsure which pattern applies. It is especially useful when off-by-one bugs or output misunderstandings keep showing up.

When to keep it lightweight

Do not turn it into ceremony. For a small and obvious task, the input shape, one important edge case, and the invariant may already be enough. The goal is clarity, not paperwork.

A strong interview workflow

A solid interview narration often sounds like this:

1. restate input and output,
2. call out the important constraint,
3. list the main edge cases,
4. define the state and invariant,
5. present a baseline,
6. then improve only if needed.

That narration already signals strong thinking.

Baseline, branching, and review

The baseline gives you a correctness anchor and a visible optimization target. Constraints then tell you whether to stay simple, move toward linear thinking, or use extra memory such as a map or counting array. In pair-programming or code review, say out loud what you are modeling, what the state means, which edge case is risky, and which assumption is undocumented.

Related LeetCode problems

These problems reward decomposition discipline over raw pattern matching:

• LeetCode #121 — Best Time to Buy and Sell Stock — reframing "maximize profit" into running-minimum state.
• LeetCode #53 — Maximum Subarray — invariant-driven scan (Kadane's algorithm).
• LeetCode #1 — Two Sum — clarifying the output contract (indices, not values).
• LeetCode #125 — Valid Palindrome — normalization + edge-case awareness.
• LeetCode #88 — Merge Sorted Array — decomposition of pointer roles.

One practical rule

If a problem feels messy, the answer is usually not a more clever loop. It is usually a cleaner decomposition.

4. Code Examples

Basic Example — checking whether an array is non-decreasing

This is a simple example, but it shows good decomposition.

We can phrase the task as:

• input: integer array,
• output: boolean,
• edge cases: empty and single-element arrays,
• invariant: every adjacent pair seen so far satisfies nums[i - 1] <= nums[i].

public class NonDecreasingCheck {
    public static boolean isNonDecreasing(int[] nums) {
        if (nums == null || nums.length <= 1) {
            return true;
        }

        for (int index = 1; index < nums.length; index++) {
            if (nums[index - 1] > nums[index]) {
                return false;
            }
        }

        return true;
    }
}

Complexity: time O(n) — one pass through the array; extra space O(1).

Why this decomposition works:

• the output is a simple boolean,
• the only relationship that matters is adjacent order,
• and the invariant is tiny and easy to verify.

Advanced Example — maximum subarray sum (Kadane's algorithm)

This is a classic decomposition problem because the prompt invites nested-loop thinking.

The useful reframing is:

• at each position, should I extend the previous subarray or start fresh here?
• and what is the best sum seen across all positions?

The state becomes:

• currentSum — best sum ending at the current position,
• bestSum — best sum seen so far across the whole array.

The invariant becomes:

• currentSum is the maximum of nums[i] alone vs extending from previous,
• bestSum is the global maximum of all currentSum values.

public class MaximumSubarray {
    public static int maxSubArray(int[] nums) {
        if (nums == null || nums.length == 0) {
            throw new IllegalArgumentException("array must not be empty");
        }

        int currentSum = nums[0];
        int bestSum = nums[0];

        for (int index = 1; index < nums.length; index++) {
            currentSum = Math.max(nums[index], currentSum + nums[index]);

            if (currentSum > bestSum) {
                bestSum = currentSum;
            }
        }

        return bestSum;
    }
}

Complexity: time O(n) — one pass through the array; extra space O(1).

What decomposition saved us from:

• checking every (i, j) pair which would be O(n²),
• confusing "sum ending here" with "global best" state,
• and forgetting that all-negative arrays still have a valid answer.

Advanced Example — longest run of equal characters

This example highlights state and transitions.

Useful decomposition:

• input: string,
• output: length of the longest consecutive run,
• edge cases: empty string and one-character string,
• state: currentRunLength, bestRunLength, previousChar.

public class LongestRun {
    public static int longestRun(String text) {
        if (text == null || text.isEmpty()) {
            return 0;
        }

        int currentRunLength = 1;
        int bestRunLength = 1;
        char previousChar = text.charAt(0);

        for (int index = 1; index < text.length(); index++) {
            char currentChar = text.charAt(index);

            if (currentChar == previousChar) {
                currentRunLength++;
            } else {
                currentRunLength = 1;
                previousChar = currentChar;
            }

            if (currentRunLength > bestRunLength) {
                bestRunLength = currentRunLength;
            }
        }

        return bestRunLength;
    }
}

Complexity: time O(n) — one pass through characters; extra space O(1).

This is not about syntax.

It is about recognizing exactly which information must survive from one step to the next.

Common Pitfall — coding before clarifying output rules

A common mistake is to solve a different problem from the one asked.

public class PairSumPitfall {
    public static int[] findPair(int[] nums, int target) {
        for (int left = 0; left < nums.length; left++) {
            for (int right = left + 1; right < nums.length; right++) {
                if (nums[left] + nums[right] == target) {
                    return new int[] {nums[left], nums[right]};
                }
            }
        }

        return new int[] {-1, -1};
    }
}

This may be wrong if the prompt asked for:

• indices instead of values,
• one-based indexing,
• preserving original order,
• or throwing an error when no solution exists.

A decomposition-first correction starts by clarifying the contract.

public class PairSumFixed {
    public static int[] findPairIndices(int[] nums, int target) {
        if (nums == null || nums.length < 2) {
            return new int[] {-1, -1};
        }

        for (int left = 0; left < nums.length; left++) {
            for (int right = left + 1; right < nums.length; right++) {
                if (nums[left] + nums[right] == target) {
                    return new int[] {left, right};
                }
            }
        }

        return new int[] {-1, -1};
    }
}

The code is still simple.

The difference is that now it solves the right task.

5. Trade-offs

Aspect	Details
⚡ Performance	Decomposition often reveals the real bottleneck early, so you avoid optimizing the wrong thing.
💾 Memory	Better problem modeling often shows whether a map, prefix array, or extra buffer is actually necessary.
🔧 Maintainability	A decomposed solution is easier to explain, review, and debug because the state and invariants are explicit.
🔄 Flexibility	Clear decomposition makes it easier to adapt the same logic to variant prompts with slightly different output or constraint rules.

Performance trade-off: Spending one minute to decompose the prompt usually saves much more than one minute of debugging.

Memory trade-off: If you know exactly what information must survive, you often avoid storing unnecessary history.

Maintainability trade-off: The fastest-to-write loop is not always the easiest-to-review solution.

Flexibility trade-off: A solution built on a clear contract survives prompt variations better than a pattern guessed too early.

6. Common Mistakes

1. Jumping to a pattern too early
   Seeing “array” and immediately choosing two pointers or a hash map is risky. First confirm the input shape, constraints, and output contract.

2. Ignoring the output contract
   Returning values instead of indices, or one valid answer instead of all valid answers, can invalidate an otherwise good algorithm.

3. Skipping edge cases
   Empty input, one element, duplicates, and impossible answers often expose hidden bugs immediately.

4. Using too much state
   Many beginners carry more information than necessary. Good decomposition tries to find the smallest state that still preserves correctness.

5. Not stating the invariant
   If you cannot explain what remains true during the loop, you are more likely to break it accidentally.

6. Treating constraints as decoration
   Constraints should guide design. If n is huge, quadratic work needs explicit justification.

7. Optimizing before having a correct baseline
   A correct brute-force or scan-based baseline is often the cleanest way to understand what really needs improvement.

7. Deep Dive

How experienced engineers decompose problems

Experienced engineers usually decompose at multiple layers.

They ask:

• what is the formal contract,
• what is the smallest useful state,
• what assumption does the solution rely on,
• what breaks if the prompt changes slightly,
• and what would a simpler baseline look like?

That layered thinking is why they look calm in front of messy prompts.

Constraints are really about risk

A constraint does not just say what is allowed.

It also says what is risky.

For example:

• n = 10^5 makes nested loops suspicious,
• large numeric ranges make direct counting arrays suspicious,
• and online or streaming input makes “sort first” impossible.

Good decomposition is risk-aware, not just pattern-aware.

Invariants are design anchors

Many interview solutions look magical until you state the invariant.

Once the invariant is visible, the loop becomes much less mysterious.

For example:

• in a running-minimum scan, the minimum truly is the minimum seen so far,
• in a sliding window, the current window is valid by construction,
• in prefix-sum logic, accumulated state summarizes the processed prefix correctly.

That is why saying the invariant out loud is a senior habit.

Edge cases are miniature adversarial tests

An edge case is not just a boring checklist item.

It is a tiny adversary.

If the solution survives:

• empty input,
• one item,
• repeated boundaries,
• and impossible targets,

then the core model is usually becoming trustworthy.

Reframing is often the real unlock

A lot of progress happens when the question is rewritten in a more mechanical form.

Examples:

• “Can I complete the answer with information already seen?”
• “What is the cheapest prefix summary I can maintain?”
• “What property must remain true after every step?”
• “Do I need global information, or is local state enough?”

This is often the bridge from confusion to pattern recognition.

The debugging advantage

Decomposition is also powerful after the first wrong answer.

When a solution fails, decompose the failure:

• is the input contract misunderstood,
• is the state incomplete,
• is the transition wrong,
• is the invariant false,
• or is an edge case missing?

That debugging path is much faster than random patching.

The interview communication advantage

Interviewers often reward thought quality, not just final code.

If you say:

• what the contract is,
• what edge cases you considered,
• what invariant you want,
• and why the chosen state is sufficient,

then even before the code is complete, your thinking already looks strong.

8. Interview Questions

Q: What is problem decomposition in algorithm interviews?
A: It is the process of turning the prompt into smaller decisions such as input/output modeling, constraints, edge cases, state, and invariants before implementing the algorithm.

Q: Why are constraints so important?
A: Because constraints eliminate unrealistic solutions and tell you what complexity range is acceptable.

Q: What is an invariant in plain language?
A: It is a property that remains true throughout the algorithm, giving you a stable reason why the loop is correct.

Q: Why should you start with a baseline solution?
A: Because a baseline clarifies the task and exposes what truly needs optimization instead of forcing premature cleverness.

Q: What is a common sign that decomposition is missing?
A: When you start coding quickly but cannot clearly explain the output contract, edge cases, or the meaning of your state variables.

9. Glossary

Term	Definition
contract	The precise input-output behavior the function must satisfy.
edge case	A boundary or unusual input that tests the correctness of the logic.
invariant	A property that remains true during execution.
state	The information carried across steps of the algorithm.
transition	The update rule that transforms one state into the next.
baseline	A simple first solution used to understand correctness and complexity before optimizing.
reframing	Restating the prompt in a more operational form that is easier to solve.

10. Cheatsheet

• Model input and output before choosing a pattern.
• Read constraints as design signals, not decoration.
• List at least three edge cases early.
• Define the smallest useful state.
• State the invariant in one sentence.
• Describe the transition from one step to the next.
• Start with a baseline before optimizing.
• Reframe vague prompts into operational questions.
• If debugging is hard, decompose the failure, not just the code.
• Strong interview answers explain the reasoning contract, not only the loop.