Scala Cheatsheet for LeetCode

0. Before You Start

• Since Scala provides immutable collections by default, add this import at the top of every solution that uses mutable collections.
• Import math package for min, max and common math functions.
• We use Scala3 syntax for control flows so no parentheses (more Python-like)

import scala.collection.mutable._
import scala.math._

1. Data Structure Mapping

Concept	Java	Python	Scala
Fixed array	int[]	list	Array[Int]
Tuple	—	tuple	(Int, Int)
Dynamic array	ArrayList<T>	list	ArrayBuffer[T]
Map	Map<K,V>	dict	Map[K,V]
Set	Set<T>	set	Set[T]
Queue (BFS)	LinkedList<T>	collections.deque	ArrayDeque[T]
Stack	Deque<T>	list	ArrayDeque[T]
Min-heap	PriorityQueue<T>	heapq	PriorityQueue[T]()(Ordering[T].reverse)
Max-heap	PriorityQueue<T> (reversed)	heapq (negated)	PriorityQueue[T]()
Sorted map	TreeMap<K,V>	sortedcontainers.SortedDict	TreeMap[K,V]

2. Variables & Types

val x = 5          // immutable (prefer this)
var i = 0          // mutable

val s: String = "hello"
val arr: Array[Int] = Array(1, 2, 3)

// Int.MaxValue / Int.MinValue (same as Java's Integer.MAX_VALUE)
val big = Int.MaxValue
val small = Int.MinValue

3. Control Flow

// if/else is an expression
val result = if x > 0 then "pos" else "neg"

// for loop
for i <- 0 until n do ()          // 0,1,...,n-1
for i <- 0 to n do ()             // 0,1,...,n
for i <- n-1 to 0 by -1 do ()    // reverse

// while
var i = 0
while i < n do i += 1

// break — avoid if possible; use a flag or return instead
// If needed:
import scala.util.control.Breaks._
breakable {
  for i <- 0 until n do
    if arr(i) == target then break()
}

4. Pattern Matching

Replaces switch and is much more powerful:

x match {
  case 0 => "zero"
  case 1 | 2 => "one or two"
  case n if n < 0 => "negative"
  case _ => "other"
}

// Destructure tuples
val pair = (1, "hello")
pair match {
  case (n, s) => println(s"$n and $s")
}

// Match on Option (replaces null checks)
map.get("key") match {
  case Some(v) => println(v)
  case None    => println("missing")
}

5. Functional Idioms

// map / filter / reduce
arr.map(_ * 2)
arr.filter(_ % 2 == 0)
arr.reduce(_ + _)
arr.foldLeft(0)(_ + _)            // fold with initial value

// flatMap / flatten
List(List(1,2), List(3,4)).flatten        // List(1,2,3,4)
arr.flatMap(x => Array(x, x * 2))

// zip / zipWithIndex
val a = Array(1, 2, 3)
val b = Array("a", "b", "c")
a.zip(b)                           // Array((1,a),(2,b),(3,c))
arr.zipWithIndex.foreach { case (v, i) => println(i, v) }

// sliding / grouped
arr.sliding(2).toList              // consecutive pairs: [[1,2],[2,3],...]
(1 to 9).grouped(3).toList         // [[1,2,3],[4,5,6],[7,8,9]]

// distinct / toSet
arr.distinct
arr.toSet

// mkString
Array(1, 2, 3).mkString(", ")     // "1, 2, 3"

// forall / exists
arr.forall(_ > 0)
arr.exists(_ < 0)

// take / drop / takeWhile / dropWhile
arr.take(3)
arr.drop(2)
arr.takeWhile(_ < 5)

6. Arrays

val arr = Array(1, 2, 3)
val zeros = Array.fill(5)(0)          // [0,0,0,0,0]
val grid = Array.fill(3, 4)(0)        // 3x4 2D array

arr(0)                                // access (NOT arr[0])
arr(0) = 10                           // set

arr.length                            // length
arr.size                              // size (same as length)
arr.sum
arr.max
arr.min

// Slice (returns Array)
arr.slice(1, 3)                       // like Python arr[1:3]

// Iterate
for x <- arr do println(x)
arr.foreach(println)

// Map / filter (returns Array when called on Array)
arr.map(_ * 2)
arr.filter(_ > 1)

// indexOf
arr.indexOf(3)                        // -1 if not found
arr.contains(3)

7. Strings

val s = "hello"
s.length
s(0)                                  // 'h' — char access
s.substring(1, 3)                     // "el"
s.toCharArray                         // Array[Char]
s.split(" ")                          // Array[String]
s.trim
s.toUpperCase
s.toLowerCase
s.reverse
s.count(_ == 'l')                     // count occurrences of char
s.replace("l", "r")
s.contains("ell")
s.startsWith("he")

// Char <-> Int
'a'.toInt                             // 97
97.toChar                             // 'a'
'a' - 'a'                             // 0  (Int arithmetic on Char works)

// Build a string
val sb = new StringBuilder
sb.append("hello")
sb.append(' ')
sb.append("world")
sb.toString

// From char array / list
Array('h','i').mkString              // "hi"
List("a","b","c").mkString(", ")     // "a, b, c"

