DSA Tutorial

🔍

Stack Basics Stack Operations Stack Implementation Stack Collection Frameworks Balanced Parentheses Expression Evaluation Monotonic Stack Practice Problems

Queue Basics Queue Operations Queue Implementation Queue Collection Frameworks Circular Queue Deque Priority Queue Queue in BFS Practice Problems

Tree Basics & Terminologies Types of Trees Binary Tree Basics & Types Binary Tree DFS Traversals BFS / Level Order Traversal Binary Tree Operations Binary Tree Practice Problems BST Basics BST DFS Traversals BST BFS Traversal BST Operations BST Practice Problems Heap Trie Advanced Trees

Graph Basics and Terminologies Graph Representation Types of Graphs Breadth First Search (BFS)Depth First Search (DFS)Connected Components Cycle Detection Topological Sort Shortest Path Algorithms Dijkstra's Algorithm Minimum Spanning Tree Union Find (DSU)Practice Problems

Backtracking Basics Decision Tree Thinking Time & Space Complexity Subsets Permutations Combination Problems N-Queens Sudoku Solver Word Search Common Mistakes Practice Problems

DP Basics State Transition Thinking Memoization Tabulation Memoization vs Tabulation 1D Dynamic Programming 2D Dynamic Programming Knapsack Pattern Longest Common Subsequence (LCS)Longest Increasing Subsequence (LIS)Practice Problems

Two Pointers Sliding Window Fast & Slow Pointers Prefix Sum Hashing Pattern Binary Search Pattern Greedy Pattern Divide & Conquer Heap Pattern Monotonic Stack & Queue Practice Problems

Top 100 DSA Problems Blind 75 NeetCode 150 Pattern → Problem Map Easy → Medium Roadmap Medium → Hard Roadmap FAANG Question Bank Mock Interviews

Weekly Revision Plan Spaced Repetition Guide Mixed Problem Sets Mock Interview Schedule Self Assessment Checklist

How to Approach Problems

Why Most Beginners Struggle

Most beginners do not struggle because they lack intelligence or effort. They struggle because they have no system.

When they see a new problem, they immediately try to write code. They pattern-match to something vaguely similar they have seen before. They get stuck, read the solution, tell themselves they "just need to practice more," and repeat the cycle — without ever improving their problem-solving process.

The developers who interview well are not the ones who have memorized the most solutions. They are the ones who have a repeatable system they can apply to any problem, including ones they have never seen before.

This topic gives you that system. It is the same thinking process experienced engineers use in real interviews — and the same process that, when practiced consistently, turns unfamiliar problems into solvable ones.

The Six-Step Problem Solving Framework

Every problem, regardless of difficulty, can be approached through these six steps in order:

›Understand the problem completely before writing anything
›Work through examples by hand
›Identify the brute force solution
›Analyze the bottleneck
›Optimize using patterns and observations
›Code, test, and validate

Skipping any step — especially the first three — is the most common reason developers get stuck or write incorrect solutions. Each step feeds the next. You cannot optimize what you do not fully understand.

Step 1: Understand the Problem Completely

Before touching a keyboard, read the problem until you can explain it in your own words without looking at it.

Ask yourself:

›What exactly is the input? What type is it — array, string, integer, graph?
›What exactly is the output? A number, a boolean, a modified array?
›What are the constraints? How large can n be? Can values be negative? Can the input be empty?
›What edge cases are possible? Empty input, single element, all duplicates, already sorted?

In an interview, repeat the problem back to the interviewer in your own words before you start. This confirms your understanding and often reveals assumptions you were making incorrectly.

The most expensive mistake in problem solving is spending 20 minutes on the wrong problem because you misread one word.

Step 2: Work Through Examples by Hand

Pick a small, concrete input and trace through what the correct output should be — manually, without code.

This step does three things:

›Confirms you actually understand what the problem is asking
›Reveals the logic you will need to implement
›Gives you test cases you can use to validate your solution later

Use at least three examples: a normal case, an edge case (empty or single element), and a tricky case (duplicates, all same values, negative numbers).

Example problem: Find all elements that appear more than once in an array.

Input: [1, 2, 3, 2, 4, 3, 5]

Manual trace:
  1 appears: 1 time  → not a duplicate
  2 appears: 2 times → duplicate
  3 appears: 2 times → duplicate
  4 appears: 1 time  → not a duplicate
  5 appears: 1 time  → not a duplicate

Output: [2, 3]

Edge case — empty array:  [] → output []
Edge case — no duplicates: [1, 2, 3] → output []
Edge case — all same: [5, 5, 5] → output [5]

