Part 3: Data Structures Fundamentals

Why These Data Structures Matter

In my early interviews, I struggled because I didn't deeply understand the data structures. I could explain what an array was, but I couldn't leverage its properties to solve problems efficiently. This part covers the fundamental data structures that appear in 70% of coding interviews.

Arrays and Strings

My Relationship with Arrays

Arrays seemed simple until I faced interview problems. The key insight I learned: arrays enable two powerful techniques—two pointers and sliding window.

Core Array Patterns

Pattern 1: Two Pointers (Opposite Directions)

Problem: Reverse a string in-place

def reverse_string(s: list[str]) -> None:
    """
    Reverse string in-place using two pointers
    
    My approach: Swap characters from both ends
    Time: O(n), Space: O(1)
    """
    left, right = 0, len(s) - 1
    
    while left < right:
        # Swap characters
        s[left], s[right] = s[right], s[left]
        left += 1
        right -= 1

# Test
chars = ['h', 'e', 'l', 'l', 'o']
reverse_string(chars)
print(chars)  # ['o', 'l', 'l', 'e', 'h']

Problem: Container With Most Water (Medium)

This problem taught me to think about what to optimize:

def max_area(height: list[int]) -> int:
    """
    Find two lines that form container with most water
    
    My insight: Always move the pointer with smaller height
    Why? Moving taller won't increase area (width decreases)
    
    Time: O(n), Space: O(1)
    """
    left, right = 0, len(height) - 1
    max_water = 0
    
    while left < right:
        # Calculate current area
        width = right - left
        current_height = min(height[left], height[right])
        current_area = width * current_height
        
        max_water = max(max_water, current_area)
        
        # Move pointer with smaller height
        if height[left] < height[right]:
            left += 1
        else:
            right -= 1
    
    return max_water

# My test cases
print(max_area([1, 8, 6, 2, 5, 4, 8, 3, 7]))  # 49

Pattern 2: Two Pointers (Same Direction)

Problem: Remove Duplicates from Sorted Array

def remove_duplicates(nums: list[int]) -> int:
    """
    Remove duplicates in-place, return new length
    
    My approach: Slow pointer tracks unique position
                 Fast pointer scans array
    
    Time: O(n), Space: O(1)
    """
    if not nums:
        return 0
    
    # Slow pointer - position for next unique element
    slow = 0
    
    # Fast pointer - scan the array
    for fast in range(1, len(nums)):
        if nums[fast] != nums[slow]:
            slow += 1
            nums[slow] = nums[fast]
    
    return slow + 1

# Test
nums = [1, 1, 2, 2, 3, 4, 4]
length = remove_duplicates(nums)
print(nums[:length])  # [1, 2, 3, 4]

Pattern 3: Sliding Window (Fixed Size)

Problem: Maximum Sum Subarray of Size K

def max_sum_subarray(nums: list[int], k: int) -> int:
    """
    Find maximum sum of contiguous subarray of size k
    
    My approach: Sliding window
    - Calculate initial window sum
    - Slide by removing left, adding right
    
    Time: O(n), Space: O(1)
    """
    if len(nums) < k:
        return 0
    
    # Calculate first window
    window_sum = sum(nums[:k])
    max_sum = window_sum
    
    # Slide the window
    for i in range(k, len(nums)):
        # Remove leftmost, add rightmost
        window_sum = window_sum - nums[i - k] + nums[i]
        max_sum = max(max_sum, window_sum)
    
    return max_sum

# Test
print(max_sum_subarray([2, 1, 5, 1, 3, 2], 3))  # 9

Pattern 4: Sliding Window (Variable Size)

Problem: Longest Substring Without Repeating Characters

This was asked in 3 of my interviews:

def length_of_longest_substring(s: str) -> int:
    """
    Find length of longest substring without repeating characters
    
    My approach: Sliding window with hash map
    - Expand window by moving right
    - Shrink window when duplicate found
    
    Time: O(n), Space: O(min(n, m)) where m is charset size
    """
    char_index = {}  # {character: last_seen_index}
    max_length = 0
    window_start = 0
    
    for window_end, char in enumerate(s):
        # If character seen and within current window
        if char in char_index and char_index[char] >= window_start:
            # Move window start past the duplicate
            window_start = char_index[char] + 1
        
        # Update character's last seen position
        char_index[char] = window_end
        
        # Update max length
        current_length = window_end - window_start + 1
        max_length = max(max_length, current_length)
    
    return max_length

# My test cases - edge cases matter!
print(length_of_longest_substring("abcabcbb"))  # 3 ("abc")
print(length_of_longest_substring("bbbbb"))     # 1 ("b")
print(length_of_longest_substring("pwwkew"))    # 3 ("wke")
print(length_of_longest_substring(""))          # 0

