Codility Mastery

17 Lessons — Complete Guide to 100%

Master all 17 Codility lessons with core techniques, complete C# solutions, and patterns for every problem type. This is the foundation Toptal requires: systematic coverage of iterations, arrays, time complexity, counting, prefix sums, sorting, stacks, leaders, slices, primes, sieves, GCD, Fibonacci, binary search, caterpillar, greedy, and dynamic programming.

17
Lessons
60+
Problems
100%
Complete Solutions
All C#
Optimized Code
All Lessons

Complete Codility Curriculum

Each lesson builds on fundamental algorithms and data structures. Cover them in order; later lessons depend on earlier concepts.

1
Iterations
Binary gap: finding longest sequence of zeros in binary representation

Core Concept

Find the longest sequence of consecutive 0 bits between two 1 bits in a binary representation. Time: O(log N), Space: O(1).

Key Problems

BinaryGap
Given integer N, find longest binary gap
O(log N) time | O(1) space

C# Core Template

csharp 
public int BinaryGap(int N) {
    int maxGap = 0, lastOne = -1;
    for (int i = 0; i < 32; i++) {
        if ((N & (1 << i)) != 0) {
            if (lastOne != -1) {
                maxGap = Math.Max(maxGap, i - lastOne);
            }
            lastOne = i;
        }
    }
    return maxGap;
}

Key Pitfalls

  • Forgetting that N must have at least two 1-bits; return 0 if not
  • Using right-shift and checking LSB instead of checking bit at position i
  • 32-bit overflow; use long if needed for larger numbers
2
Arrays
Array rotation, odd occurrences, and basic array manipulation

Core Concept

Master rotations, odd element detection using XOR, and simple array transformations. Most problems O(N) time, O(1) space.

Key Problems

CyclicRotation
Rotate array right by K positions
O(N) time | O(N) space
OddOccurrencesInArray
Find element appearing odd number of times (rest appear even times)
O(N) time | O(1) space

C# Core Templates

csharp 
// OddOccurrencesInArray — XOR all elements
public int OddOccurrences(int[] A) {
    int result = 0;
    foreach (int x in A) {
        result ^= x;  // XOR cancels pairs
    }
    return result;
}

// CyclicRotation
public int[] CyclicRotation(int[] A, int K) {
    int n = A.Length;
    if (n == 0) return A;
    K = K % n;  // Handle K > N
    int[] result = new int[n];
    for (int i = 0; i < n; i++) {
        result[(i + K) % n] = A[i];
    }
    return result;
}

Key Pitfalls

  • Rotation: forgetting to handle K > N with modulo
  • OddOccurrences: XOR properties (a^a=0, a^0=a, commutative)
  • Empty arrays: always check length before operations
3
Time Complexity
Frog jumps, missing elements, tape equilibrium — O(N) vs O(N²)

Core Concept

Recognize when naive O(N²) approaches fail and switch to O(N) single-pass or prefix/suffix techniques.

Key Problems

FrogJmp
Minimum jumps to reach distance D, jump size J
O(1) time | O(1) space
PermMissingElem
Find missing element in array [1..N+1]
O(N) time | O(1) space
TapeEquilibrium
Minimize difference between left and right sums at split point
O(N) time | O(1) space

C# Solutions

csharp 
// FrogJmp
public int FrogJmp(int X, int Y, int D) {
    return ((int)Math.Ceiling((double)(Y - X) / D));
}

// PermMissingElem — XOR or math approach
public int PermMissing(int[] A) {
    long n = A.Length + 1;
    long expectedSum = n * (n + 1) / 2;
    long actualSum = 0;
    foreach (int x in A) actualSum += x;
    return (int)(expectedSum - actualSum);
}

// TapeEquilibrium — single pass prefix sum
public int TapeEquilibrium(int[] A) {
    long totalSum = 0;
    foreach (int x in A) totalSum += x;
    long leftSum = 0, minDiff = long.MaxValue;
    for (int i = 0; i < A.Length - 1; i++) {
        leftSum += A[i];
        long rightSum = totalSum - leftSum;
        minDiff = Math.Min(minDiff, Math.Abs(leftSum - rightSum));
    }
    return (int)minDiff;
}

Key Pitfalls

  • FrogJmp: integer division truncates; use Math.Ceiling and cast properly
  • PermMissing: sums can overflow; use long for intermediate calculations
  • TapeEquilibrium: split at N-1 positions; test first and last
