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

Choosing the Right Data Structure

Why the Right Data Structure Matters

Writing correct code is table stakes. Writing code that scales is the actual engineering skill.

Two solutions to the same problem can be completely correct and produce identical output. One runs in milliseconds. The other times out. The difference is almost always the data structure.

A hash map where you used an array. A heap where you used sorting. A deque where you used an array with shifting. These are not minor implementation details — they are the decisions that determine whether your solution is usable at scale.

The right data structure does not just speed up code. It often makes the code simpler. When you choose the structure that fits the problem's natural shape, the algorithm follows cleanly. When you force the wrong structure, you fight the problem the entire way through.

This topic gives you a repeatable decision process: read the problem, identify what operations matter, match those operations to the structure that makes them fast.

The Decision Framework

Before choosing a data structure, answer four questions about the problem:

What operations are needed? Access by index, search by value, insert at a position, delete by value, track order, find minimum or maximum — the answer determines everything.

How often does each operation happen? An operation that happens once can be O(n). An operation that happens n times must be O(1) or O(log n) or the total becomes O(n²).

Does order matter? Insertion order, sorted order, priority order — each leads to a different structure.

What are the constraints? Input size, duplicate values, negative numbers — these rule out certain structures and confirm others.

Once you know the answers, the structure choice is usually obvious. The table below is your starting reference.

The Quick Reference Table

Need	Best Structure	Why
Access by index	Array	O(1) direct address computation
Search by value (unsorted)	Hash Map or Hash Set	O(1) average lookup
Search by value (sorted)	Sorted Array + Binary Search	O(log n) search
Insert and delete at both ends	Deque	O(1) at both ends
Insert and delete anywhere	Linked List	O(1) with pointer, O(n) to find
Last-in first-out	Stack	O(1) push and pop
First-in first-out	Queue	O(1) enqueue and dequeue
Always access minimum	Min-Heap	O(1) peek min, O(log n) insert/delete
Always access maximum	Max-Heap	O(1) peek max, O(log n) insert/delete
Sorted insertion and lookup	BST or Sorted Set	O(log n) all operations
Count frequencies	Hash Map	O(1) per update and lookup
Track unique elements	Hash Set	O(1) per insert and check
Hierarchical data	Tree	Natural recursive structure
Connections and paths	Graph	Models arbitrary relationships
Prefix-based search	Trie	O(length) per word operation

Array: When Position Is Everything

Use an array when you know the index of what you want. Arrays give O(1) access by index — nothing else does.

Arrays are also the right choice when you need to iterate over all elements in order, when the data has a natural sequence, or when you need cache-friendly traversal (arrays store elements in contiguous memory, which is faster to traverse than linked structures).

Arrays become the wrong choice when you frequently insert or delete from the middle, or when you need to search by value rather than by position.

Java

Try it out

public class ArrayUsage {

    // Array is right here: access by index is the core operation
    // Finding the second largest element — O(n) single pass
    public static int secondLargest(int[] arr) {
        int first = Integer.MIN_VALUE;
        int second = Integer.MIN_VALUE;

        for (int num : arr) {
            if (num > first) {
                second = first;   // Previous first drops to second
                first = num;
            } else if (num > second && num != first) {
                second = num;
            }
        }

        return second;
    }

    public static void main(String[] args) {
        int[] arr = {3, 1, 7, 5, 2, 9, 4};

        System.out.println("Array:          " + java.util.Arrays.toString(arr));
        System.out.println("Second largest: " + secondLargest(arr));

        // Index access — O(1)
        System.out.println("Element at index 3: " + arr[3]);
    }
}

Output:
Array:          [3, 1, 7, 5, 2, 9, 4]
Second largest: 7
Element at index 3: 5

Hash Map: When You Need Fast Lookup by Value

Use a hash map when you need to find, count, or group elements by a key — not by position. Hash maps give O(1) average for insert, lookup, and delete regardless of size.

