Ruby DSA Cheat Sheet

Ruby DSA Cheat Sheet

A comprehensive guide to data structures and algorithms in Ruby. Includes examples, time/space complexities, and usage patterns.

---

📑 Table of Contents

• 1. Arrays
• 2. Hashes / Dictionaries
• 3. Strings
• 4. Linked Lists
• 5. Stacks & Queues
• 6. Heaps / Priority Queue
• 7. Trees
• 8. Graphs
• 9. Common Algorithms
  • Recursion / Backtracking
  • Dynamic Programming
  • Sliding Window
  • Two Pointers
• 10. Complexity Cheats

---

1. Arrays

Creation

arr = []          # empty array
arr = [1, 2, 3]   # initialized array

Common Operations

arr.push(4)        # add to end
arr.pop            # remove from end
arr.unshift(0)     # add to start
arr.shift          # remove from start
arr.include?(2)    # check if exists
arr.index(3)       # get index of first occurrence
arr.uniq           # remove duplicates
arr.sort           # sort array
arr.reverse        # reverse array
arr.sum            # sum of elements

Iteration

arr.each { |x| puts x }
arr.map { |x| x * 2 }          # returns new array
arr.select { |x| x > 2 }       # filter
arr.reject { |x| x > 2 }       # opposite of select
arr.reduce(0) { |sum, x| sum + x }  # fold/reduce

Time Complexity

Operation	Average	Worst
Access	O(1)	O(1)
Append/Push	O(1)	O(n)
Prepend/Unshift	O(n)	O(n)
Delete by index	O(n)	O(n)
Search	O(n)	O(n)

---

2. Hashes / Dictionaries

Creation

h = {}                   # empty hash
h = { a: 1, b: 2 }       # initialized
h = Hash.new(0)           # default value

Common Operations

h[:c] = 3                 # add/update
h.delete(:a)              # delete key
h.key?(:b)                # check existence
h.values                  # array of values
h.keys                    # array of keys
h.each { |k,v| puts "#{k}: #{v}" }

Use Cases

• Frequency counting
• Lookup tables
• Memoization

Time Complexity

Operation	Average	Worst
Access	O(1)	O(n)
Insert	O(1)	O(n)
Delete	O(1)	O(n)
Search	O(1)	O(n)

---

3. Strings

Basics

s = "hello"
s.length          # 5
s[0]              # 'h'
s[0..2]           # 'hel'
s.chars           # ['h','e','l','l','o']
s.split           # ["hello"]
s.include?("ll")  # true

Operations

s.gsub("h","H")      # replace
s.reverse            # reverse
s.count("l")         # count occurrences
s.start_with?("he")  # check prefix
s.end_with?("lo")    # check suffix
s << " world"        # append (mutable)

Iteration

s.each_char { |c| puts c }
s.chars.map(&:upcase)   # ['H','E','L','L','O']

---

4. Linked Lists

Node Class Example

class Node
  attr_accessor :val, :next
  def initialize(val)
    @val = val
    @next = nil
  end
end

Operations

• Insert at head/tail
• Delete node
• Traverse
• Reverse

Time Complexity

Operation	Singly	Doubly
Insert	O(1)	O(1)
Delete	O(n)	O(1)
Search	O(n)	O(n)

---

5. Stacks & Queues

Stack (LIFO)

stack = []
stack.push(1)   # push
stack.pop       # pop
stack.last      # peek

Queue (FIFO)

queue = []
queue.push(1)   # enqueue
queue.shift     # dequeue
queue.first     # peek

Time Complexity

• Stack push/pop: O(1)
• Queue enqueue/dequeue: O(1) with proper deque, O(n) if using Array for shift

---

6. Heaps / Priority Queue

• Ruby: Use priority_queue gem or implement manually.
• Operations:
  • Insert: O(log n)
  • Extract Min/Max: O(log n)
  • Peek: O(1)
• Use Cases: Top-K, Dijkstra, scheduling

---

7. Trees

Binary Tree Node

class TreeNode
  attr_accessor :val, :left, :right
  def initialize(val)
    @val = val
    @left = nil
    @right = nil
  end
end

Traversals

# Inorder traversal
def inorder(root)
  return if root.nil?
  inorder(root.left)
  print root.val
  inorder(root.right)
end

Binary Search Tree (BST) Complexity

Operation	Avg	Worst
Insert	O(log n)	O(n)
Search	O(log n)	O(n)
Delete	O(log n)	O(n)