4
Counting Elements
Frog river one, perm check, max counters, missing integer

Core Concept

Use arrays or sets to count occurrences and track membership. Efficient detection of missing/duplicate elements.

Key Problems

FrogRiverOne
Find earliest second when frog reaches position X (needs all leaves [1..X])
O(N) time | O(X) space
PermCheck
Check if array is permutation of [1..N]
O(N) time | O(N) space
MaxCounters
Process increment/max operations on counters efficiently
O(N+M) time | O(N) space
MissingInteger
Find smallest positive integer not in array
O(N) time | O(N) space

C# Solutions

csharp 
// FrogRiverOne
public int FrogRiverOne(int X, int[] A) {
    var seen = new HashSet<int>();
    for (int i = 0; i < A.Length; i++) {
        if (A[i] <= X) seen.Add(A[i]);
        if (seen.Count == X) return i;
    }
    return -1;
}

// MaxCounters — efficient with lazy reset
public int[] MaxCounters(int N, int[] A) {
    int[] counters = new int[N];
    int maxVal = 0, baseLevel = 0;
    foreach (int op in A) {
        if (op == N + 1) {
            baseLevel = maxVal;  // Lazy reset
        } else {
            counters[op - 1] = Math.Max(counters[op - 1], baseLevel);
            counters[op - 1]++;
            maxVal = Math.Max(maxVal, counters[op - 1]);
        }
    }
    for (int i = 0; i < N; i++) {
        counters[i] = Math.Max(counters[i], baseLevel);
    }
    return counters;
}

// MissingInteger
public int MissingInteger(int[] A) {
    var seen = new HashSet<int>(A);
    for (int i = 1; i <= A.Length + 1; i++) {
        if (!seen.Contains(i)) return i;
    }
    return 1;
}

Key Pitfalls

  • MaxCounters: naive approach resets all (O(N*M)); use lazy reset via baseLevel
  • FrogRiverOne: track count, not individual positions; early exit
  • Handling 1-indexed vs 0-indexed arrays consistently
5
Prefix Sums
Passing cars, genomic range query, min avg two slice, count div

Core Concept

Build prefix arrays to answer range queries in O(1). Handle overflow with long[]. Multiple prefix strategies: cumulative sum, bit flags, modulo.

Key Problems

PassingCars
Count pairs (i, j) where i < j, A[i]=0, A[j]=1 (cars passing)
O(N) time | O(1) space
GenomicRangeQuery
Minimum impact factor in range [L..R] for multiple queries
O(N+M) time | O(4N) space
MinAvgTwoSlice
Find slice with minimum average value
O(N) time | O(N) space
CountDiv
Count integers divisible by K in range [A..B]
O(1) time | O(1) space

C# Solutions

csharp 
// PassingCars
public int PassingCars(int[] A) {
    long result = 0, zeros = 0;
    foreach (int x in A) {
        if (x == 0) zeros++;
        else result += zeros;
        if (result > 1000000000) return -1;
    }
    return (int)result;
}

// CountDiv
public int CountDiv(int A, int B, int K) {
    return (B / K) - ((A - 1) / K);
}

// MinAvgTwoSlice — check slices of length 2 and 3
public int MinAvgTwoSlice(int[] A) {
    double minAvg = double.MaxValue;
    int result = 0;
    for (int i = 0; i < A.Length - 1; i++) {
        double avg2 = (A[i] + A[i + 1]) / 2.0;
        if (avg2 < minAvg) { minAvg = avg2; result = i; }

        if (i < A.Length - 2) {
            double avg3 = (A[i] + A[i + 1] + A[i + 2]) / 3.0;
            if (avg3 < minAvg) { minAvg = avg3; result = i; }
        }
    }
    return result;
}

// GenomicRangeQuery — 4 prefix arrays
public int[] GenomicRangeQuery("string" S, int[] P, int[] Q) {
    int n = S.Length;
    int[][] prefixes = new int[4][];
    for (int k = 0; k < 4; k++) prefixes[k] = new int[n + 1];

    for (int i = 0; i < n; i++) {
        for (int k = 0; k < 4; k++) {
            prefixes[k][i + 1] = prefixes[k][i];
        }
        int idx = S[i] == 'A' ? 0 : S[i] == 'C' ? 1 : S[i] == 'G' ? 2 : 3;
        prefixes[idx][i + 1]++;
    }

    int[] result = new int[P.Length];
    for (int i = 0; i < P.Length; i++) {
        for (int k = 0; k < 4; k++) {
            if (prefixes[k][Q[i] + 1] - prefixes[k][P[i]] > 0) {
                result[i] = k + 1;
                break;
            }
        }
    }
    return result;
}

