Ruby DSA Cheat Sheet

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

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

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

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

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}" }

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

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)

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

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

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

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

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

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

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

# 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

# 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

# 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 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