Any time your brute force has an inner loop searching for a value, a hash map eliminates it. Any time you need to count frequencies, a hash map is the natural fit.

Java

Try it out

import java.util.HashMap;
import java.util.Map;

public class HashMapUsage {

    // Hash map is right here: need to count frequencies and find by value
    // Find the first character that appears exactly once
    public static char firstUniqueChar(String s) {
        Map<Character, Integer> freq = new HashMap<>();

        // Count frequency of each character — O(n)
        for (char c : s.toCharArray()) {
            freq.put(c, freq.getOrDefault(c, 0) + 1);
        }

        // Find first character with frequency 1 — O(n)
        for (char c : s.toCharArray()) {
            if (freq.get(c) == 1) return c;
        }

        return '\0'; // No unique character found
    }

    public static void main(String[] args) {
        String s1 = "leetcode";
        String s2 = "aabbc";

        System.out.println("First unique in '" + s1 + "': " + firstUniqueChar(s1));
        System.out.println("First unique in '" + s2 + "': " + firstUniqueChar(s2));
    }
}

Output:
First unique in 'leetcode': l
First unique in 'aabbc': c

Why Not an Array Here

A brute force approach would scan the string for every character to count occurrences — O(n²). A hash map reduces frequency counting and lookup both to O(1) per character, giving O(n) total. The lookup is by character value, not by index — that is the signal to use a hash map.

Stack: When Last In Must Come Out First

Use a stack when the most recently added element is always the next one needed. Stacks model any problem with nested structure: brackets that must close in reverse order of opening, function call chains, undo history, DFS traversal.

The core insight: when you encounter an element that must be "matched" against the most recent unmatched element, that is a stack.

Java

Try it out

import java.util.Stack;

public class StackUsage {

    // Stack is right here: closing bracket must match the most recent opening bracket
    // Valid parentheses — check if brackets are correctly nested and closed
    public static boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();

        for (char c : s.toCharArray()) {
            // Push opening brackets onto the stack
            if (c == '(' || c == '[' || c == '{') {
                stack.push(c);
            } else {
                // Closing bracket — must match the most recent opening bracket
                if (stack.isEmpty()) return false;

                char top = stack.pop();

                if (c == ')' && top != '(') return false;
                if (c == ']' && top != '[') return false;
                if (c == '}' && top != '{') return false;
            }
        }

        return stack.isEmpty(); // All brackets were matched
    }

    public static void main(String[] args) {
        System.out.println("'()[]{}' valid: " + isValid("()[]{}"));
        System.out.println("'([)]'  valid: " + isValid("([)]"));
        System.out.println("'{[]}'  valid: " + isValid("{[]}"));
    }
}

Output:
'()[]{}' valid: true
'([)]'  valid: false
'{[]}'  valid: true

Dry Run: Stack on "{[]}"

Input: { [ ] }