Key Pitfalls

  • PassingCars: overflow; return -1 if result > 10^9
  • MinAvgTwoSlice: optimal solution always has length 2 or 3 (mathematical property)
  • GenomicRangeQuery: 4 separate prefix arrays for ACGT; find first with count > 0
  • CountDiv: formula (B/K) - (A-1)/K) works for any K and range
6
Sorting
Distinct, max product of three, triangle, number of disc intersections

Core Concept

Leverage sorting to simplify problems. After sort, use two pointers, greedy selection, or binary search.

Key Problems

Distinct
Count distinct elements in array
O(N log N) time | O(N) space
MaxProductOfThree
Find three elements with maximum product
O(N log N) time | O(1) space
Triangle
Check if three elements form valid triangle (P+Q > R)
O(N log N) time | O(1) space
NumberOfDiscIntersections
Count intersecting pairs of discs
O(N log N) time | O(N) space

C# Solutions

csharp 
// Distinct
public int Distinct(int[] A) {
    var set = new HashSet<int>(A);
    return set.Count;
}

// MaxProductOfThree
public int MaxProductOfThree(int[] A) {
    System.Array.Sort(A);
    int n = A.Length;
    // Two cases: largest three or two smallest (negatives) + largest
    return Math.Max(A[n-1] * A[n-2] * A[n-3],
                     A[0] * A[1] * A[n-1]);
}

// Triangle — check all consecutive triples
public int Triangle(int[] A) {
    System.Array.Sort(A);
    for (int i = 0; i < A.Length - 2; i++) {
        if (((long)A[i] + A[i + 1] > A[i + 2])) return 1;
    }
    return 0;
}

// NumberOfDiscIntersections — sweep line
public int NumberOfDiscIntersections(int[] A) {
    int n = A.Length;
    var events = new List<(long, int)>();
    for (int i = 0; i < n; i++) {
        events.Add((((long)i - A[i]), 1));  // left
        events.Add((((long)i + A[i]) + 1, -1));  // right + 1
    }
    events.Sort();
    long count = 0, active = 0;
    foreach (var (pos, delta) in events) {
        count += active * delta;
        active += delta;
    }
    return (int)(count / 2);
}

Key Pitfalls

  • Triangle: need to check consecutive triples after sort (only adjacent need checking)
  • MaxProductOfThree: two smallest negatives might multiply to large positive
  • NumberOfDiscIntersections: sweep line with events; be careful with boundary conditions
  • Overflow when adding indices and radii; use long
7
Stacks and Queues
Brackets, fish, nesting, stone wall — LIFO/FIFO patterns

Core Concept

Use stacks for matching problems, nesting validation, and height processing. Use queues for order-preserving traversal.

Key Problems

Brackets
Validate properly nested brackets
O(N) time | O(N) space
Fish
Count surviving fish (downstream eat upstream if conditions met)
O(N) time | O(N) space
Nesting
Check if array can be nested properly
O(N) time | O(1) space
StoneWall
Minimum blocks to build wall of varying height
O(N) time | O(N) space

C# Solutions

csharp 
// Brackets
public int Brackets("string" S) {
    var stack = new Stack<char>();
    foreach (char c in S) {
        if (c == '(' || c == '[' || c == '{') {
            stack.Push(c);
        } else {
            if (stack.Count == 0) return 0;
            char open = stack.Pop();
            if ((c == ')' && open != '(') ||
                (c == ']' && open != '[') ||
                (c == '}' && open != '{')) {
                return 0;
            }
        }
    }
    return stack.Count == 0 ? 1 : 0;
}

// StoneWall
public int StoneWall(int[] H) {
    var stack = new Stack<int>();
    int blocks = 0;
    foreach (int h in H) {
        while (stack.Count > 0 && stack.Peek() > h) {
            stack.Pop();
        }
        if (stack.Count == 0 || stack.Peek() != h) {
            stack.Push(h);
            blocks++;
        }
    }
    return blocks;
}

