# Class Inside Class, a Scala language concept

Last updated

A great aspect of Scala is being able to declare classes in other classes. This allows one to reduce repetition and for example refer to values of the outer class effortlessly.

Last updated

A great aspect of Scala is being able to declare classes in other classes. This allows one to reduce repetition and for example refer to values of the outer class effortlessly.

Fully unit-tested, with explanations and relevant concepts; new algorithms published about once a week.

- Compute the length of longest valid parentheses
- Check a binary tree is balanced
- Make a queue using stacks (Lists in Scala)
- Find height of binary tree
- Single-elimination tournament tree
- Reverse Polish Notation calculator
- Quick Sort sorting algorithm in pure immutable Scala
- Find minimum missing positive number in a sequence
- Least-recently used cache (LRU)
- Count pairs of a given expected sum
- Compute a Roman numeral for an Integer, and vice-versa
- Compute keypad possibilities
- Matching parentheses algorithm with foldLeft and a state machine
- Traverse a tree Breadth-First, immutably
- Read a matrix as a spiral
- Remove duplicates from a sorted list (state machine)
- Token Bucket Rate Limiter
- Leaky Bucket Rate Limiter
- Merge Sort: stack-safe, tail-recursive, in pure immutable Scala, N-way
- Longest increasing sub-sequence length
- Reverse first n elements of a queue
- Binary search a generic Array
- Game of Life
- Merge Sort: in pure immutable Scala
- Make a queue using Maps
- Is an Array a permutation?
- Count number of contiguous countries by colors
- Add numbers without using addition (plus sign)
- Tic Tac Toe MinMax solve
- Run-length encoding (RLE) Encoder
- Print Alphabet Diamond
- Find kth largest element in a List
- Balanced parentheses algorithm with tail-call recursion optimisation
- Reverse a String's words efficiently
- Count number of changes (manipulations) needed to make an anagram with foldLeft and a MultiSet
- Count passing cars
- Establish execution order from dependencies
- Counting inversions of a sequence (array) using a Merge Sort
- Longest common prefix of strings
- Check if an array is a palindrome
- Compute missing ranges
- Check a directed graph has a routing between two nodes (depth-first search)
- Compute nth row of Pascal's triangle
- Run-length encoding (RLE) Decoder
- Check if a number is a palindrome
- In a range of numbers, count the numbers divisible by a specific integer
- Compute minimum number of Fibonacci numbers to reach sum
- Find the index of a substring ('indexOf')
- Reshape a matrix
- Compute the steps to transform an anagram only using swaps
- Compute modulo of an exponent without exponentiation
- Closest pair of coordinates in a 2D plane
- Find the contiguous slice with the minimum average
- Compute maximum sum of subarray (Kadane's algorithm)
- Pure-functional double linked list
- Binary search in a rotated sorted array
- Check if a directed graph has cycles
- Rotate Array right in pure-functional Scala - using an unusual immutable efficient approach
- Check a binary tree is a search tree
- Length of the longest common substring
- Sliding Window Rate Limiter
- Tic Tac Toe board check
- Find an unpaired number in an array
- Check if a String is a palindrome
- Count binary gap size of a number using tail recursion
- Remove duplicates from a sorted list (Sliding)
- Monitor success rate of a process that may fail
- Least-recently used cache (MRU)
- Find sub-array with the maximum sum
- Find the minimum absolute difference of two partitions
- Find maximum potential profit from an array of stock price
- Fibonacci in purely functional immutable Scala
- Fizz Buzz in purely functional immutable Scala
- Find triplets that sum to a target ('3Sum')
- Find combinations adding up to N (non-unique)
- Find the minimum item in a rotated sorted array
- Make a binary search tree (Red-Black tree)
- Remove duplicates from an unsorted List
- Mars Rover
- Find combinations adding up to N (unique)
- Find indices of tuples that sum to a target (Two Sum)
- Count factors/divisors of an integer
- Compute single-digit sum of digits
- Fixed Window Rate Limiter
- Traverse a tree Depth-First
- Reverse bits of an integer
- Find k closest elements to a value in a sorted Array
- QuickSelect Selection Algorithm (kth smallest item/order statistic)
- Rotate a matrix by 90 degrees clockwise

To save you going through various tutorials, we cherry-picked the most useful Scala concepts in a consistent form.

- Class Inside Class
- Class Inside Def
- Collect
- Def Inside Def
- Drop, Take, dropRight, takeRight
- foldLeft and foldRight
- For-comprehension
- Lazy List
- Option Type
- Ordering
- Partial Function
- Pattern Matching
- Range
- scanLeft and scanRight
- Sliding / Sliding Window
- Stack Safety
- State machine
- Tail Recursion
- Type Class
- View
- Zip

- A description/goal of the algorithm.
- An explanation with both Scala and logical parts.
- A proof or a derivation, where appropriate.
- Links to Scala concepts used in this specific algorithm, also unit-tested.
- An implementation in pure-functional immutable Scala, with efficiency in mind (for most algorithms, this is for paid subscribers only).
- Unit tests, with a button to run them immediately in our in-browser IDE.