String-Specific Problems

Problem: Valid Palindrome

def is_palindrome(s: str) -> bool:
    """
    Check if string is palindrome (alphanumeric only, case-insensitive)
    
    My approach: Two pointers with character filtering
    Time: O(n), Space: O(1)
    """
    left, right = 0, len(s) - 1
    
    while left < right:
        # Skip non-alphanumeric from left
        while left < right and not s[left].isalnum():
            left += 1
        
        # Skip non-alphanumeric from right
        while left < right and not s[right].isalnum():
            right -= 1
        
        # Compare characters (case-insensitive)
        if s[left].lower() != s[right].lower():
            return False
        
        left += 1
        right -= 1
    
    return True

# Test
print(is_palindrome("A man, a plan, a canal: Panama"))  # True
print(is_palindrome("race a car"))                       # False

Problem: Group Anagrams

def group_anagrams(strs: list[str]) -> list[list[str]]:
    """
    Group strings that are anagrams of each other
    
    My approach: Use sorted string as key
    Time: O(n * k log k) where k is max string length
    Space: O(n)
    """
    from collections import defaultdict
    
    anagram_groups = defaultdict(list)
    
    for word in strs:
        # Sorted string is same for anagrams
        key = ''.join(sorted(word))
        anagram_groups[key].append(word)
    
    return list(anagram_groups.values())

# Test
words = ["eat", "tea", "tan", "ate", "nat", "bat"]
print(group_anagrams(words))
# [['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']]

Hash Tables (Dictionaries)

When I Reach for Hash Tables

Hash tables became my go-to for:

• Counting frequencies

• Detecting duplicates

• Finding complements

• Caching results

Core Hash Table Patterns

Pattern 1: Frequency Counter

Problem: First Unique Character

def first_unique_char(s: str) -> int:
    """
    Find first non-repeating character index
    
    My approach: Two passes
    1. Count frequencies
    2. Find first with count 1
    
    Time: O(n), Space: O(1) - max 26 characters
    """
    from collections import Counter
    
    # Count character frequencies
    char_count = Counter(s)
    
    # Find first unique character
    for i, char in enumerate(s):
        if char_count[char] == 1:
            return i
    
    return -1

# Test
print(first_unique_char("leetcode"))      # 0 ('l')
print(first_unique_char("loveleetcode"))  # 2 ('v')

Pattern 2: Complement Finding

Problem: Two Sum (Revisited with Explanation)

def two_sum(nums: list[int], target: int) -> list[int]:
    """
    Find two indices that sum to target
    
    My insight: Instead of checking all pairs O(n²),
                store each number and check if complement exists O(n)
    
    Time: O(n), Space: O(n)
    """
    seen = {}  # {number: index}
    
    for i, num in enumerate(nums):
        complement = target - num
        
        # Check if complement was seen before
        if complement in seen:
            return [seen[complement], i]
        
        # Store current number for future complements
        seen[num] = i
    
    return []

# Edge cases I learned to test
print(two_sum([2, 7, 11, 15], 9))  # [0, 1]
print(two_sum([3, 2, 4], 6))        # [1, 2] - not [0, 0]
print(two_sum([3, 3], 6))           # [0, 1] - same number, different indices

Pattern 3: Detecting Duplicates

Problem: Contains Duplicate

def contains_duplicate(nums: list[int]) -> bool:
    """
    Check if array has duplicates
    
    My approach: Set to track seen numbers
    Time: O(n), Space: O(n)
    """
    seen = set()
    
    for num in nums:
        if num in seen:
            return True
        seen.add(num)
    
    return False

# Alternative: one-liner
def contains_duplicate_v2(nums: list[int]) -> bool:
    """Space-optimized comparison"""
    return len(nums) != len(set(nums))

# Test both
print(contains_duplicate([1, 2, 3, 1]))     # True
print(contains_duplicate_v2([1, 2, 3, 4]))  # False

Problem: Valid Anagram

def is_anagram(s: str, t: str) -> bool:
    """
    Check if two strings are anagrams
    
    My approach: Compare character frequencies
    Time: O(n), Space: O(1) - max 26 chars
    """
    if len(s) != len(t):
        return False
    
    from collections import Counter
    return Counter(s) == Counter(t)

# Manual approach (interview coding)
def is_anagram_manual(s: str, t: str) -> bool:
    """Without using Counter"""
    if len(s) != len(t):
        return False
    
    char_count = {}
    
    # Count characters in s
    for char in s:
        char_count[char] = char_count.get(char, 0) + 1
    
    # Decrement for characters in t
    for char in t:
        if char not in char_count:
            return False
        char_count[char] -= 1
        if char_count[char] < 0:
            return False
    
    return True

