A factorial, in mathematics, is the product of all positive integers from 1 up to a given number. It's written using an exclamation point.

This lecture explains the time complexity and space complexity of the factorial function.

A clear breakdown of confusing aspects of the factorial function.

This lecture is a clear and simple way of re-iterating and understanding what time and space complexity is.

Problem Statement:

Write a Swift function named sumOfEveryKthNumber that takes three parameters:

• start: an Int — the starting number of the range

• end: an Int — the end of the range (exclusive)

• step: an Int — the step value

The function should:

• Use a for-in loop and stride(from:to:by:)

• Return the sum of all numbers between start (inclusive) and end (exclusive) stepping by step

When the Difference Matters

For small ranges (e.g., stride from 0 to 10), the performance difference is negligible.

But for large ranges (e.g., stride from 0 to 1,000,000), the arithmetic version is dramatically faster — because it doesn’t loop at all.

Coding Challenge: Evenly Spaced Markers

Problem Statement:

Write a Swift function called generateMarkers that:

• Accepts a total length (an Int) and a number of steps (an Int)

• Returns an array of marker positions as evenly spaced Int values

• Uses stride to generate the marker positions

Problem Statement:

Write a function called countMultiples that:

• Takes three parameters:

  • start: an Int (inclusive)

  • end: an Int (exclusive)

  • multipleOf: an Int

• Returns the number of integers between start and end that are divisible by multipleOf

• Uses stride and a for-in loop to solve the problem

Time Complexity for the 1st Solution: O(n)

(where n = maxStep)

Why?

In this loop:

for step in stride(from: maxStep, through: 1, by: -1) {

    let testStride = Array(stride(from: 0, to: rangeLimit, by: step))

    if let final = testStride.last, final == rangeLimit - step {

        return step

    }

}

• You’re iterating from maxStep down to 1 → O(maxStep) iterations

• In each iteration, you build an array using stride(...) → cost depends on rangeLimit / step

• In the worst case, building the array could approach O(rangeLimit / step), and over multiple steps, that can add up

So while each stride doesn't touch every value (due to stepping), the cumulative cost across steps still leads to linear time complexity in relation to maxStep.

Overall:

• Time complexity: O(maxStep + rangeLimit / minValidStep) — dominated by maxStep

• Space complexity: Worst case O(rangeLimit / step) for each array creation

Time Complexity for the 2nd Solution: O(1)

How It Works

This replaces:

Array(stride(from: 0, to: rangeLimit, by: step)).last

with:

((rangeLimit - 1) / step) * step

That expression gives the largest number less than rangeLimit that’s divisible by step.

Then we check if that number is equal to rangeLimit - step, which is the condition we’re looking for.

Example:

let result = largestDivisibleStep(rangeLimit: 12, maxStep: 5)

print(result ?? "No valid step") // Output: 4

Complexity

• Time complexity: O(maxStep) (still iterating steps, but each step is O(1))

• Space complexity: O(1) — no arrays, no sequences, no dynamic allocations

Write a Swift function named filteredMultiples that:

• Accepts three parameters:

  • start: an Int (inclusive)

  • end: an Int (exclusive)

  • multipleOf: an Int

• Returns an array of all numbers in the range [start, end) that are:

  1. Divisible by multipleOf

  2. Not divisible by 2 or 5

The solution is O(n) (linear time). A truly O(1) solution would not loop at all — it would use math only, such as computing counts or patterns directly. But since you're returning an array of values (which grows with input), the function must scale at least linearly with the output size.

Thus, the best possible complexity in this case is O(k), where k is the number of valid values that will be returned.

Write a Swift function called alternatingStepSum that:

• Takes three parameters:

  • start: an Int (inclusive)

  • end: an Int (exclusive)

  • step: an Int > 0

• Iterates through the range [start, end) using stride(from:to:by:)

• Alternates between adding and subtracting each value

• Returns the final result

Here’s how we can build an O(1) version of alternatingStepSum using a mathematical formula — but note that it only works cleanly when the pattern is predictable, like when you're summing evenly spaced numbers with alternating signs.

Coding Challenge: Max Sum in Sliding Window

Problem Statement:

Write a function called maxSlidingWindowSum that:

• Takes two parameters:

  • numbers: an array of Int

  • windowSize: an Int > 0

• Returns the maximum sum of any contiguous subarray of size windowSize

• Uses a for-in loop (not reduce or recursion)

• Must run in O(n) time

Time Complexity Analysis

What the function does:

It examines every element in the array at least once to:

• Initialize the first window

• Slide the window forward

• Update the sum by subtracting the outgoing value and adding the incoming one

Even with the optimized sliding window technique, you're still performing O(n) total operations, where n = numbers.count.

Could You Do It in O(1)?

Only if:

• You already had precomputed auxiliary data (like a prefilled array of window sums)

• Or you weren’t sliding the window — i.e., you were just summing one fixed subarray

But in the general case, where you’re asked to compute the max sum over all possible windows of size k, you must examine O(n) elements to ensure the result is correct.

Problem Statement:

You are given an array of n distinct integers from the range 0...n. That means the array contains all numbers from 0 to n, except one number is missing.

Write a function that returns the missing number.

Coding Challenge: First Duplicate Element

Problem Statement:

Write a function called firstDuplicate that:

• Takes an array of integers

• Returns the first duplicate number in the array based on its first reappearance

• If there is no duplicate, return nil

Smallest Subarray with Given Sum

Problem Statement:

Write a function called smallestSubarrayLength that:

• Takes two parameters:

  • target: an Int representing the desired sum

  • numbers: an array of positive integers

• Returns the length of the smallest contiguous subarray whose sum is greater than or equal to target

• Returns 0 if no such subarray exists

Swift Benchmarking Utility

This function allows you to observe how a function's execution time scales with input size. It helps you estimate time complexity by measuring how long a function takes for various input sizes.