// Fish
public int Fish(int[] A, int[] B) {
    var stack = new Stack<int>();
    for (int i = 0; i < A.Length; i++) {
        bool eaten = false;
        while (B[i] == 1 && stack.Count > 0 && B[stack.Peek()] == 0) {
            if (A[stack.Peek()] > A[i]) {
                eaten = true;
                break;
            }
            stack.Pop();
        }
        if (!eaten) stack.Push(i);
    }
    return stack.Count;
}

Key Pitfalls

  • Brackets: empty stack check before pop; all closing brackets must have match
  • StoneWall: stack tracks "open" block heights; merge when possible
  • Fish: B[i]=1 means downstream, B[i]=0 means upstream; only they can collide
8
Leader
Dominator, equileader — find and verify leaders

Core Concept

A leader is an element appearing > N/2 times. Use Boyer-Moore majority vote algorithm (O(N) time, O(1) space).

Key Problems

Dominator
Find index of element appearing > N/2 times
O(N) time | O(1) space
EquiLeader
Count split points where leader is same on both sides with same frequency ratio
O(N) time | O(1) space

C# Solution

csharp 
// Dominator — Boyer-Moore majority vote
public int Dominator(int[] A) {
    int candidate = 0, count = 0;
    for (int i = 0; i < A.Length; i++) {
        if (count == 0) {
            candidate = A[i];
            count = 1;
        } else {
            if (A[i] == candidate) count++;
            else count--;
        }
    }
    // Verify candidate
    count = 0;
    int result = -1;
    for (int i = 0; i < A.Length; i++) {
        if (A[i] == candidate) {
            count++;
            if (result == -1) result = i;
        }
    }
    return count > A.Length / 2 ? result : -1;
}

// EquiLeader
public int EquiLeader(int[] A) {
    // Find global leader
    int candidate = 0, count = 0;
    for (int i = 0; i < A.Length; i++) {
        if (count == 0) { candidate = A[i]; count = 1; }
        else { count = A[i] == candidate ? count + 1 : count - 1; }
    }
    count = 0;
    for (int i = 0; i < A.Length; i++) {
        if (A[i] == candidate) count++;
    }
    if (count <= A.Length / 2) return 0;

    // Count equileader split points
    int result = 0, leftCount = 0;
    for (int i = 0; i < A.Length - 1; i++) {
        if (A[i] == candidate) leftCount++;
        int rightCount = count - leftCount;
        if (leftCount > (i + 1) / 2 && rightCount > (A.Length - i - 1) / 2) {
            result++;
        }
    }
    return result;
}

Key Pitfalls

  • Boyer-Moore: must verify candidate is actually leader (appears > N/2)
  • EquiLeader: exact majority on each side; (i+1)/2 and (N-i-1)/2 floor division
9
Maximum Slice Problem
MaxProfit, MaxSliceSum, MaxDoubleSliceSum — Kadane's algorithm variants

Core Concept

Kadane's algorithm finds max subarray in O(N). Variants: cumulative, double slice (exclude middle element).

Key Problems

MaxProfit
Max profit from buy/sell with price array
O(N) time | O(1) space
MaxSliceSum
Maximum sum contiguous subarray (Kadane)
O(N) time | O(1) space
MaxDoubleSliceSum
Max sum of two non-overlapping slices (exclude one element between)
O(N) time | O(N) space

C# Solutions

csharp 
// MaxProfit
public int MaxProfit(int[] A) {
    int maxProfit = 0, minPrice = A[0];
    for (int i = 1; i < A.Length; i++) {
        maxProfit = Math.Max(maxProfit, A[i] - minPrice);
        minPrice = Math.Min(minPrice, A[i]);
    }
    return maxProfit;
}

// MaxSliceSum — Kadane's algorithm
public int MaxSliceSum(int[] A) {
    int maxEnding = A[0], maxSoFar = A[0];
    for (int i = 1; i < A.Length; i++) {
        maxEnding = Math.Max(A[i], maxEnding + A[i]);
        maxSoFar = Math.Max(maxSoFar, maxEnding);
    }
    return maxSoFar;
}