Only after you can produce the correct output manually are you ready to think about how to implement it.

Step 3: Identify the Brute Force Solution

Every problem has an obvious, naive solution. Find it first — even if it is slow.

The brute force is valuable for three reasons:

›It is almost always correct, giving you a working baseline
›It clarifies the logic before you worry about efficiency
›It gives you something to compare your optimized solution against

State the brute force approach in plain English before writing any code. If you cannot explain it in words, you do not understand it well enough to code it.

Brute force for finding duplicates:

For each element in the array:
  Count how many times it appears by scanning the entire array
  If the count is greater than 1, it is a duplicate

Time: O(n²) — for each of n elements, scan n elements
Space: O(n) — storing the result list

In interviews, always state the brute force first even if you know a better solution. It shows you can think through problems methodically and gives the interviewer a starting point to guide you.

Step 4: Analyze the Bottleneck

Once you have a brute force, ask: what is the slowest part? What is doing the most unnecessary repeated work?

This is the most important thinking step. The bottleneck almost always points directly at the optimization.

Brute force bottleneck analysis:

For each element (outer loop — n iterations):
  Scan entire array to count occurrences (inner loop — n iterations)

Bottleneck: we are rescanning the entire array for every element.
            We are counting the same elements multiple times.

Observation: what if we counted every element's frequency in a single pass?
             Then lookups would be O(1) instead of O(n).

This observation leads directly to using a Hash Map.

The shift from "rescanning every time" to "precompute and look up" is one of the most common optimization patterns in all of DSA. The bottleneck analysis is what reveals it.

Step 5: Optimize Using Patterns

Once you know the bottleneck, look for a pattern or data structure that removes it.

Over time, you will notice that most bottlenecks fall into a small number of categories, and each category has a corresponding fix:

Bottleneck	Optimization	Pattern
Rescanning for a value	Precompute into a hash map	Hashing
Comparing every pair	Sort first, then use two pointers	Two Pointers
Repeated subarray computation	Track a running window	Sliding Window
Recomputing overlapping subproblems	Cache results	Dynamic Programming
Searching unsorted data	Sort first, then binary search	Binary Search
Tracking minimum or maximum dynamically	Use a heap	Heap
Graph connectivity or cycles	DFS or BFS	Graph Traversal

Recognizing which bottleneck category you are in is the core interview skill. It comes from practice — but only if you are consciously analyzing the bottleneck, not just memorizing solutions.

Step 6: Code, Test, and Validate

Only after steps 1 through 5 are complete should you write code.

Start with a clean structure. Write readable, well-named code — not clever one-liners. Code that is easy to read is easy to debug.

After writing, test with the examples you created in Step 2. Then test with edge cases. Trace through your code manually on a small input if the output looks wrong.

State the final time and space complexity before the interviewer asks.

Putting It All Together: Finding Duplicates

Let us apply all six steps to a complete problem.

Problem: Given an integer array, return all elements that appear more than once. Each duplicate should appear only once in the output.

Step 1 — Understand: Input is an integer array. Output is an array of elements that appear more than once. Each duplicate reported once regardless of how many times it appears.

Step 2 — Examples by hand: Already done above in the trace.

Step 3 — Brute force: For each element, scan the full array to count occurrences. O(n²) time, O(n) space.

Step 4 — Bottleneck: Rescanning the full array n times is wasteful. We are counting the same elements repeatedly.

Step 5 — Optimize: One pass with a hash map to count frequencies. One more pass to collect elements with count greater than 1. Total: O(n) time, O(n) space.

Step 6 — Code:

Java

Try it out

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class FindDuplicates {

    public static List<Integer> findDuplicates(int[] arr) {
        // Step 1: Count frequency of each element in one pass — O(n)
        Map<Integer, Integer> frequency = new HashMap<>();

        for (int num : arr) {
            frequency.put(num, frequency.getOrDefault(num, 0) + 1);
        }

        // Step 2: Collect elements that appear more than once — O(n)
        List<Integer> duplicates = new ArrayList<>();

        for (Map.Entry<Integer, Integer> entry : frequency.entrySet()) {
            if (entry.getValue() > 1) {
                duplicates.add(entry.getKey());
            }
        }

        return duplicates;
    }

    public static void main(String[] args) {
        int[] input = {1, 2, 3, 2, 4, 3, 5};
        List<Integer> result = findDuplicates(input);
        System.out.println("Duplicates: " + result);

        int[] nodup = {1, 2, 3};
        System.out.println("No duplicates: " + findDuplicates(nodup));

        int[] empty = {};
        System.out.println("Empty array: " + findDuplicates(empty));
    }
}