c='{': opening → push '{' → stack=[{]
c='[': opening → push '[' → stack=[{, []
c=']': closing → top='[', matches ']' → pop → stack=[{]
c='}': closing → top='{', matches '}' → pop → stack=[]

stack is empty → return true ✓

Queue: When First In Must Come Out First

Use a queue when elements must be processed in the order they arrived. Queues model any level-by-level or sequential processing: BFS traversal, task scheduling, message delivery, sliding window with order tracking.

The core signal: if the order of processing must match the order of arrival, use a queue.

Java

Try it out

import java.util.LinkedList;
import java.util.Queue;

public class QueueUsage {

    // Queue is right here: BFS explores nodes level by level
    // Find shortest path length in an unweighted graph
    public static int shortestPath(int[][] graph, int src, int dst, int n) {
        boolean[] visited = new boolean[n];
        Queue<Integer> queue = new LinkedList<>();

        queue.offer(src);
        visited[src] = true;
        int steps = 0;

        while (!queue.isEmpty()) {
            int size = queue.size(); // Process one level at a time

            for (int i = 0; i < size; i++) {
                int node = queue.poll();

                if (node == dst) return steps;

                for (int neighbor = 0; neighbor < n; neighbor++) {
                    if (graph[node][neighbor] == 1 && !visited[neighbor]) {
                        visited[neighbor] = true;
                        queue.offer(neighbor);
                    }
                }
            }

            steps++;
        }

        return -1; // No path found
    }

    public static void main(String[] args) {
        // Graph: 0-1, 0-2, 1-3, 2-3, 3-4
        int[][] graph = {
            {0,1,1,0,0},
            {1,0,0,1,0},
            {1,0,0,1,0},
            {0,1,1,0,1},
            {0,0,0,1,0}
        };

        System.out.println("Shortest path 0 to 4: " + shortestPath(graph, 0, 4, 5) + " steps");
        System.out.println("Shortest path 0 to 1: " + shortestPath(graph, 0, 1, 5) + " steps");
    }
}

Output:
Shortest path 0 to 4: 2 steps
Shortest path 0 to 1: 1 steps

Heap: When You Always Need the Minimum or Maximum

Use a heap (priority queue) when you repeatedly need the smallest or largest element from a dynamic collection. Heap gives O(1) access to the extreme element and O(log n) insert and delete.

The key signal: if you are sorting an entire collection just to repeatedly access one end of it, a heap eliminates the full sort.

Java

Try it out

import java.util.PriorityQueue;

public class HeapUsage {

    // Heap is right here: repeatedly need the k-th largest as elements arrive
    // Find the K largest elements from a stream — O(n log k)
    public static int[] kLargest(int[] stream, int k) {
        // Min-heap of size k — smallest of the k largest sits at top
        PriorityQueue<int[]> minHeap = new PriorityQueue<>(
            (a, b) -> a[0] - b[0]
        );

        for (int num : stream) {
            minHeap.offer(new int[]{num});

            // Maintain only k elements — evict smallest if over capacity
            if (minHeap.size() > k) {
                minHeap.poll();
            }
        }

        int[] result = new int[k];
        for (int i = k - 1; i >= 0; i--) {
            result[i] = minHeap.poll()[0];
        }

        return result;
    }

    public static void main(String[] args) {
        int[] stream = {3, 1, 5, 12, 2, 11, 7, 8};
        int k = 3;
        int[] result = kLargest(stream, k);

        System.out.print("Stream: ");
        for (int x : stream) System.out.print(x + " ");
        System.out.println();

        System.out.print("Top " + k + " largest: ");
        for (int x : result) System.out.print(x + " ");
        System.out.println();
    }
}

Output:
Stream: 3 1 5 12 2 11 7 8
Top 3 largest: 12 11 8

Why Not Sort Here

Sorting the entire array costs O(n log n). A min-heap of size k costs O(n log k). When k is small (find the top 10 from ten million elements), the heap approach is dramatically more efficient. More importantly, heaps handle streaming data — you can process elements one at a time as they arrive, which sorting cannot do without reprocessing everything.

Hash Set: When You Need Uniqueness or Membership Tests

Use a hash set when you need to track which elements have been seen, detect duplicates, or check membership — and you do not need to store any value associated with each element.

A hash set gives O(1) average insert, lookup, and delete. It is the right choice any time the question is "have I seen this before?"

Java

Try it out

import java.util.HashSet;
import java.util.Set;

public class HashSetUsage {

    // Hash set is right here: need to detect if a value was seen before
    // Find the longest consecutive sequence — O(n)
    public static int longestConsecutive(int[] nums) {
        Set<Integer> numSet = new HashSet<>();

        for (int num : nums) numSet.add(num);

        int longest = 0;

        for (int num : numSet) {
            // Only start counting from the beginning of a sequence
            if (!numSet.contains(num - 1)) {
                int current = num;
                int length = 1;

                // Extend the sequence as long as next element exists
                while (numSet.contains(current + 1)) {
                    current++;
                    length++;
                }

                longest = Math.max(longest, length);
            }
        }

        return longest;
    }

    public static void main(String[] args) {
        int[] nums = {100, 4, 200, 1, 3, 2};
        System.out.println("Array:                   " + java.util.Arrays.toString(nums));
        System.out.println("Longest consecutive seq: " + longestConsecutive(nums));

        int[] nums2 = {0, 3, 7, 2, 5, 8, 4, 6, 0, 1};
        System.out.println("Longest consecutive seq: " + longestConsecutive(nums2));
    }
}

Output:
Array:                   [100, 4, 200, 1, 3, 2]
Longest consecutive seq: 4
Longest consecutive seq: 9

Dry Run: Longest Consecutive on [100, 4, 200, 1, 3, 2]

numSet = {100, 4, 200, 1, 3, 2}

num=100: 99 not in set → start of sequence
  current=100, 101 not in set → length=1
  longest=1

num=4: 3 IS in set → skip (not start of sequence)

num=200: 199 not in set → start of sequence
  current=200, 201 not in set → length=1
  longest=1

num=1: 0 not in set → start of sequence
  current=1, 2 in set → current=2, length=2
  current=2, 3 in set → current=3, length=3
  current=3, 4 in set → current=4, length=4
  current=4, 5 not in set → stop
  longest=4

Result: 4  (sequence 1,2,3,4)
Time: O(n) — each element is visited at most twice across all sequences

How the Same Problem Changes With the Right Structure

The best illustration of data structure choice is showing the same problem solved with the wrong structure and then the right one.

Problem: Given a stream of integers, after each new integer, find the median of all integers seen so far.

With an array, each query requires re-sorting — O(n log n) per insertion. With two heaps (a max-heap for the lower half and a min-heap for the upper half), insertion is O(log n) and median retrieval is O(1).

Java

Try it out

import java.util.Collections;
import java.util.PriorityQueue;

public class MedianFinder {

    // Two heaps is right here: need median after each insertion
    // Lower half in max-heap, upper half in min-heap
    // Median is at the tops of the heaps
    private PriorityQueue<Integer> lowerHalf; // Max-heap — largest of lower half at top
    private PriorityQueue<Integer> upperHalf; // Min-heap — smallest of upper half at top

    public MedianFinder() {
        lowerHalf = new PriorityQueue<>(Collections.reverseOrder());
        upperHalf = new PriorityQueue<>();
    }

    public void addNum(int num) {
        lowerHalf.offer(num); // Always add to lower half first

        // Balance: move largest of lower to upper if needed
        if (!upperHalf.isEmpty() && lowerHalf.peek() > upperHalf.peek()) {
            upperHalf.offer(lowerHalf.poll());
        }

        // Balance sizes: lower can have at most one more element than upper
        if (lowerHalf.size() > upperHalf.size() + 1) {
            upperHalf.offer(lowerHalf.poll());
        } else if (upperHalf.size() > lowerHalf.size()) {
            lowerHalf.offer(upperHalf.poll());
        }
    }

    public double findMedian() {
        if (lowerHalf.size() > upperHalf.size()) {
            return lowerHalf.peek(); // Odd count — lower has the middle element
        }
        return (lowerHalf.peek() + upperHalf.peek()) / 2.0; // Even — average of two middles
    }

    public static void main(String[] args) {
        MedianFinder mf = new MedianFinder();
        int[] stream = {5, 15, 1, 3, 8};

        for (int num : stream) {
            mf.addNum(num);
            System.out.printf("Added %2d → median = %.1f%n", num, mf.findMedian());
        }
    }
}

Output:
Added  5 → median = 5.0
Added 15 → median = 10.0
Added  1 → median = 5.0
Added  3 → median = 4.0
Added  8 → median = 5.0

Why Two Heaps

The median is always either the middle element (odd count) or the average of two middle elements (even count). Two heaps maintain this middle boundary dynamically:

›The max-heap holds the lower half — its top is the largest of the smaller elements.
›The min-heap holds the upper half — its top is the smallest of the larger elements.
›Keeping them balanced by at most one element ensures the median is always at one or both tops in O(1).

Single array: O(n log n) per insertion to re-sort. Two heaps: O(log n) per insertion, O(1) median retrieval.

The Data Structure Decision Guide

When you face a new problem, run through this checklist:

Do I need to access elements by position?
  Yes → Array

Do I need to find/check elements by value, not position?
  Existence only (seen or not) → Hash Set
  Value associated with key    → Hash Map

Do I need LIFO — process most recent first?
  Yes → Stack

Do I need FIFO — process oldest first?
  Yes → Queue

Do I need to repeatedly find the minimum or maximum?
  Min repeatedly → Min-Heap
  Max repeatedly → Max-Heap
  Both min and max (e.g. median) → Two Heaps

Do I need sorted order and fast insert/delete/search?
  Yes → Balanced BST (TreeMap/TreeSet in Java, SortedList in Python)

Do I need prefix-based search or autocomplete?
  Yes → Trie

Do I need to model hierarchical relationships?
  Yes → Tree

Do I need to model arbitrary connections?
  Yes → Graph

No clear answer? → Start with Array or Hash Map.
  Array: if you iterate in order
  Hash Map: if you look up by value

Common Mistakes Beginners Make

Defaulting to arrays for everything. Arrays are the most familiar structure, so beginners reach for them first regardless of fit. If you are searching an array by value more than once, you should be using a hash map or hash set.

Using a list when a set is needed. Checking if x in list is O(n). Checking if x in set is O(1). Any time you need existence checks on a growing collection, convert to a set.

Sorting when a heap would do. Sorting an array to find the minimum or maximum repeatedly costs O(n log n) every time the collection changes. A heap maintains the extreme element dynamically in O(log n) per change.

Using a queue when a deque is needed. A standard queue only removes from the front. If you need to efficiently add or remove from both ends (sliding window maximum, palindrome checking), use a deque.

Choosing by familiarity instead of by operations. The right question is not "what structure do I know how to use?" but "what operations does this problem actually need, and what structure makes those operations fast?" Let the operations decide.

Interview Questions

Q: How do you decide between a hash map and an array for frequency counting?

If the values are bounded integers in a small range (like characters 'a' to 'z', which is only 26 values), an array of size 26 indexed by value is simpler and faster than a hash map. If the values are arbitrary integers or strings with no known bound, a hash map is required. Arrays win on simplicity and cache performance when the value range is small and known.

Q: When would you use a min-heap instead of sorting?

When the collection changes over time or when you only need the minimum repeatedly rather than all elements in sorted order. Sorting is a one-time O(n log n) operation on a static collection. A heap is O(log n) per insert or delete and O(1) to access the minimum — it stays efficient as elements are added and removed dynamically.

Q: What is the difference between a stack and a queue, and when do you use each?

A stack is LIFO — the most recently added element is removed first. Use it for nested structures, undo operations, DFS traversal, and expression evaluation. A queue is FIFO — the oldest element is removed first. Use it for BFS traversal, level-by-level processing, task scheduling, and any situation where order of arrival must be preserved.

Q: Why would you use a hash set instead of a sorted array for membership testing?

A sorted array supports O(log n) binary search. A hash set supports O(1) average membership testing. For large collections with many membership queries and no need for sorted order, the hash set is faster. The sorted array is better when you also need predecessor/successor queries or range queries — operations a hash set cannot support.

FAQs

Can I always just use a hash map and be safe?

Hash maps handle many problems well, but they have costs: O(n) space, no ordering guarantees, and worst-case O(n) operations due to hash collisions (rare in practice). For small fixed-size ranges, arrays are faster. For problems needing sorted order or range queries, a sorted structure is necessary. Use hash maps when you need fast key-value access on arbitrary keys — not as a universal default.

What is the difference between a TreeMap and a HashMap in Java?

A HashMap stores key-value pairs with O(1) average operations but no ordering guarantee. A TreeMap maintains keys in sorted order with O(log n) operations — it is backed by a Red-Black Tree. Use HashMap when you need fast access. Use TreeMap when you need the keys in sorted order, need to find the smallest or largest key, or need range queries like "all keys between 5 and 10."

When should I use a linked list over an array?

Linked lists give O(1) insert and delete at a known position (with a pointer to that position) and unlimited dynamic growth. Arrays give O(1) index access but O(n) insert and delete in the middle. In practice, arrays are preferable for most problems because index access is far more common than arbitrary insertion, and arrays have better cache performance. Linked lists appear in specific problems: LRU cache, reversing sequences without extra memory, and problems where you have a pointer to the node you need to modify.

Is there a data structure that handles everything well?

No — every structure optimizes for some operations at the cost of others. This is the fundamental reason choosing the right structure matters. A hash map is O(1) for lookup but cannot answer "what is the minimum element?" A sorted array supports binary search but is O(n) for insertion. A heap answers "what is the minimum?" in O(1) but cannot look up arbitrary elements. Understanding these tradeoffs is the entire skill.

Quick Quiz

Question 1: You need to check whether each word in a document has been seen before as you read it. Which structure is most appropriate?

›A) Array
›B) Stack
›C) Hash Set
›D) Min-Heap