// MaxDoubleSliceSum
public int MaxDoubleSliceSum(int[] A) {
    int n = A.Length;
    int[] maxLeft = new int[n];   // max ending at i
    int[] maxRight = new int[n];  // max starting at i

    for (int i = 1; i < n - 1; i++) {
        maxLeft[i] = Math.Max(0, maxLeft[i - 1] + A[i]);
    }
    for (int i = n - 2; i >= 1; i--) {
        maxRight[i] = Math.Max(0, maxRight[i + 1] + A[i]);
    }

    int result = 0;
    for (int i = 1; i < n - 1; i++) {
        result = Math.Max(result, maxLeft[i] + maxRight[i + 1]);
    }
    return result;
}

Key Pitfalls

  • MaxSliceSum: Kadane's handles negative numbers; initialize with A[0]
  • MaxDoubleSliceSum: slice cannot be empty; use Math.Max(0, ...) to allow zero-sum
  • Must exclude middle element between slices; two separate forward/backward passes
10
Prime and Composite Numbers
Factor counting, rectangle perimeter, flags, peaks — efficient integer factorization

Core Concept

Factor a number up to sqrt(N) in O(sqrt(N)). Iterate divisors only up to sqrt.

Key Problems

CountFactors
Count all divisors of N
O(sqrt N) time | O(1) space
MinPerimeterRectangle
Rectangle with area N, minimum perimeter
O(sqrt N) time | O(1) space
Flags
Max flags on peaks with min distance between them
O(N) time | O(N) space
Peaks
Divide array into blocks with equal peaks per block
O(N) time | O(N) space

C# Solutions

csharp 
// CountFactors
public int CountFactors(int N) {
    int count = 0;
    for (int i = 1; i * i <= N; i++) {
        if (N % i == 0) {
            count += (i * i == N) ? 1 : 2;
        }
    }
    return count;
}

// MinPerimeterRectangle
public int MinPerimeterRectangle(int N) {
    int minPerim = int.MaxValue;
    for (int i = 1; i * i <= N; i++) {
        if (N % i == 0) {
            int j = N / i;
            minPerim = Math.Min(minPerim, 2 * (i + j));
        }
    }
    return minPerim;
}