Output:
Duplicates: [2, 3]
No duplicates: []
Empty array: []

Dry Run: Hash Map Frequency Count on [1, 2, 3, 2, 4, 3, 5]

Pass 1 — Build frequency map:
  num=1 → frequency: {1:1}
  num=2 → frequency: {1:1, 2:1}
  num=3 → frequency: {1:1, 2:1, 3:1}
  num=2 → frequency: {1:1, 2:2, 3:1}
  num=4 → frequency: {1:1, 2:2, 3:1, 4:1}
  num=3 → frequency: {1:1, 2:2, 3:2, 4:1}
  num=5 → frequency: {1:1, 2:2, 3:2, 4:1, 5:1}

Pass 2 — Collect duplicates (count > 1):
  1 → count=1 → skip
  2 → count=2 → add to result
  3 → count=2 → add to result
  4 → count=1 → skip
  5 → count=1 → skip

Result: [2, 3]

Complexity:
  Time:  O(n) + O(n) = O(n)
  Space: O(n)  — frequency map holds up to n entries

How to Recognize Patterns

One of the highest-leverage skills in DSA is recognizing which algorithmic pattern applies to a problem before you start solving it. Every problem contains clues in its structure, wording, and constraints.

Here are the most reliable clues and what they signal:

Clue: "Find a pair that satisfies a condition"

This almost always suggests Two Pointers (on sorted data) or Hashing (for unsorted data).

"Find two numbers that sum to target"
"Find a pair with minimum difference"
→ Sort first → Two Pointers: O(n log n)
→ Or use a Hash Set for O(n)

Clue: "Subarray or substring with a property"

This almost always suggests Sliding Window or Prefix Sum.

"Longest subarray with sum ≤ k"
"Smallest subarray with sum ≥ target"
→ Sliding Window: O(n)

"How many subarrays have sum equal to k?"
→ Prefix Sum + Hash Map: O(n)

Clue: "Find something in a sorted array"

This almost always suggests Binary Search.

"Find the first element greater than x in sorted array"
"Find minimum in rotated sorted array"
→ Binary Search: O(log n)

Clue: "All combinations, subsets, or permutations"

This almost always suggests Backtracking or Recursion.

"Generate all subsets of an array"
"Find all valid combinations that sum to target"
→ Backtracking: O(2^n) or O(n!)

Clue: "Optimal value — minimum cost, maximum profit"

This often suggests Dynamic Programming or Greedy.

"Minimum number of coins to make change"
"Maximum profit from stock prices"
→ DP if choices have overlapping subproblems
→ Greedy if local optimal always leads to global optimal

Clue: "Connected components, shortest path, cycles"

This always suggests Graph traversal — BFS or DFS.

"Number of islands in a grid"
"Shortest path between two nodes"
→ BFS for shortest path (unweighted)
→ DFS for connectivity, cycles, topological order

Learning to match clues to patterns is what makes the jump from "I have never seen this problem" to "I know exactly where to start."

How to Communicate During an Interview

Strong problem-solving communication is as important as getting the right answer. Interviewers are evaluating your thinking process, not just your output.

Follow this communication pattern:

Restate the problem. "So we are given an integer array and need to return all elements that appear more than once. Each duplicate should appear once in the output. Is that correct?"

State the brute force. "A naive approach would be to check the frequency of each element by scanning the entire array for each one, giving O(n²) time. Let me think about a better approach."

State the bottleneck and your observation. "The bottleneck is the repeated scanning. If I count frequencies in one pass using a hash map, I can reduce that to O(n)."

Walk through your approach. "I will do two passes: first build a frequency map, then collect all entries with count greater than one."

Code while narrating. Say what each block does as you write it. Do not code in silence.

State complexity at the end. "This runs in O(n) time and O(n) space because the hash map stores at most n entries."

Test with your examples. Walk through the code manually with the examples you prepared in step 2.

This structure shows organized thinking, technical depth, and communication skills — all of which interviewers evaluate simultaneously.

Brute Force vs Optimal: A Side-by-Side View

Seeing brute force and optimal side by side — with the same problem — reinforces why the six-step framework works. The brute force clarifies the logic. The optimization removes the bottleneck.

Java

