Core Data Structures

July 20, 2025

Table of Contents

• Core Data Structures
  • Array
  • String
  • Linked List
  • Hash Table (Hash Map / Dictionary)
  • Set (Hash Set)
  • Stack
  • Queue
  • Matrix
  • Tree

Core Data Structures

Array

Definition: A data structure consisting of a collection of elements, each identified by at least one array index or key. Elements are stored in contiguous memory locations.

• Access: O(1)
• Search: O(N)
• Insertion (at end): O(1) (amortized for dynamic arrays)
• Insertion (in middle): O(N)
• Deletion (from end): O(1)
• Deletion (from middle): O(N)

Space Complexity: O(N) for N elements.

• Fast Lookups: If you know the index, getting an element is O(1). This is the primary reason to use an array.
• Cache Friendliness: Elements are in contiguous memory blocks. When you access one element, the CPU is likely to cache nearby elements (locality of reference), making sequential iteration extremely fast.

• Costly Inserts/Deletes: Adding or removing elements from the middle is O(N) because it requires shifting all subsequent elements. This is a critical trade-off compared to a Linked List.
• Fixed Size (for static arrays): In languages like Java or C++, you must declare the size of a static array upfront. If you underestimate, you have to create a new, larger array and copy everything over.

Python Example: This example demonstrates basic list creation, access, and modification.

# Python's list serves as a dynamic array
my_list = [10, 20, 30, 40, 50]

# Access element by index (O(1))
print(f"Element at index 2: {my_list[2]}")
# Expected Output: Element at index 2: 30

# Append an element (O(1) amortized)
my_list.append(60)
print(f"List after appending 60: {my_list}")
# Expected Output: List after appending 60: [10, 20, 30, 40, 50, 60]

# Remove an element (O(N))
my_list.remove(30)
print(f"List after removing 30: {my_list}")
# Expected Output: List after removing 30: [10, 20, 40, 50, 60]

Java Example: This example demonstrates basic array creation (using ArrayList), access, and modification.

import java.util.ArrayList;
import java.util.Arrays;

public class ArrayExample {
    public static void main(String[] args) {
        // Java's ArrayList serves as a dynamic array.
        // We initialize it with values from a static array.
        ArrayList<Integer> myList = new ArrayList<>(Arrays.asList(10, 20, 30, 40, 50));

        // Access element by index (O(1))
        System.out.println("Element at index 2: " + myList.get(2));
        // Expected Output: Element at index 2: 30

        // Append an element (O(1) amortized)
        myList.add(60);
        System.out.println("List after appending 60: " + myList);
        // Expected Output: List after appending 60: [10, 20, 30, 40, 50, 60]

        // Remove an element by value (O(N))
        // We use Integer.valueOf() to remove the object 30, not the element at index 30.
        myList.remove(Integer.valueOf(30));
        System.out.println("List after removing 30: " + myList);
        // Expected Output: List after removing 30: [10, 20, 40, 50, 60]
    }
}