// Flags — binary search on answer
public int Flags(int[] A) {
    // Find all peaks
    var peaks = new List<int>();
    for (int i = 1; i < A.Length - 1; i++) {
        if (A[i] > A[i-1] && A[i] > A[i+1]) {
            peaks.Add(i);
        }
    }
    if (peaks.Count == 0) return 0;

    // Binary search on number of flags
    int left = 1, right = peaks.Count, ans = 0;
    while (left <= right) {
        int mid = (left + right) / 2;
        if (CanPlace(peaks, mid)) {
            ans = mid;
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return ans;
}

bool CanPlace(List<int> peaks, int numFlags) {
    int placed = 1, lastPos = peaks[0];
    for (int i = 1; i < peaks.Count; i++) {
        if (peaks[i] - lastPos >= 2 * numFlags) {
            placed++;
            lastPos = peaks[i];
        }
    }
    return placed >= numFlags;
}

Key Pitfalls

  • CountFactors: if i*i == N, count once; otherwise count i and N/i
  • Flags: binary search on answer; greedy placement when possible
  • Peaks: array indexing; peaks must have at least one element on each side
11
Sieve of Eratosthenes
Count semiprimes, count non-divisible — efficient prime sieve applications

Core Concept

Sieve finds all primes up to N in O(N log log N). Use for factorization tasks and prime-based queries.

Key Problems

CountSemiprimes
Count numbers in [L..R] that are product of exactly two primes
O(N log log N + M) time | O(N) space
CountNonDivisible
For each element, count array elements it doesn't divide
O(N sqrt N) time | O(N) space

C# Solutions

csharp 
// CountSemiprimes
public int[] CountSemiprimes(int N, int[] P, int[] Q) {
    // Find smallest prime factor for each number
    int[] spf = new int[N + 1];
    for (int i = 0; i <= N; i++) spf[i] = i;

    for (int i = 2; i * i <= N; i++) {
        if (spf[i] == i) {  // i is prime
            for (int j = i * i; j <= N; j += i) {
                if (spf[j] == j) spf[j] = i;
            }
        }
    }

    // Check if each number is semiprime
    bool[] isSemi = new bool[N + 1];
    for (int i = 4; i <= N; i++) {
        int num = i, factors = 0;
        while (num > 1) {
            int p = spf[num];
            factors++;
            num /= p;
        }
        isSemi[i] = (factors == 2);
    }

    // Build prefix sum
    int[] prefix = new int[N + 1];
    for (int i = 1; i <= N; i++) {
        prefix[i] = prefix[i - 1] + (isSemi[i] ? 1 : 0);
    }

    int[] ans = new int[P.Length];
    for (int i = 0; i < P.Length; i++) {
        ans[i] = prefix[Q[i]] - prefix[P[i] - 1];
    }
    return ans;
}

// CountNonDivisible
public int[] CountNonDivisible(int[] A) {
    int maxVal = int.MinValue;
    foreach (int x in A) maxVal = Math.Max(maxVal, x);

    int[] freq = new int[maxVal + 1];
    foreach (int x in A) freq[x]++;

    int[] ans = new int[A.Length];
    for (int i = 0; i < A.Length; i++) {
        int divisors = 0;
        for (int d = 1; d * d <= A[i]; d++) {
            if (A[i] % d == 0) {
                divisors += freq[d];
                if (d * d != A[i]) divisors += freq[A[i] / d];
            }
        }
        ans[i] = A.Length - divisors;
    }
    return ans;
}

Key Pitfalls

  • CountSemiprimes: semiprime has exactly 2 prime factors (not distinct); count with multiplicity
  • Smallest Prime Factor (SPF) sieve; use spf to factorize quickly
  • CountNonDivisible: iterate divisors of A[i], not all numbers
12
Euclidean Algorithm
GCD, chocolates, common prime divisors — modular arithmetic

Core Concept

GCD(a, b) = GCD(b, a mod b). Efficient for finding greatest common divisor and LCM.

Key Problems

ChocolatesByNumbers
Distribute chocolates in circle, step size S. Count distribution points.
O(log min(N, S)) time | O(1) space
CommonPrimeDivisors
Check if GCD of each pair equals 1 after removing common divisors
O(log min(A[i], B[i])) per pair

C# Solutions

csharp 
// Euclidean GCD
long GCD(long a, long b) {
    while (b != 0) {
        long temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

// ChocolatesByNumbers
public int ChocolatesByNumbers(int N, int S) {
    // Answer is N / GCD(N, S)
    long g = GCD(N, S);
    return (int)(N / g);
}

// CommonPrimeDivisors
public int CommonPrimeDivisors(int[] A, int[] B) {
    int count = 0;
    for (int i = 0; i < A.Length; i++) {
        long a = A[i], b = B[i];
        long g = GCD(a, b);
        while (a > 1) {
            long p = GCD(a, g);
            if (p == 1) break;
            while (a % p == 0) a /= p;
        }
        if (a == 1) count++;
    }
    return count;
}

Key Pitfalls

  • ChocolatesByNumbers: lcm(N, S) = N*S/gcd(N,S); count = N/gcd
  • CommonPrimeDivisors: check if all prime divisors of A are also in B
13
Fibonacci Numbers
Fib frog, ladder — dynamic programming with Fibonacci

Core Concept

Precompute Fibonacci sequence. Use for counting paths/jumps in O(log N) or O(N) depending on problem.

Key Problems

FibFrog
Minimum jumps to reach position N+1 (can jump Fibonacci distances)
O(N log N) time | O(N) space
Ladder
Count ways to climb ladder (1 or 2 steps, modulo 2^N)
O(N) time | O(N) space

C# Solutions

csharp 
// FibFrog
public int FibFrog(int[] A) {
    var fibs = new List<int>();
    int a = 1, b = 2;
    while (a <= A.Length + 1) {
        fibs.Add(a);
        int temp = a + b;
        a = b;
        b = temp;
    }

    var reachable = new HashSet<int>();
    var queue = new Queue<(int, int)>();  // (position, jumps)
    queue.Enqueue((0, 0));
    reachable.Add(0);

    while (queue.Count > 0) {
        var (pos, jumps) = queue.Dequeue();

        foreach (int fib in fibs) {
            int nextPos = pos + fib;
            if (nextPos == A.Length + 1) return jumps + 1;

            if (nextPos < A.Length && A[nextPos] == 1 && !reachable.Contains(nextPos)) {
                reachable.Add(nextPos);
                queue.Enqueue((nextPos, jumps + 1));
            }
        }
    }
    return -1;
}

// Ladder
public int[] Ladder(int[] A) {
    int maxN = 0;
    foreach (int n in A) maxN = Math.Max(maxN, n);

    long[] dp = new long[maxN + 1];
    dp[0] = 1; dp[1] = 1;
    for (int i = 2; i <= maxN; i++) {
        dp[i] = (dp[i-1] + dp[i-2]) & (((long)1 << 30) - 1);  // mod 2^30
    }

    int[] result = new int[A.Length];
    for (int i = 0; i < A.Length; i++) {
        result[i] = (int)(dp[A[i]] % ((long)1 << A[i]));
    }
    return result;
}

Key Pitfalls

  • FibFrog: BFS from position 0; target is position N+1
  • Ladder: modulo 2^N (not fixed); use bitwise AND to handle dynamic modulo
14
Binary Search
Min max division, nailing planks — binary search on answer

Core Concept

Binary search on answer: check if a value is achievable, narrow bounds.

Key Problems

MinMaxDivision
Divide array into K subarrays, minimize max subarray sum
O(N log(sum)) time | O(N) space
NailingPlanks
Minimum nails to cover all planks (planks are ranges)
O(N log N) time | O(N) space

C# Solutions

csharp 
// MinMaxDivision
public int MinMaxDivision(int K, int M, int[] A) {
    long left = 0, right = 0;
    foreach (int x in A) {
        left = Math.Max(left, x);
        right += x;
    }

    long ans = right;
    while (left <= right) {
        long mid = (left + right) / 2;
        if (CanDivide(A, K, mid)) {
            ans = mid;
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return (int)ans;
}

bool CanDivide(int[] A, int K, long maxSum) {
    int parts = 1;
    long sum = 0;
    foreach (int x in A) {
        if (sum + x > maxSum) {
            parts++;
            sum = x;
            if (parts > K) return false;
        } else {
            sum += x;
        }
    }
    return true;
}

// NailingPlanks
public int NailingPlanks(int[] A, int[] B, int[] C) {
    int left = 0, right = C.Length - 1, ans = -1;
    while (left <= right) {
        int mid = (left + right) / 2;
        if (CanNail(A, B, C, mid)) {
            ans = mid + 1;
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return ans;
}

bool CanNail(int[] A, int[] B, int[] C, int maxIdx) {
    int lastNail = int.MinValue;
    int nIdx = 0;
    for (int i = 0; i < A.Length; i++) {
        // Find a nail covering [A[i], B[i]]
        while (nIdx <= maxIdx && C[nIdx] < A[i]) nIdx++;
        if (nIdx > maxIdx || C[nIdx] > B[i]) return false;
    }
    return true;
}

Key Pitfalls

  • MinMaxDivision: left bound is max single element, not 0
  • NailingPlanks: nails and planks must be sorted; use two pointers after sort
15
Caterpillar Method
AbsDistinct, CountDistinctSlices, CountTriangles, MinAbsSumOfTwo — two pointers on sorted data

Core Concept

Two-pointer technique on sorted arrays. Move left/right pointer based on condition.

Key Problems

AbsDistinct
Count distinct absolute values in array
O(N) time | O(1) space
CountDistinctSlices
Count distinct slices (no repeating elements)
O(N) time | O(N) space
CountTriangles
Count valid triangles from three elements
O(N²) time | O(1) space
MinAbsSumOfTwo
Minimize |A[i] + A[j]| for i != j
O(N log N) time | O(1) space

C# Solutions

csharp 
// AbsDistinct
public int AbsDistinct(int[] A) {
    var set = new HashSet<int>();
    foreach (int x in A) {
        set.Add(Math.Abs(x));
    }
    return set.Count;
}

// CountDistinctSlices
public int CountDistinctSlices(int M, int[] A) {
    long count = 0;
    int left = 0;
    var seen = new Dictionary<int, int>();

    for (int right = 0; right < A.Length; right++) {
        if (seen.ContainsKey(A[right])) {
            left = Math.Max(left, seen[A[right]] + 1);
        }
        seen[A[right]] = right;
        count += (right - left + 1);
    }
    return (int)Math.Min(count, 1000000000);
}

// CountTriangles
public int CountTriangles(int[] A) {
    System.Array.Sort(A);
    int count = 0;
    for (int i = A.Length - 1; i >= 2; i--) {
        int left = 0, right = i - 1;
        while (left < right) {
            if (((long)A[left] + A[right] > A[i])) {
                count += right - left;
                right--;
            } else {
                left++;
            }
        }
    }
    return count;
}

// MinAbsSumOfTwo
public int MinAbsSumOfTwo(int[] A) {
    System.Array.Sort(A);
    int minAbs = int.MaxValue;
    int left = 0, right = A.Length - 1;

    while (left < right) {
        int sum = A[left] + A[right];
        minAbs = Math.Min(minAbs, Math.Abs(sum));

        if (sum < 0) {
            left++;
        } else {
            right--;
        }
    }
    return minAbs;
}

Key Pitfalls

  • CountDistinctSlices: overflow; cap at 10^9
  • CountTriangles: must check P+Q > R; move pointers based on condition
  • MinAbsSumOfTwo: sum can be negative; track absolute value
16
Greedy Algorithms
Tie ropes, max non-overlapping segments — optimal local choices

Core Concept

Greedy approach: make locally optimal choice at each step. Prove correctness or test thoroughly.

Key Problems

TieRopes
Maximum number of knots combining ropes of minimum length K
O(N) time | O(1) space
MaxNonoverlappingSegments
Maximum non-overlapping segments from list of ranges
O(N log N) time | O(1) space

C# Solutions

csharp 
// TieRopes
public int TieRopes(int K, int[] A) {
    int knots = 0, sum = 0;
    foreach (int length in A) {
        sum += length;
        if (sum >= K) {
            knots++;
            sum = 0;
        }
    }
    return knots;
}

// MaxNonoverlappingSegments
public int MaxNonoverlappingSegments(int[] A, int[] B) {
    // Pair and sort by end point
    var segs = new List<(int, int)>();
    for (int i = 0; i < A.Length; i++) {
        segs.Add((A[i], B[i]));
    }
    segs.Sort((a, b) => a.Item2.CompareTo(b.Item2));

    int count = 0, lastEnd = int.MinValue;
    foreach (var (start, end) in segs) {
        if (start > lastEnd) {
            count++;
            lastEnd = end;
        }
    }
    return count;
}

Key Pitfalls

  • TieRopes: greedy works—combine greedily as soon as sum >= K
  • MaxNonoverlappingSegments: sort by end point, not start; earliest finish first
17
Dynamic Programming
Number solitaire, min abs sum — DP on decision/value spaces

Core Concept

Overlapping subproblems + optimal substructure = DP. Memoization or bottom-up tabulation.

Key Problems

NumberSolitaire
Maximize final score jumping 1-6 steps at a time
O(N) time | O(N) space
MinAbsSum
Partition array into +/- groups, minimize absolute sum
O(N * sum) time | O(N * sum) space

C# Solutions

csharp 
// NumberSolitaire
public int NumberSolitaire(int[] A) {
    int[] dp = new int[A.Length];
    dp[0] = A[0];

    for (int i = 1; i < A.Length; i++) {
        dp[i] = int.MinValue;
        for (int j = 1; j <= 6 && i - j >= 0; j++) {
            dp[i] = Math.Max(dp[i], dp[i - j] + A[i]);
        }
    }
    return dp[A.Length - 1];
}

// MinAbsSum
public int MinAbsSum(int[] A) {
    long sum = 0;
    foreach (int x in A) sum += Math.Abs(x);

    long target = sum / 2;
    var dp = new bool[target + 1];
    dp[0] = true;

    foreach (int x in A) {
        int absX = Math.Abs(x);
        for (long j = target; j >= absX; j--) {
            dp[j] = dp[j] || dp[j - absX];
        }
    }

    for (long i = target; i >= 0; i--) {
        if (dp[i]) {
            return (int)(sum - 2 * i);
        }
    }
    return 0;
}

Key Pitfalls

  • NumberSolitaire: dp[i] = max(dp[i-1..i-6]) + A[i]; boundary check
  • MinAbsSum: partition into two groups minimizing |S1 - S2|; 0/1 knapsack variant
  • Work backwards in inner loop for MinAbsSum (avoid using updated values)
Track

Completion Checklist — 100% Mastery

Check off each lesson as you complete all problems with full solutions and deep understanding.

All 17 Lessons

✓
Mastery Strategy: Work through lessons sequentially. For each, code the solutions from scratch without references. Test edge cases, understand time/space complexity, and explain the algorithm aloud. When all 17 checkboxes are ticked and you can code each problem in <5 minutes, you are ready for Toptal's technical screening.