Try it out

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class BruteVsOptimal {

    // Brute Force — O(n²) time, O(n) space
    // For each element, scan entire array to count occurrences
    public static List<Integer> bruteForce(int[] arr) {
        List<Integer> result = new ArrayList<>();

        for (int i = 0; i < arr.length; i++) {
            int count = 0;

            // Rescan entire array for each element — the bottleneck
            for (int j = 0; j < arr.length; j++) {
                if (arr[j] == arr[i]) count++;
            }

            if (count > 1 && !result.contains(arr[i])) {
                result.add(arr[i]);
            }
        }

        return result;
    }

    // Optimal — O(n) time, O(n) space
    // Single pass to build frequency map, single pass to collect duplicates
    public static List<Integer> optimal(int[] arr) {
        Map<Integer, Integer> freq = new HashMap<>();
        for (int num : arr) freq.put(num, freq.getOrDefault(num, 0) + 1);

        List<Integer> result = new ArrayList<>();
        for (Map.Entry<Integer, Integer> e : freq.entrySet()) {
            if (e.getValue() > 1) result.add(e.getKey());
        }

        return result;
    }

    public static void main(String[] args) {
        int[] input = {1, 2, 3, 2, 4, 3, 5};
        System.out.println("Brute Force: " + bruteForce(input));
        System.out.println("Optimal:     " + optimal(input));
    }
}

Output:
Brute Force: [2, 3]
Optimal:     [2, 3]

Both produce the same output. The difference is entirely in efficiency:

Approach     Time     Space   Operations for n=1,000,000
Brute Force  O(n²)   O(n)    1,000,000,000,000 (one trillion)
Optimal      O(n)    O(n)    2,000,000          (two million)

Same output. 500,000x fewer operations.

How to Handle Being Stuck

Getting stuck is normal — even for experienced engineers. What separates strong candidates from weak ones is how they handle it.

When you are stuck, work through this checklist in order:

Re-read the problem. Confirm you understand what is actually being asked. Many blocks come from solving the wrong problem.

Try a simpler version. If the problem feels overwhelming, solve it for n=3 or n=4 manually. The pattern often reveals itself at small scale.

Look for structure in the input. Is it sorted? Does it have repeated elements? Are values bounded? Input structure almost always hints at the approach.

Think about what information you are missing. If you had to solve the problem optimally, what would you need to know at each step? Often this reveals the data structure you need.

State what you do know. Out loud or in writing, say: "I know the input is an array. I know I need to find duplicates. I know a brute force approach works in O(n²). I know the bottleneck is repeated scanning." Speaking forces clarity.

Try a different angle. If you are trying to solve forward (input to output), try backward (what does the output look like? what must be true just before producing it?).

Struggling with a problem for 10 minutes and reaching the solution through systematic thinking is more valuable for growth than reading a solution immediately. The struggle builds the pattern recognition you need.

Common Mistakes Beginners Make

Starting to code before fully understanding the problem. This is the single most common mistake. Spending two minutes carefully understanding saves ten minutes of debugging wrong code.

Skipping the brute force because it feels too slow. The brute force clarifies your logic. An O(n²) solution you can explain completely is a far better foundation for optimization than a half-understood O(n) approach.

Jumping to optimization without naming the bottleneck. Optimization without bottleneck analysis is guessing. Name exactly what is slow and why before you propose a fix.

Testing only the happy path. Writing code that works on [1, 2, 3, 2] but crashes on [] is a bug, not a solution. Always test edge cases — empty input, single element, all duplicates, all unique.

Staying silent in interviews. Interviewers cannot evaluate thinking they cannot hear. Narrate every step. A wrong answer communicated clearly often scores better than a correct answer arrived at silently.

Treating patterns as solutions instead of starting points. Knowing "this looks like a sliding window problem" is valuable. But every problem has constraints that modify the standard pattern. Apply patterns thoughtfully, not mechanically.

Interview Questions

Q: How should you begin approaching a problem you have never seen before?

Start by reading the problem until you can restate it in your own words. Identify the input type, output type, constraints, and edge cases. Work through two or three small examples by hand to confirm your understanding. Only then consider algorithms — starting with the brute force. The most important thing is to avoid writing code before you understand what you are trying to produce.

Q: Why should you always state the brute force solution first in an interview?

The brute force demonstrates that you can solve the problem correctly before worrying about efficiency. It shows methodical thinking. It gives the interviewer a baseline to discuss optimization from. And it reveals the bottleneck — which is the direct path to the optimized solution. Jumping straight to an optimal solution you cannot fully explain is riskier than stating a clear brute force and improving it.

Q: How do input constraints help you choose an algorithm?

Constraints bound the input size n, which tells you which complexities are acceptable. If n is one million, O(n²) is too slow and O(n) or O(n log n) is required. If the problem says the array is sorted, binary search becomes viable. If values are bounded between 1 and 1000, a frequency array may be faster than a hash map. Constraints are hints — reading them carefully often reveals the intended approach.

Q: What is the difference between recognizing a pattern and solving a problem?