# Test
print(is_anagram("anagram", "nagaram"))  # True
print(is_anagram("rat", "car"))          # False

Linked Lists

My Linked List Journey

Linked lists intimidated me initially. The key breakthrough: draw the pointers before writing code.

Linked List Node Definition

class ListNode:
    """Standard singly linked list node"""
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

# Helper function I use for testing
def create_linked_list(values: list) -> ListNode:
    """Create linked list from array"""
    if not values:
        return None
    
    head = ListNode(values[0])
    current = head
    
    for val in values[1:]:
        current.next = ListNode(val)
        current = current.next
    
    return head

def print_linked_list(head: ListNode) -> list:
    """Convert linked list to array for printing"""
    result = []
    current = head
    
    while current:
        result.append(current.val)
        current = current.next
    
    return result

Core Linked List Patterns

Pattern 1: Two Pointers (Fast & Slow)

Problem: Middle of Linked List

def middle_node(head: ListNode) -> ListNode:
    """
    Find middle node of linked list
    
    My approach: Fast pointer moves 2x speed
    When fast reaches end, slow is at middle
    
    Time: O(n), Space: O(1)
    """
    slow = fast = head
    
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    
    return slow

# Test
head = create_linked_list([1, 2, 3, 4, 5])
middle = middle_node(head)
print(middle.val)  # 3

Problem: Linked List Cycle

def has_cycle(head: ListNode) -> bool:
    """
    Detect if linked list has cycle
    
    My approach: Floyd's cycle detection
    If fast catches slow, there's a cycle
    
    Time: O(n), Space: O(1)
    """
    if not head:
        return False
    
    slow = fast = head
    
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        
        if slow == fast:
            return True
    
    return False

Pattern 2: Reverse Linked List

This appears in SO many variations:

def reverse_list(head: ListNode) -> ListNode:
    """
    Reverse linked list iteratively
    
    My approach: Three pointers technique
    prev -> current -> next
    
    Time: O(n), Space: O(1)
    """
    prev = None
    current = head
    
    while current:
        # Save next node
        next_node = current.next
        
        # Reverse pointer
        current.next = prev
        
        # Move pointers forward
        prev = current
        current = next_node
    
    return prev

# Recursive approach (elegant but uses O(n) stack space)
def reverse_list_recursive(head: ListNode) -> ListNode:
    """
    Reverse recursively
    
    Time: O(n), Space: O(n) - call stack
    """
    if not head or not head.next:
        return head
    
    # Reverse rest of list
    new_head = reverse_list_recursive(head.next)
    
    # Reverse connection
    head.next.next = head
    head.next = None
    
    return new_head

# Test
head = create_linked_list([1, 2, 3, 4, 5])
reversed_head = reverse_list(head)
print(print_linked_list(reversed_head))  # [5, 4, 3, 2, 1]

Problem: Reverse Between Positions

def reverse_between(head: ListNode, left: int, right: int) -> ListNode:
    """
    Reverse linked list between positions left and right
    
    My approach: Find positions, reverse that portion
    Time: O(n), Space: O(1)
    """
    if not head or left == right:
        return head
    
    dummy = ListNode(0, head)
    prev = dummy
    
    # Move to position before left
    for _ in range(left - 1):
        prev = prev.next
    
    # Reverse from left to right
    current = prev.next
    for _ in range(right - left):
        next_node = current.next
        current.next = next_node.next
        next_node.next = prev.next
        prev.next = next_node
    
    return dummy.next

# Test
head = create_linked_list([1, 2, 3, 4, 5])
result = reverse_between(head, 2, 4)
print(print_linked_list(result))  # [1, 4, 3, 2, 5]

Pattern 3: Merge Operations

Problem: Merge Two Sorted Lists

def merge_two_lists(l1: ListNode, l2: ListNode) -> ListNode:
    """
    Merge two sorted linked lists
    
    My approach: Dummy node + comparison
    Time: O(n + m), Space: O(1)
    """
    dummy = ListNode(0)
    current = dummy
    
    while l1 and l2:
        if l1.val <= l2.val:
            current.next = l1
            l1 = l1.next
        else:
            current.next = l2
            l2 = l2.next
        current = current.next
    
    # Append remaining nodes
    current.next = l1 if l1 else l2
    
    return dummy.next