• Two Pointers: Using two indices that move through the array, typically towards each other or in the same direction, to solve problems involving sorted arrays, palindromes, or pairs of elements.
  • Two Sum II - Input array is sorted (#167)
  • Container With Most Water (#11)
  • Valid Palindrome (#125)
  • 3Sum (#15)
• Sliding Window: Using two pointers to define a "window" of elements that is moved through the array. This is used to find the longest/shortest subarray or substring that satisfies a certain condition.
  • Longest Substring Without Repeating Characters (#3)
  • Minimum Size Subarray Sum (#209)
  • Permutation in String (#567)
  • Best Time to Buy and Sell Stock (#121)
• Prefix Sum / Suffix Sum: Pre-calculating a new array where prefix_sum[i] stores the sum of all elements from 0 to i. This allows for finding the sum of any subarray [i, j] in O(1) time by computing prefix_sum[j] - prefix_sum[i-1].
  • Range Sum Query - Immutable (#303)
  • Subarray Sum Equals K (#560)
  • Product of Array Except Self (#238)
• Using the Array as a Hash Map: When the input array contains numbers within a specific, limited range (e.g., 1 to N), the array indices themselves can be used for tracking information. By manipulating element signs (e.g., making arr[i] negative) or using swaps, you can store boolean "visited" information or place elements in their "correct" positions without using extra space. This is common in problems asking for duplicates or missing numbers.
  • Find All Numbers Disappeared in an Array (#448)
  • Find the Duplicate Number (#287)
  • First Missing Positive (#41)

String

Definition: A data structure representing a sequence of characters. In most modern languages (like Java and Python), strings are immutable, meaning their contents cannot be changed after creation. Conceptually, they are often implemented as an array of characters.

• Access Character (at index i): O(1)
• Search (for substring): O(N x M) in the naive case, where N and M are the lengths of the string and substring. More advanced algorithms can achieve O(N+M).
• Concatenation/Append: O(N+M) because a completely new string of the combined length must be created in memory.
• Slicing (creating a substring): O(K) where K is the length of the slice, as a new string must be created.

Space Complexity: O(N) for a string of length N.

• Readability: Strings are the natural way to represent and work with human-readable text.
• Rich Libraries: Most languages provide a vast, highly-optimized set of built-in functions for common string manipulations (searching, splitting, formatting, etc.).

• Immutability: Since strings cannot be changed, any modification (like appending a character or changing a case) creates an entirely new string. Performing many modifications in a loop can be very inefficient, leading to high memory usage and slow performance due to repeated memory allocation and copying.

Python Example: This example demonstrates immutability and the correct way to build strings.

# Strings are immutable. Concatenation creates a new string.
str1 = "hello"
print(f"Original ID: {id(str1)}")
# Expected Output: Original ID: <some memory address, e.g., 4355581360>

str1 = str1 + " world"
print(f"New ID: {id(str1)}")
# Expected Output: New ID: <a different memory address, e.g., 4355581936>

# Efficiently building a string using join()
# This creates a list first and then allocates the final string once.
words = ["this", "is", "good"]
result_good = "".join(words)
print(f"Efficient result: {result_good}")
# Expected Output: Efficient result: thisisgood

Java Example: This example contrasts inefficient String concatenation with the efficient StringBuilder.

public class StringExample {
    public static void main(String[] args) {
        // Inefficient concatenation in a loop
        // Creates a new String object each time, which is slow.
        String[] words = {"this", "is", "a", "test"};
        String result = "";
        for (String word : words) {
            result += word;
        }
        System.out.println("Inefficient result: " + result);
        // Expected Output: Inefficient result: thisisatest

        // Efficiently building a string with StringBuilder
        // StringBuilder is a mutable sequence of characters.
        StringBuilder sb = new StringBuilder();
        for (String word : words) {
            sb.append(word); // Appends to the internal buffer, no new object created.
        }
        String efficientResult = sb.toString(); // Creates the final string once.
        System.out.println("Efficient result: " + efficientResult);
        // Expected Output: Efficient result: thisisatest
    }
}

• Two Pointers: Use two pointers moving through the string to check for properties like palindromes or to reverse sections of the string.

  • Valid Palindrome (#125)
  • Reverse String (#344)
  • Reverse Vowels of a String (#345)
  • Valid Palindrome II (#680)

• Sliding Window: Define a "window" (substring) using two pointers and slide it across the string to find the longest/shortest substring that satisfies a certain property, often related to character counts.

  • Longest Substring Without Repeating Characters (#3)
  • Permutation in String (#567)
  • Find All Anagrams in a String (#438)
  • Longest Repeating Character Replacement (#424)

• Frequency Count (Hash Map / Array): Use a hash map or a simple fixed-size array (int[26]) to count character frequencies. This is essential for solving problems related to anagrams, character sets, and structural comparisons.

  • Valid Anagram (#242)
  • Ransom Note (#383)
  • Group Anagrams (#49)
  • Isomorphic Strings (#205)

• Backtracking / Recursion: Use recursion to solve problems that involve generating all possible string combinations or permutations, or exploring paths in a grid of characters.

  • Generate Parentheses (#22)
  • Letter Combinations of a Phone Number (#17)
  • Word Search (#79)

Linked List

Definition: A linear collection of data elements, called nodes, where the order is not determined by physical memory placement. Instead, each node contains data and a pointer (or reference) to the next node in the sequence, forming a chain.

• Access (by index): O(N). You must traverse the list from the head to find the Nth element.
• Search (by value): O(N). Requires traversing the list to find the element.
• Insertion/Deletion (at beginning): O(1). Only requires updating the head pointer.
• Insertion/Deletion (at end): O(N) for a singly linked list without a tail pointer. This becomes O(1) if a tail pointer is maintained.
• Insertion/Deletion (in middle): O(1) if you already have a pointer to the node before the insertion/deletion point. Otherwise, it's O(N) to find that node first.

Space Complexity: O(N) for N nodes. Each node requires extra space for its pointer(s).

• Efficient Insertions/Deletions: Unlike an array, inserting or deleting a node in the middle is an O(1) operation if you already have a reference to the preceding node, as no elements need to be shifted.
• Dynamic Size: Linked lists can grow and shrink dynamically without the costly resizing and copying operations required by a dynamic array.

• Slow Access and Search: Accessing an element by index requires traversing the list from the beginning, resulting in O(N) performance. This is the primary trade-off compared to an array's O(1) indexed access.
• Poor Cache Locality: Nodes are typically scattered in memory, unlike the contiguous blocks of an array. This leads to more cache misses and can result in slower iteration performance in practice.

Python Example: This example defines a ListNode, creates a list, and inserts a new node.

class ListNode:
    def __init__(self, value=0, next=None):
        self.value = value
        self.next = next

# Create a list: 10 -> 30
head = ListNode(10, ListNode(30))

# Insert a new node (20) between 10 and 30
new_node = ListNode(20)
new_node.next = head.next
head.next = new_node

# Traverse and print the list
current = head
while current:
    print(current.value, end=" -> ")
    current = current.next
print("None")
# Expected Output: 10 -> 20 -> 30 -> None

Java Example: This example uses a custom ListNode class to create a linked list. It is worth noting that java.util has a LinkedList class that is a doubly linked list.

public class LinkedListExample {

    // A static nested class for the node structure
    static class ListNode {
        int value;
        ListNode next;

        // Constructor for a node with a specified next node
        ListNode(int value, ListNode next) {
            this.value = value;
            this.next = next;
        }
        
        // Constructor for a node that is the end of a list
        ListNode(int value) {
            this(value, null);
        }
    }

    public static void main(String[] args) {
        // Create a linked list manually: 1 -> 2 -> 3
        ListNode head = new ListNode(1, new ListNode(2, new ListNode(3)));

        // Traverse the linked list and print its contents
        System.out.print("List contents: ");
        ListNode current = head;
        while (current != null) {
            System.out.print(current.value + " -> ");
            current = current.next;
        }
        System.out.println("null");
        // Expected Output: List contents: 1 -> 2 -> 3 -> null
    }
}

• Fast & Slow Pointers: Uses two pointers that move at different speeds. This pattern is fundamental for detecting cycles, finding the middle of a list, or solving related structural problems.
  • Linked List Cycle (#141)
  • Middle of the Linked List (#876)
  • Linked List Cycle II (#142)
• Reversing a List: An essential skill that involves iteratively or recursively reversing the next pointers of the nodes. It's a building block for more complex problems.
  • Reverse Linked List (#206)
  • Reverse Linked List II (#92)
  • Palindrome Linked List (#234)
• Dummy Head Node: A sentinel or placeholder node is created at the beginning of the list to simplify logic. This is especially useful for problems where the original head node might be removed or where insertions happen at the very beginning, eliminating edge cases.
  • Remove Nth Node From End of List (#19)
  • Remove Linked List Elements (#203)
  • Add Two Numbers (#2)
• Merging: Combines two or more sorted linked lists into a single sorted list by comparing nodes and re-wiring their next pointers.
  • Merge Two Sorted Lists (#21)
  • Merge k Sorted Lists (#23)

Hash Table (Hash Map / Dictionary)

Definition: A data structure that maps unique keys to corresponding values, creating associative pairs (e.g., a word to its definition). It uses a hash function to compute an index into an underlying array, allowing for the direct storage and retrieval of values based on their keys. A Set can be thought of as a specialized version of this structure where only the keys matter.

• Insert (key-value pair): O(1) on average, O(N) in the worst case.
• Delete (by key): O(1) on average, O(N) in the worst case.
• Search (by key): O(1) on average, O(N) in the worst case.

The worst-case O(N) occurs when all keys generate the same hash index (a hash collision), forcing a linear search within a single "bucket". Good hash functions make this extremely rare.

Space Complexity: O(N) to store N key-value pairs.

• Fast Data Retrieval: The primary strength is O(1) average time to access a value if you know its key. This is ideal for any "lookup" or "dictionary" style problem.
• Associative Pairing: It naturally associates two pieces of data, which is essential for tasks like frequency counting, caching, or mapping one object to another.
• Flexible Keys: Keys can be complex types like strings or objects, not just integers like in an array.

• Worst-Case Performance: While uncommon, the O(N) worst-case from hash collisions can be a factor in highly time-sensitive systems.
• Unordered: Most standard hash maps do not maintain insertion order. Iterating through key-value pairs may yield an unpredictable sequence.
• Space Overhead: The underlying array is often kept only partially full (a low "load factor") to minimize collisions, which can lead to some unused memory.

Python Example: This example uses a dict (hash map) to count character frequencies.

# A dictionary (dict) is Python's implementation of a hash map
frequency_map = {}
text = "hello world"

for char in text:
    # Get the current count (or 0) and add 1
    # O(1) average time for access and insertion
    frequency_map[char] = frequency_map.get(char, 0) + 1

print(f"Character frequencies: {frequency_map}")
# Expected Output: Character frequencies: {'h': 1, 'e': 1, 'l': 3, 'o': 2, ' ': 1, 'w': 1, 'r': 1, 'd': 1}

Java Example: This example uses Java's HashMap for the same frequency counting task.

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

public class HashTableExample {
    public static void main(String[] args) {
        // HashMap for storing key-value pairs
        Map<Character, Integer> frequencyMap = new HashMap<>();
        String text = "hello world";

        for (char c : text.toCharArray()) {
            // O(1) average time for get() and put()
            frequencyMap.put(c, frequencyMap.getOrDefault(c, 0) + 1);
        }

        System.out.println("Character frequencies: " + frequencyMap);
        // Expected Output: Character frequencies: {r=1, d=1, e=1, w=1, h=1, l=3, o=2,  =1} (order may vary)
    }
}

• Frequency Counting: Using a hash map to count occurrences of elements. This is essential for problems involving anagrams (rearranging the letters of a word to form another word) or finding the most frequent items.
  • Valid Anagram (#242)
  • Ransom Note (#383)
  • Group Anagrams (#49)
  • Top K Frequent Elements (#347)
• Two Sum Pattern: The classic use case where you iterate through an array and use a hash map to check for the existence of target - current_value in O(1) time.
  • Two Sum (#1)
  • Subarray Sum Equals K (#560)
• Associative Mapping: Using a hash map to associate one piece of data with another, such as mapping a character to another character or an original node to its copy.
  • Isomorphic Strings (#205)
  • Copy List with Random Pointer (#138)
  • LRU Cache (#146)

Set (Hash Set)

Definition: A Set is an abstract data structure that stores a collection of unique elements in no particular order. It is most commonly implemented using a hash table, which allows for highly efficient operations.

• Add (Insert): O(1) on average, O(N) in the worst case.
• Remove (Delete): O(1) on average, O(N) in the worst case.
• Contains (Search): O(1) on average, O(N) in the worst case.
• Set Operations (Union, Intersection): O(N + M) where N and M are the sizes of the two sets.

The worst-case O(N) performance is due to hash collisions, which is rare in practice.

Space Complexity: O(N) to store N unique elements.

• Automatic Uniqueness: The data structure inherently enforces that all its elements are unique. Adding a duplicate element has no effect.
• Extremely Fast Membership Testing: Checking if an element exists in a set is, on average, an O(1) operation, which is significantly faster than searching in an array or list (O(N)).
• Efficient Set Operations: Provides highly optimized, built-in methods for common mathematical set operations like union, intersection, and difference.

• Unordered: Standard hash-based sets do not maintain the insertion order of elements. If you iterate through a set, the order is not guaranteed.
• No Indexed Access: You cannot access elements by a numeric index (e.g., my_set[0]) because there is no defined order. You can only check for the existence of an element.

Python Example: This example uses Python's built-in set.

# Create a set. Duplicates are automatically ignored.
my_set = {1, 2, 3, 3, 4}
print(f"Initial set: {my_set}")
# Expected Output: Initial set: {1, 2, 3, 4}

# Add an element
my_set.add(5)
print(f"Set after adding 5: {my_set}")
# Expected Output: Set after adding 5: {1, 2, 3, 4, 5}

# Check for existence (membership test) - O(1) on average
print(f"Does the set contain 3? {3 in my_set}")
# Expected Output: Does the set contain 3? True

# Perform a set operation (union)
union_set = {4, 5, 6, 7}
union_result = my_set.union(union_set)
print(f"Union: {union_result}")
# Expected Output: Union: {1, 2, 3, 4, 5, 6, 7}

# Perform a set operation (intersection)
intersection_set = {4, 5, 6, 7}
intersection_result = my_set.intersection(intersection_set)
print(f"Intersection: {intersection_result}")
# Expected Output: Intersection: {4, 5}

Java Example: This example uses Java's HashSet.

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

public class SetExample {
    public static void main(String[] args) {
        // Create a HashSet from a list containing duplicates
        Set<Integer> mySet = new HashSet<>(Arrays.asList(1, 2, 3, 3, 4));
        System.out.println("Initial set: " + mySet);
        // Expected Output: Initial set: [1, 2, 3, 4] (order may vary)

        // Add an element. The return value indicates if the set was changed.
        mySet.add(5);
        System.out.println("Set after adding 5: " + mySet);
        // Expected Output: Set after adding 5: [1, 2, 3, 4, 5] (order may vary)

        // Check for existence (membership test) - O(1) on average
        System.out.println("Does the set contain 3? " + mySet.contains(3));
        // Expected Output: Does the set contain 3? true

        // Perform a set operation (union)
        Set<Integer> unionSet = new HashSet<>(Arrays.asList(4, 5, 6, 7));
        Set<Integer> unionResult = new HashSet<>(mySet);
        unionResult.addAll(unionSet); // Modifies the set in place
        System.out.println("Union: " + unionResult);
        // Expected Output: Union: [1, 2, 3, 4, 5, 6, 7] (order may vary)
        
        // Perform a set operation (intersection)
        Set<Integer> intersectionSet = new HashSet<>(Arrays.asList(4, 5, 6, 7));
        // Create a new set for the result to avoid modifying mySet
        Set<Integer> intersectionResult = new HashSet<>(mySet);
        intersectionResult.retainAll(intersectionSet); // Modifies the set in place
        System.out.println("Intersection: " + intersectionResult);
        // Expected Output: Intersection: [4, 5] (order may vary)
    }
}

• Tracking Seen / Visited Elements: The most frequent pattern. Use a set to keep track of items you have already processed to avoid redundant work, such as visited nodes in a graph or numbers in an array.
  • Contains Duplicate (#217)
  • Valid Sudoku (#36)
  • Longest Substring Without Repeating Characters (#3)
• Finding Unique Items: Use a set to easily find all unique items from one or more collections. This is useful for problems involving existence, not frequency.
  • Intersection of Two Arrays (#349)
  • Unique Email Addresses (#929)
  • Find the Difference of Two Arrays (#2215)

Stack

Definition: A Stack is a linear data structure that follows the Last-In, First-Out (LIFO) principle. Elements are added (pushed) and removed (popped) from the same end, called the "top." This is analogous to a stack of plates, where you can only take the top plate off.

• Push (Add to top): O(1)
• Pop (Remove from top): O(1)
• Peek (View top element): O(1)
• Search (Find an element): O(N)

These complexities assume the stack is implemented using a dynamic array or linked list. The primary operations are all constant time.

Space Complexity: O(N) to store N elements.

• Fast Operations: The core operations of push, pop, and peek are extremely fast, with a constant time complexity of O(1).
• Simple Model: Stacks provide a simple and intuitive model for solving problems that involve reversing order or processing nested structures, such as recursion.
• Low Memory Usage: A simple stack implementation has very little memory overhead compared to more complex data structures.

• Restricted Access: You cannot access, insert, or delete elements from the middle of the stack. All operations are restricted to the "top" element, making it unsuitable for problems that require quick access to arbitrary data.

Python Example: This example uses a Python list as a stack.

# A list can be used directly as a stack.
# `append()` is push, `pop()` is pop.
stack = []

# Push operations
stack.append(10)
stack.append(20)
stack.append(30)
print(f"Stack after pushes: {stack}")
# Expected Output: Stack after pushes: [10, 20, 30]

# Peek operation (view the top element without removing)
top_element = stack[-1]
print(f"Peeked element: {top_element}")
# Expected Output: Peeked element: 30

# Pop operation
popped_element = stack.pop()
print(f"Popped element: {popped_element}")
# Expected Output: Popped element: 30
print(f"Stack after pop: {stack}")
# Expected Output: Stack after pop: [10, 20]

Java Example: This example uses ArrayDeque as a stack, which is the recommended modern approach.

import java.util.ArrayDeque;
import java.util.Deque;

public class StackExample {
    public static void main(String[] args) {
        // Use Deque as the interface and ArrayDeque as the implementation.
        // This is preferred over the legacy Stack class due to its better performance and usability.
        Deque<Integer> stack = new ArrayDeque<>();

        // Push operations
        stack.push(10); // Adds to the front of the Deque
        stack.push(20);
        stack.push(30);
        System.out.println("Stack after pushes: " + stack);
        // Expected Output: Stack after pushes: [30, 20, 10]

        // Peek operation
        int topElement = stack.peek();
        System.out.println("Peeked element: " + topElement);
        // Expected Output: Peeked element: 30

        // Pop operation
        int poppedElement = stack.pop();
        System.out.println("Popped element: " + poppedElement);
        // Expected Output: Popped element: 30
        System.out.println("Stack after pop: " + stack);
        // Expected Output: Stack after pop: [20, 10]
    }
}

• Matching Pairs / Validity Checks: The most common use case for a stack is to validate sequences with nested pairs, like parentheses, brackets, or HTML tags. Opening elements are pushed onto the stack, and closing elements must match the item at the top of the stack.

  • Valid Parentheses (#20)

• Monotonic Stack: This is a powerful technique where you maintain a stack whose elements are always in a strictly increasing or decreasing order. It's used to efficiently find the "next greater element" or "previous smaller element" for each item in a sequence.

  • Next Greater Element I (#496)
  • Daily Temperatures (#739)
  • Largest Rectangle in Histogram (#84)

• Simulating Recursion / Backtracking: The function call stack is inherently a stack. You can explicitly use a stack data structure to implement a recursive algorithm iteratively. This is often done to handle very deep recursion that might otherwise cause a stack overflow.

  • Binary Tree Inorder Traversal (#94)
  • Evaluate Reverse Polish Notation (#150)

Queue

Definition: A Queue is a linear data structure that follows the First-In, First-Out (FIFO) principle. Elements are added (enqueued) to one end (the "rear") and removed (dequeued) from the other end (the "front"). This is analogous to a checkout line at a store, where the first person to get in line is the first one to be served.

• Enqueue (Add to rear): O(1)
• Dequeue (Remove from front): O(1)
• Peek (View front element): O(1)
• Search (Find an element): O(N)

These complexities assume an efficient queue implementation like a linked list or a double-ended queue (deque). Using a simple list or array for dequeueing from the front is inefficient (O(N)).

Space Complexity: O(N) to store N elements.

• Fairness and Order: Queues are excellent for managing items that must be processed in the exact order they were received, ensuring fairness.
• Fast Operations: When implemented correctly, the core operations of enqueue, dequeue, and peek are all O(1), making them very fast.
• Separation of Concerns: The model of adding to one end and removing from the other is a simple and effective way to manage data flow between processes.

• Restricted Access: Similar to a stack, a queue does not allow for quick access to elements in the middle. All operations are restricted to the front and rear of the queue.

Python Example: This example shows the efficient (deque) and inefficient (list) ways to implement a queue.

# The efficient way using collections.deque
from collections import deque

# `append()` is enqueue, `popleft()` is dequeue
queue = deque() 

# Enqueue operations
queue.append(10)
queue.append(20)
queue.append(30)
print(f"Efficient Queue: {queue}")
# Expected Output: Efficient Queue: deque([10, 20, 30])

# Peek operation
front_element = queue[0]
print(f"Peeked element: {front_element}")
# Expected Output: Peeked element: 10

# Dequeue operation
dequeued_element = queue.popleft() # This is an O(1) operation
print(f"Dequeued element: {dequeued_element}")
# Expected Output: Dequeued element: 10
print(f"Queue after dequeue: {queue}")
# Expected Output: Queue after dequeue: deque([20, 30])

# ---

# The inefficient way using a list
# Note: This should be avoided in interviews and production code.
list_queue = []
list_queue.append(10)
list_queue.append(20)
# Dequeueing from the front of a list is an O(N) operation
# because all other elements must be shifted.
inefficient_dequeue = list_queue.pop(0)
print(f"\nInefficient dequeue from {['A', 'B']}: {inefficient_dequeue}")
# Expected Output: Inefficient dequeue from ['A', 'B']: 10

Java Example (ArrayDeque): This example uses ArrayDeque, which is a highly efficient implementation of the Queue interface.

import java.util.ArrayDeque;
import java.util.Queue;
public class QueueExample {
    public static void main(String[] args) {
        // Queue is an interface; ArrayDeque is a highly efficient implementation.
        Queue<Integer> queue = new ArrayDeque<>();

        // Enqueue operations (add() or offer())
        queue.add(10);
        queue.add(20);
        queue.add(30);
        System.out.println("Queue after additions: " + queue);
        // Expected Output: Queue after additions: [10, 20, 30]

        // Peek operation (view the front element)
        int frontElement = queue.peek();
        System.out.println("Peeked element: " + frontElement);
        // Expected Output: Peeked element: 10

        // Dequeue operation (poll() or remove())
        // poll() returns null if the queue is empty.
        int dequeuedElement = queue.poll();
        System.out.println("Dequeued element: " + dequeuedElement);
        // Expected Output: Dequeued element: 10
        
        System.out.println("Queue after poll: " + queue);
        // Expected Output: Queue after poll: [20, 30]
    }
}

Java Example (LinkedList): This example uses LinkedList, which implements the Queue interface.

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

public class QueueExample {
    public static void main(String[] args) {
        // Queue is an interface; LinkedList is a common implementation.
        // ArrayDeque is also an excellent choice.
        Queue<Integer> queue = new LinkedList<>();

        // Enqueue operations (add() or offer())
        queue.add(10);
        queue.add(20);
        queue.add(30);
        System.out.println("Queue after additions: " + queue);
        // Expected Output: Queue after additions: [10, 20, 30]

        // Peek operation (view the front element)
        int frontElement = queue.peek();
        System.out.println("Peeked element: " + frontElement);
        // Expected Output: Peeked element: 10

        // Dequeue operation (poll() or remove())
        // poll() returns null if empty; remove() throws an exception.
        int dequeuedElement = queue.poll();
        System.out.println("Dequeued element: " + dequeuedElement);
        // Expected Output: Dequeued element: 10
        System.out.println("Queue after poll: " + queue);
        // Expected Output: Queue after poll: [20, 30]
    }
}

Key Difference: ArrayDeque is backed by a resizable array, while LinkedList is backed by nodes and pointers. For queue operations (adding to tail, removing from head), ArrayDeque is generally faster due to better cache locality and lower memory overhead per element.

• Breadth-First Search (BFS): The most critical application of a queue. BFS is an algorithm for traversing a tree or graph data structure level by level. The queue is used to store the nodes to visit next, ensuring that you explore all nodes at the present depth before moving on to the next level.

  • Binary Tree Level Order Traversal (#102)
  • Number of Islands (#200)
  • Rotting Oranges (#994)

• Resource Management / Task Scheduling: Queues are used in systems to manage shared resources or schedule tasks that must be executed in the order they were received. This includes CPU scheduling, print queues, and handling server requests.

  • Implement Stack using Queues (#225)
  • Design Circular Queue (#622)

Matrix

Definition: A Matrix, commonly known as a 2D Array, is a fundamental data structure that stores elements in a grid of rows and columns. It's a collection of elements of the same type, arranged in a fixed number of rows and columns. Matrices are the natural way to represent any problem involving a grid, such as a game board, a maze, an image, or tabular data.

• Access (at [row][col]): O(1)
• Update (at [row][col]): O(1)
• Search (for a value, unsorted): O(N * M) where N is the number of rows and M is the number of columns.

Space Complexity: O(N * M) to store N * M elements.

• Constant Time Access: Accessing or updating any element is extremely fast if you know its row and column index.
• Intuitive Representation: It provides a simple and direct way to model grid-based problems.
• Cache Friendliness: Iterating through elements sequentially (e.g., row by row) is very cache-friendly, leading to good performance.

• Fixed Size: In most languages, matrices are static, meaning their size must be known at creation. Resizing a matrix is an expensive operation that requires creating a new matrix and copying all elements.
• Costly Structural Changes: Inserting or deleting entire rows or columns is inefficient, as it may require shifting a large number of elements.

Python Example: This example demonstrates creating, accessing, and iterating through a matrix (represented as a list of lists).

# A 3x4 matrix (3 rows, 4 columns)
matrix = [
    [1, 2, 3, 4],
    [5, 6, 7, 8],
    [9, 10, 11, 12]
]

# Access an element (O(1))
element = matrix[1][2] # Row 1, Column 2
print(f"Element at [1][2]: {element}")
# Expected Output: Element at [1][2]: 7

# Update an element (O(1))
matrix[1][2] = 99
print(f"Updated element at [1][2]: {matrix[1][2]}")
# Expected Output: Updated element at [1][2]: 99

# Iterate through the matrix
print("Iterating through the matrix:")
for row in matrix:
    for item in row:
        print(item, end=" ")
    print()
# Expected Output:
# Iterating through the matrix:
# 1 2 3 4 
# 5 6 99 8 
# 9 10 11 12 

Java Example: This example demonstrates creating, accessing, and iterating through a 2D array.

public class MatrixExample {
    public static void main(String[] args) {
        // A 3x4 matrix (3 rows, 4 columns)
        int[][] matrix = {
            {1, 2, 3, 4},
            {5, 6, 7, 8},
            {9, 10, 11, 12}
        };

        // Access an element (O(1))
        int element = matrix[1][2]; // Row 1, Column 2
        System.out.println("Element at [1][2]: " + element);
        // Expected Output: Element at [1][2]: 7

        // Update an element (O(1))
        matrix[1][2] = 99;
        System.out.println("Updated element at [1][2]: " + matrix[1][2]);
        // Expected Output: Updated element at [1][2]: 99

        // Iterate through the matrix
        System.out.println("Iterating through the matrix:");
        for (int i = 0; i < matrix.length; i++) { // Iterate rows
            for (int j = 0; j < matrix[i].length; j++) { // Iterate columns
                System.out.print(matrix[i][j] + " ");
            }
            System.out.println();
        }
        // Expected Output:
        // Iterating through the matrix:
        // 1 2 3 4 
        // 5 6 99 8 
        // 9 10 11 12 
    }
}

• Grid Traversal (DFS & BFS): This is the most common pattern. The matrix is treated as an implicit graph where each cell (i, j) is a node. Edges connect a cell to its adjacent neighbors (up, down, left, right). These traversals are used to find paths, connected areas, and solve mazes.

  • Number of Islands (#200)
  • Rotting Oranges (#994)
  • Word Search (#79)

• Dynamic Programming: Many DP problems use a matrix (often called a dp table) to store the results of subproblems. The state dp[i][j] typically represents the solution for a subproblem of size i and j.

  • Unique Paths (#62)
  • Longest Common Subsequence (#1143)
  • Edit Distance (#72)

• Matrix Manipulation & Simulation: These problems require you to directly modify the matrix according to a set of rules. This can include rotating the matrix, transposing it, or simulating a process like a game over several steps.

  • Rotate Image (#48)
  • Set Matrix Zeroes (#73)
  • Game of Life (#289)

• Searching in a Sorted Matrix: A special category of problems where the matrix has a sorted structure (e.g., rows are sorted, columns are sorted). This allows for search algorithms that are much more efficient than a full scan.

  • Search a 2D Matrix (#74)

Tree

Definition: A Tree is a widely used non-linear, hierarchical data structure consisting of nodes connected by edges. Each tree has a root node (the topmost node), and every other node is a descendant of the root. Unlike other data structures, a tree has no cycles. Key terms include parent, child, and leaf (a node with no children). The most common type in interviews is the Binary Tree, where each node has at most two children: a left child and a right child.

• Access (by value): O(N) in the worst case (if the tree is skewed like a linked list). For a balanced tree, this improves to O(log N).
• Search (by value): O(N) in the worst case. O(log N) for balanced trees.
• Insertion: O(N) in the worst case. O(log N) for balanced trees.
• Deletion: O(N) in the worst case. O(log N) for balanced trees.

The O(N) worst-case performance is a critical weakness of unbalanced trees. Specialized trees like Binary Search Trees (BSTs) and Heaps provide more efficient operations.

Space Complexity: O(N) to store N nodes. The space required for recursion during traversal is O(H), where H is the height of the tree (O(log N) for a balanced tree, O(N) for a skewed tree).

• Represents Hierarchical Data: Trees are a natural fit for representing hierarchical relationships, such as file systems, organizational charts, or family trees.
• Efficient Operations (in balanced trees): Balanced trees provide efficient O(log N) time complexity for searching, inserting, and deleting elements, which is significantly faster than the O(N) of linear data structures for large datasets.
• Reflects Recursive Structures: Many tree problems can be solved elegantly with recursion, where a problem is broken down into smaller, identical problems on its subtrees.

• Unbalanced Performance Degradation: If a tree becomes unbalanced (skewed), its performance for most operations degrades to O(N), which is no better than a linked list.
• Implementation Complexity: The logic for implementing tree operations, especially for insertion and deletion, is generally more complex than for linear data structures.

Python Example: This example defines a TreeNode and performs a recursive In-order traversal.

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

# Manually create a simple binary tree:
#     10
#    /  \
#   5    15
root = TreeNode(10)
root.left = TreeNode(5)
root.right = TreeNode(15)

def in_order_traversal(node):
    """Recursively traverses the tree in Left-Root-Right order."""
    if not node:
        return
    in_order_traversal(node.left)
    print(node.val, end=" ")
    in_order_traversal(node.right)

print("In-order traversal:", end=" ")
in_order_traversal(root)
# Expected Output: In-order traversal: 5 10 15 

Java Example: This example defines a TreeNode and performs the same recursive traversal.

public class TreeExample {

    // Definition for a binary tree node.
    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int val) { this.val = val; }
    }

    /**
     * Recursively traverses the tree in Left-Root-Right order.
     */
    public static void inOrderTraversal(TreeNode node) {
        if (node == null) {
            return;
        }
        inOrderTraversal(node.left);
        System.out.print(node.val + " ");
        inOrderTraversal(node.right);
    }

    public static void main(String[] args) {
        // Manually create a simple binary tree:
        //     10
        //    /  \
        //   5    15
        TreeNode root = new TreeNode(10);
        root.left = new TreeNode(5);
        root.right = new TreeNode(15);
        
        System.out.print("In-order traversal: ");
        inOrderTraversal(root);
        // Expected Output: In-order traversal: 5 10 15 
    }
}

• Tree Traversal (DFS and BFS): This is the most fundamental tree pattern. You must know how to traverse a tree to solve almost any problem.

  • Depth-First Search (DFS): Explores as far down a path as possible before backtracking. Implemented with recursion or a stack.
    • In-order (Left, Root, Right): Binary Tree Inorder Traversal (#94)
    • Pre-order (Root, Left, Right): Binary Tree Preorder Traversal (#144)
    • Post-order (Left, Right, Root): Binary Tree Postorder Traversal (#145)
  • Breadth-First Search (BFS): Explores the tree level by level. Implemented with a queue.
    • Level Order Traversal: Binary Tree Level Order Traversal (#102)

• Recursive Solutions: Many tree problems have concise, recursive solutions that operate on the subtrees of a node.

  • Maximum Depth of Binary Tree (#104): maxDepth = 1 + max(maxDepth(left), maxDepth(right))
  • Same Tree (#100): Check if two trees are structurally identical and have the same node values.
  • Symmetric Tree (#101): Check if a tree is a mirror image of itself.

• Path Problems: Problems that involve finding or evaluating a path from the root to a leaf.

  • Path Sum (#112): Check if there exists a root-to-leaf path that sums up to a given value.

Remember: The goal isn't just to memorize implementations, but to understand the underlying principles and trade-offs that make each data structure suitable for specific problems.

For more advanced data structures, check out Advanced Data Structures.

For core algorithmic techniques, check out Core Algorithms and Patterns Part 1 and Core Algorithms and Patterns Part 2.