# foldLeft and foldRight, a Scala language concept

Last updated

A 'fold' allows you to perform the equivalent of a for-loop, but with a lot less code.

Last updated

A 'fold' allows you to perform the equivalent of a for-loop, but with a lot less code.

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

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
- Print a binary tree
- Remove duplicates from an unsorted List
- 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
- Check word in grid (depth-first search)
- Maximum wait at a fuel station
- Find minimum missing positive number in a sequence
- Least-recently used cache (LRU)
- Count pairs of a given expected sum
- Binary heap (min-heap)
- 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
- Check word in grid (stack-safe)
- Leaky Bucket Rate Limiter
- Merge Sort: stack-safe, tail-recursive, in pure immutable Scala, N-way
- Median of two sorted arrays
- 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 an efficient foldLeft
- Count passing cars
- Count dist intersections
- 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
- Merge intervals
- Compute minimum number of Fibonacci numbers to reach sum
- Find the longest palindrome within a string
- 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)
- 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
- Check Sudoku board
- Find k closest elements to a value in a sorted Array
- Print a binary tree vertically
- 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
- Variance
- View
- Zip

Maximize your Scala with disciplined and consistently unit-tested solutions to 100+ algorithms.

Use it from improving your day-to-day data structures and Scala; all the way to interviewing.