Other Trees

• AVL, Red-Black, Segment Tree, Trie

---

8. Graphs

Representation

graph = {
  0 => [1,2],
  1 => [0,3],
  2 => [0],
  3 => [1]
}

Traversals

• BFS (Queue)
• DFS (Stack / Recursion)

Common Algorithms

• Dijkstra, Bellman-Ford, Floyd-Warshall
• Kruskal, Prim

Complexity

• BFS/DFS: O(V + E)

---

9. Common Algorithms

Recursion / Backtracking

# Factorial (Recursive)
def factorial(n)
  return 1 if n <= 1
  n * factorial(n - 1)
end

# Fibonacci (Recursive)
def fib(n)
  return n if n <= 1
  fib(n - 1) + fib(n - 2)
end

# Permutations (Backtracking)
def permute(arr)
  return [arr] if arr.length <= 1
  result = []
  arr.each_with_index do |el, i|
    rest = arr[0...i] + arr[i+1..-1]
    permute(rest).each { |p| result << [el] + p }
  end
  result
end

# Subsets (Backtracking / Recursion)
def subsets(arr)
  return [[]] if arr.empty?
  first = arr[0]
  rest_subsets = subsets(arr[1..-1])
  rest_subsets + rest_subsets.map { |s| [first] + s }
end

# Combinations (n choose k)
def combinations(arr, k)
  return [[]] if k == 0
  return [] if arr.empty?
  first, *rest = arr
  with_first = combinations(rest, k - 1).map { |c| [first] + c }
  without_first = combinations(rest, k)
  with_first + without_first
end

Dynamic Programming

# Memoization (Top-Down)
def fib_memo(n, memo = {})
  return n if n <= 1
  memo[n] ||= fib_memo(n - 1, memo) + fib_memo(n - 2, memo)
end

# Tabulation (Bottom-Up)
def fib_tab(n)
  return n if n <= 1
  dp = Array.new(n+1)
  dp[0], dp[1] = 0, 1
  (2..n).each { |i| dp[i] = dp[i-1] + dp[i-2] }
  dp[n]
end

Sliding Window

# Maximum Sum Subarray (Size k)
def max_subarray_sum(arr, k)
  return nil if arr.size < k
  max_sum = arr[0...k].sum
  current_sum = max_sum
  (k...arr.size).each do |i|
    current_sum += arr[i] - arr[i - k]
    max_sum = [max_sum, current_sum].max
  end
  max_sum
end

# Minimum Length Subarray (Sum ≥ target)
def min_subarray_len(arr, target)
  left = 0
  sum = 0
  min_len = Float::INFINITY
  arr.each_with_index do |num, right|
    sum += num
    while sum >= target
      min_len = [min_len, right - left + 1].min
      sum -= arr[left]
      left += 1
    end
  end
  min_len == Float::INFINITY ? 0 : min_len
end

# Length of Longest Substring Without Repeating Characters
def length_of_longest_substring(s)
  seen = {}
  left = 0
  max_len = 0
  s.chars.each_with_index do |c, right|
    if seen.key?(c) && seen[c] >= left
      left = seen[c] + 1
    end
    seen[c] = right
    max_len = [max_len, right - left + 1].max
  end
  max_len
end

Two Pointers

# Two Sum on Sorted Array
def two_sum_sorted(arr, target)
  left, right = 0, arr.length - 1
  while left < right
    sum = arr[left] + arr[right]
    return [left, right] if sum == target
    sum < target ? left += 1 : right -= 1
  end
  nil
end

# Palindrome Check
def palindrome?(s)
  left, right = 0, s.length - 1
  while left < right
    return false if s[left] != s[right]
    left += 1
    right -= 1
  end
  true
end

---

10. Complexity Cheats

Structure / Operation	Avg Time	Worst Time	Space
Array Access	O(1)	O(1)	O(n)
Array Search	O(n)	O(n)	O(1)
Hash Lookup	O(1)	O(n)	O(n)
Stack/Queue	O(1)	O(1)	O(n)
BST Lookup	O(log n)	O(n)	O(n)
Heap Insert/Extract	O(log n)	O(log n)	O(n)
Graph Traversal BFS/DFS	O(V+E)	O(V+E)	O(V)
Sorting	O(n log n)	O(n log n)	O(n)

---

This cheat sheet covers Ruby-specific methods, common data structures, algorithm patterns, and their complexities for thorough DSA prep.