Recognizing a pattern tells you where to start. Solving the problem requires adapting that pattern to the specific constraints, edge cases, and output format of this particular problem. Two problems that both use sliding window may require completely different window validity conditions. Pattern recognition is a starting point, not a shortcut around thinking.

FAQs

How many problems do I need to solve before I get good at this?

Quality of practice matters more than quantity. Solving 50 problems while consciously applying the six steps — understanding, examples, brute force, bottleneck, optimize, test — builds more skill than solving 200 problems by reading solutions. If you can explain why your solution works and what the bottleneck of the brute force was, you did the problem correctly.

What should I do when I get a problem completely wrong?

Do not just read the solution and move on. First, understand where your approach diverged from correct thinking — was it in understanding the problem, the brute force logic, or the optimization step? Re-solve the problem from scratch without looking at the solution. Then solve one or two similar problems within 48 hours while the pattern is fresh.

Should I memorize common patterns?

You should understand them deeply enough that you recognize them, not memorize implementations. Knowing that "find two numbers summing to a target in an unsorted array" maps to hashing is valuable. Being able to reconstruct the hash map approach from understanding is what you need. Memorizing code without understanding why it works breaks down on modified versions of the same problem.

How do I get faster at recognizing patterns?

After solving each problem — even ones you solved correctly — write one sentence identifying which pattern it used and why the input structure pointed to that pattern. After 30 to 40 problems of this deliberate labeling, the recognition becomes intuitive. You start seeing the pattern in the problem statement before you have thought about the algorithm at all.

Quick Quiz

Question 1: You are asked to find the longest subarray with a sum less than or equal to k. What is the first thing you should do?

›A) Start coding a nested loop solution
›B) Search for the optimal algorithm
›C) Work through a small example by hand to confirm you understand the problem
›D) Identify the pattern immediately and implement it

Answer: C) Work through a small example by hand. Understanding the problem concretely before thinking about algorithms is always step one. After working through examples, the sliding window pattern becomes obvious from the structure of the problem.

Question 2: Your brute force solution for a problem runs in O(n²). The bottleneck is that you repeatedly scan the array to check if a value has been seen. What optimization does this suggest?

›A) Sort the array first
›B) Use a hash set to track seen values in O(1)
›C) Use binary search
›D) Use a two-pointer approach

Answer: B) Use a hash set to track seen values in O(1). Repeated scanning for a value is the classic bottleneck that hashing solves. A hash set lookup is O(1) average, reducing the total from O(n²) to O(n).

Question 3: An interviewer asks for the time complexity of your solution. You have one outer loop over n and a hash map lookup inside. What is the complexity?

›A) O(n²) because there is a loop and an inner operation
›B) O(n log n) because hash maps use trees internally
›C) O(n) because hash map lookup is O(1) on average
›D) O(1) because hash maps are fast

Answer: C) O(n) because hash map lookup is O(1) on average. The outer loop runs n times. Each iteration does O(1) hash map work. O(n) × O(1) = O(n). The common mistake is assuming any inner operation makes the loop O(n²) — it only does if the inner operation itself is O(n).

Question 4: You are stuck on a problem after five minutes. What is the best next step?

›A) Immediately look at the solution
›B) Try to code something and see if it works
›C) Re-read the problem and try a simpler example with n=3 or n=4
›D) Move on to a different problem

Answer: C) Re-read the problem and try a simpler example. Most blocks come from incomplete problem understanding or missing a pattern at small scale. Working through n=3 manually almost always reveals the logic. Looking at the solution immediately skips the productive struggle that builds problem-solving skill.

Summary

Approaching problems systematically is a skill that can be learned and improved with deliberate practice. The developers who interview well are not the ones who have seen every problem — they are the ones who have a reliable process for every problem they have not seen.

The six steps carried forward:

›Understand the problem completely before writing anything — input, output, constraints, edge cases
›Work through small examples by hand to confirm understanding and generate test cases
›State the brute force solution clearly — correct and explainable beats clever and confusing
›Identify the bottleneck — what is doing repeated or unnecessary work?
›Match the bottleneck to a pattern — hashing, two pointers, sliding window, DP, graph traversal
›Code cleanly, test with your examples, state complexity at the end

The pattern recognition table, the communication framework, and the bottleneck analysis method are tools you can apply immediately to every problem you solve from this point forward. Use them consciously on every problem — even easy ones — until they become instinct.

In the next section, you will start applying these skills to real data structures, beginning with How to Identify Patterns in the Problem Solving Strategy section.

←

PreviousAnalyze Code Complexity (Practice)

NextHow to Identify Patterns

→