8. HashMap

val map = HashMap[String, Int]()

// Put
map("key") = 1

// Get — returns Option[V]
map.get("key")          // Some(1) or None
map("key")              // throws if missing
map.getOrElse("key", 0) // safe default

// Contains
map.contains("key")

// Remove
map.remove("key")

// Iterate
for (k, v) <- map do println(s"$k -> $v")
map.foreach { case (k, v) => println(k, v) }

// Count frequency:
val freq = s.groupBy(identity).mapValues(_.length)

// Keys / values
map.keys
map.values
map.toList           // List[(K,V)]

9. HashSet

val set = HashSet[Int]()

set.add(1)
set += 1             // same
set -= 1             // remove
set.contains(1)
set.remove(1)
set.size

// Immutable set literal (useful for lookup tables)
val vowels = Set('a', 'e', 'i', 'o', 'u')
vowels('a')          // true — same as .contains

10. Queue (BFS)

val q = Queue[Int]()

q.enqueue(1)
q.enqueue(2, 3)       // enqueue multiple
q.dequeue()           // removes and returns front
q.front               // peek without removing
q.isEmpty
q.size

// BFS template
val queue = Queue[(Int, Int)]()   // (node, distance)
queue.enqueue((start, 0))
val visited = HashSet[Int]()

while queue.nonEmpty do
  val (node, dist) = queue.dequeue()
  if !visited.contains(node) then
    visited.add(node)
    // process node
    for neighbor <- getNeighbors(node) do
      queue.enqueue((neighbor, dist + 1))

11. Stack

val stack = Stack[Int]()

stack.push(1)
stack.pop()          // removes and returns top
stack.top            // peek
stack.isEmpty

// Alternatively use ArrayBuffer as stack (common in interviews)
val stk = ArrayBuffer[Int]()
stk.append(1)
stk.last             // peek
stk.remove(stk.size - 1)   // pop

12. Priority Queue (Heap)

// Max-heap (default — largest on top)
val maxHeap = PriorityQueue[Int]()
maxHeap.enqueue(3, 1, 4)
maxHeap.dequeue()    // 4

// Min-heap
val minHeap = PriorityQueue[Int]()(Ordering[Int].reverse)
minHeap.enqueue(3, 1, 4)
minHeap.dequeue()    // 1

// Heap of tuples — e.g. (distance, node) for Dijkstra
// Min by first element:
val pq = PriorityQueue[(Int, Int)]()(Ordering.by(-_._1))
pq.enqueue((5, 0))
val (dist, node) = pq.dequeue()

13. Sorting

// Arrays
arr.sorted                         // ascending, new array
arr.sortWith(_ > _)                // descending
arr.sortBy(x => -x)               // by key

// Sort array of tuples by second element
val pairs = Array((1,3),(2,1),(3,2))
pairs.sortBy(_._2)
pairs.sortWith((a,b) => a._2 < b._2)

// In-place sort
scala.util.Sorting.quickSort(arr)

// List / Seq
list.sorted
list.sortBy(_.length)

14. Math & Bit Operations

math.abs(-5)
math.max(a, b)
math.min(a, b)
math.pow(2, 10).toInt             // 1024
math.sqrt(16.0)                   // 4.0

// Integer division and modulo (same as Java)
7 / 2                             // 3
7 % 2                             // 1

// Bit ops
n & 1                             // check last bit (odd/even)
n >> 1                            // right shift
n << 1                            // left shift
n ^ m                             // XOR
~n                                // bitwise NOT
Integer.bitCount(n)               // popcount (count set bits)
Integer.toBinaryString(n)         // binary string

// Long for overflow-prone problems
val l: Long = 1L << 40

15. Common Algorithm Templates

Binary Search

var lo = 0
var hi = arr.length - 1
while lo <= hi do
  val mid = lo + (hi - lo) / 2
  if arr(mid) == target then return mid
  else if arr(mid) < target then lo = mid + 1
  else hi = mid - 1

DFS (recursive)

val visited = HashSet[Int]()

def dfs(node: Int): Unit =
  if visited.contains(node) then return
  visited.add(node)
  for neighbor <- graph(node) do dfs(neighbor)

Dynamic Programming

val dp = Array.fill(n + 1)(0)
dp(0) = 1
for i <- 1 to n do
  dp(i) = dp(i - 1) + (if i >= 2 then dp(i - 2) else 0)

16. Gotchas for Python/Java Developers

Situation	Pitfall	Fix
Array access	arr[i] → compile error	Use arr(i)
Missing map key	map("key") throws	Use map.getOrElse("key", 0)
Mutable collections	Forgot mutable. prefix	import scala.collection.mutable._
Int overflow	Int max ~2.1B	Use Long for large products/sums
Heap direction	Default PQ is max-heap	Pass Ordering[T].reverse for min-heap
== on objects	Works correctly (unlike Java)	Safe to use == for value equality
return in lambdas	Returns from enclosing method	Avoid return inside map/foreach
Empty collection	.max on empty throws	Guard with .nonEmpty or use reduceOption
until vs to	Off-by-one	0 until n = [0,n), 0 to n = [0,n]