# Test
l1 = create_linked_list([1, 3, 5])
l2 = create_linked_list([2, 4, 6])
merged = merge_two_lists(l1, l2)
print(print_linked_list(merged))  # [1, 2, 3, 4, 5, 6]

Stacks

When to Use Stacks

From my experience, stacks are perfect for:

• Matching pairs (parentheses, brackets)

• Tracking previous elements

• Undo operations

• Expression evaluation

Core Stack Problems

Problem: Valid Parentheses (Complete Solution)

def is_valid(s: str) -> bool:
    """
    Check if parentheses/brackets are valid
    
    My approach: Stack to match opening with closing
    Time: O(n), Space: O(n)
    """
    # Map closing to opening brackets
    pairs = {
        ')': '(',
        '}': '{',
        ']': '['
    }
    
    stack = []
    
    for char in s:
        if char in pairs:
            # Closing bracket
            if not stack or stack[-1] != pairs[char]:
                return False
            stack.pop()
        else:
            # Opening bracket
            stack.append(char)
    
    # Valid if all matched (stack empty)
    return len(stack) == 0

# Test cases I always check
print(is_valid("()"))        # True
print(is_valid("()[]{}"))    # True
print(is_valid("(]"))        # False
print(is_valid("([)]"))      # False - interleaved
print(is_valid("{[]}"))      # True - nested

Problem: Daily Temperatures

This problem taught me monotonic stacks:

def daily_temperatures(temperatures: list[int]) -> list[int]:
    """
    For each day, find how many days until warmer temperature
    
    My approach: Monotonic decreasing stack
    Store indices of days waiting for warmer temp
    
    Time: O(n), Space: O(n)
    """
    n = len(temperatures)
    result = [0] * n
    stack = []  # Stack of indices
    
    for i, temp in enumerate(temperatures):
        # Check if current temp is warmer than previous days
        while stack and temperatures[stack[-1]] < temp:
            prev_day = stack.pop()
            result[prev_day] = i - prev_day
        
        stack.append(i)
    
    return result

# Test
temps = [73, 74, 75, 71, 69, 72, 76, 73]
print(daily_temperatures(temps))
# [1, 1, 4, 2, 1, 1, 0, 0]

Queues

Queue vs Stack

• Stack: LIFO (Last In, First Out) - like plates

• Queue: FIFO (First In, First Out) - like a line

Implementation in Python

from collections import deque

# Queue using deque (efficient O(1) operations)
queue = deque()
queue.append(1)      # Add to right
queue.append(2)
first = queue.popleft()  # Remove from left

# Stack using list
stack = []
stack.append(1)      # Push
stack.append(2)
top = stack.pop()    # Pop

Queue Problem Example

Problem: Moving Average from Data Stream

class MovingAverage:
    """
    Calculate moving average of last size values
    
    My approach: Queue to maintain window
    """
    def __init__(self, size: int):
        self.size = size
        self.queue = deque()
        self.window_sum = 0
    
    def next(self, val: int) -> float:
        """
        Add value and return current average
        Time: O(1), Space: O(size)
        """
        self.queue.append(val)
        self.window_sum += val
        
        # Remove old value if window full
        if len(self.queue) > self.size:
            self.window_sum -= self.queue.popleft()
        
        return self.window_sum / len(self.queue)

# Test
ma = MovingAverage(3)
print(ma.next(1))    # 1.0
print(ma.next(10))   # 5.5
print(ma.next(3))    # 4.67
print(ma.next(5))    # 6.0

Key Takeaways

From solving 100+ data structure problems:

1. Arrays: Master two pointers and sliding window

2. Strings: Often similar to arrays, watch for edge cases

3. Hash Tables: Default choice for O(1) lookup needs

4. Linked Lists: Draw the pointers before coding

5. Stacks: Perfect for matching pairs and previous elements

6. Queues: FIFO processing and sliding windows

Practice Problems

Problems I recommend solving:

Arrays:

• Best Time to Buy and Sell Stock

• Product of Array Except Self

• 3Sum

Strings:

• Longest Palindromic Substring

• Minimum Window Substring

• Valid Anagram

Hash Tables:

• Top K Frequent Elements

• Subarray Sum Equals K

Linked Lists:

• Remove Nth Node From End

• Reorder List

• Palindrome Linked List

Stacks/Queues:

• Min Stack

• Implement Queue using Stacks

• Largest Rectangle in Histogram

What's Next?

In Part 4: Advanced Data Structures, we'll explore:

• Binary trees and BST operations

• Graph traversal (BFS, DFS)

• Heaps and priority queues

• Trie data structures

These appear in 30% of interviews and separate good candidates from great ones!

---

This part is based on my experience solving 200+ array, string, and linked list problems.