Answer: C) Hash Set. You need membership testing (have I seen this word?) with O(1) lookup as new words arrive. A hash set provides O(1) average insert and membership test. An array would require O(n) scanning per word.

Question 2: You are implementing a browser's back button. Pressing back should return to the most recently visited page. Which structure fits?

›A) Queue
›B) Stack
›C) Hash Map
›D) Array

Answer: B) Stack. The back button needs LIFO behavior — the most recently visited page is the first one returned. Each visited page is pushed onto the stack. Pressing back pops the most recent one.

Question 3: You receive a stream of integers one at a time and must output the current median after each new integer. Which structure gives the best performance?

›A) Sorted Array — re-sort after each insertion
›B) Single Max-Heap
›C) Two Heaps — max-heap for lower half, min-heap for upper half
›D) Hash Map with counts

Answer: C) Two Heaps. Two balanced heaps give O(log n) insertion and O(1) median retrieval. Re-sorting an array after each insertion is O(n log n) per insertion. A single heap cannot efficiently find the median. A hash map with counts can work but requires O(n) median retrieval.

Question 4: You need to find whether any two numbers in an unsorted array sum to a target. Which structure gives O(n) overall time?

›A) Sort the array, then use binary search — O(n log n)
›B) Use two nested loops — O(n²)
›C) Use a hash set to store seen values and check complement in O(1)
›D) Use a min-heap and pop elements one by one

Answer: C) Use a hash set. For each element x, check if (target - x) is in the set in O(1), then add x to the set. One pass gives O(n) total. Sorting plus binary search is O(n log n). Nested loops are O(n²). The heap approach has no natural fit here.

Summary

Choosing the right data structure is not about memorizing a table. It is about understanding what operations your problem needs and which structure makes those operations fast.

The decision process to carry forward:

›Need access by position → Array
›Need lookup, counting, or grouping by value → Hash Map
›Need membership or duplicate detection → Hash Set
›Need last-in-first-out → Stack
›Need first-in-first-out → Queue
›Need repeated minimum or maximum access → Heap
›Need sorted order with fast insert and search → Balanced BST
›Need prefix-based string search → Trie

The data structure choice precedes the algorithm. Before thinking about how to solve a problem, think about what shape the data takes and what the problem needs to do with it. When the structure fits the problem's natural shape, the algorithm is almost always straightforward.

In the next topic, you will explore Dry Run and Debug Approach — learning how to trace through code systematically to find bugs and validate correctness before submitting.

←

PreviousBrute Force to Optimal

NextDry Run & Debug Approach

→