Skip to content
Tutorials Center
My learning

Topics

Lesson 145 of 146 ยท Practice

Practice Problems: Algorithms in Swift

Twelve interview-style algorithm exercises in Swift with hints, full solutions and complexity notes: arrays, strings, hashing, two pointers, recursion, sorting and grids.

Reading about algorithms and writing them are different skills. This lesson gives you twelve exercises of the kind that appear in interviews and coding screens, grouped by technique. Each one has a task, a hint, and a complete solution that you can run, change and break.

Work like this: read the task, close your eyes on the solution, and try to write your own version in the editor first. Only open the hint when you are stuck for a few minutes. The solutions are written for clarity in Swift 6 and use the standard library only. Background for the techniques lives in array algorithms, dictionary patterns, recursion, sort details and text processing.

In an interview, say the brute-force idea first, state its cost, then improve it. A correct slow answer that you can explain beats a clever answer you cannot.

Arrays and hashing

Problem 1: Two sum

Given an array of integers and a target, return the indices of two different elements that add up to the target, or nil if there are none.

Hint: for each number you need target - number. A dictionary from value to index lets you check in constant time whether you have seen it.

Problem 2: Contains duplicate within distance k

Return true if the array contains two equal values whose indices differ by at most k.

Hint: keep the last index at which each value was seen.

Problem 3: Maximum subarray sum

Find the largest sum of a non-empty contiguous slice of the array.

Hint: at each element decide whether to extend the running slice or start a new one (Kadane's algorithm).

Swift Solutions 1 to 3

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with readLine()), it gets the next line from this box.

Notes on problem 1: the lookup happens before the insert, so an element is never paired with itself, yet [3, 3] with target 6 still works. In problem 3, the all-negative case is why you must start from the first element and not from zero.

Strings

Problem 4: Valid anagram

Two strings are anagrams if they use the same characters the same number of times. Decide whether they are, ignoring case and spaces.

Hint: count characters with a dictionary, or compare sorted arrays when speed does not matter.

Problem 5: Longest substring without repeating characters

Return the length of the longest stretch of a string with all-distinct characters.

Hint: sliding window. Move the right edge; when you see a repeat, move the left edge past the previous occurrence.

Problem 6: Run-length encoding

Compress "aaabccdddd" into "a3b1c2d4" and decode it back.

Hint: walk the string once, and compare each character with the previous one.

Swift Solutions 4 to 6

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with readLine()), it gets the next line from this box.

Notes: working on Array(text) avoids repeated String.Index arithmetic (see strings). In problem 5, the check previous >= left matters: an old occurrence that is already outside the window must be ignored.

Two pointers and sorting

Problem 7: Merge two sorted arrays

Merge two sorted arrays into one sorted array without calling sort.

Hint: keep one index per array and always take the smaller front element.

Problem 8: Merge intervals

Given a list of closed intervals, merge all that overlap: [1,3], [2,6], [8,10], [15,18] becomes [1,6], [8,10], [15,18].

Hint: sort by start. Then each interval either overlaps the last merged one (extend its end) or starts a new one.

Swift Solutions 7 and 8

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with readLine()), it gets the next line from this box.

In problem 8 the touching intervals [2,6] and [6,7] merge because the comparison is <=. Ask your interviewer whether touching counts as overlapping; that question is part of the exercise.

Recursion and backtracking

Problem 9: Generate all subsets

Return every subset of an array of distinct numbers.

Hint: for each element there are two choices, leave it out or put it in.

Problem 10: Valid parentheses

Given a string made of ()[]{}, decide whether every bracket is closed in the right order.

Hint: a stack. Push openers; on a closer, the top of the stack must be its matching opener.

Swift Solutions 9 and 10

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with readLine()), it gets the next line from this box.

The subset function is a small example of backtracking: make a choice, recurse, then undo the choice so the next branch starts clean.

Grids and counting

Problem 11: Number of islands

A grid of "1" (land) and "0" (water) is given as strings. Count the groups of land cells connected up, down, left or right.

Hint: scan the grid; when you hit unvisited land, count one island and flood-fill all of it so it is not counted again.

Problem 12: Rotate a matrix

Rotate a square matrix 90 degrees clockwise.

Hint: transposing and then reversing each row does the job, and you can do it in place.

Swift Solutions 11 and 12

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with readLine()), it gets the next line from this box.

The inner range (i + 1)..<n visits only the cells above the diagonal, so each pair is swapped once. When i is the last index the range is empty, which is valid in Swift.

Complexity cheat table

Problem Time Extra space
Two sum O(n) O(n)
Nearby duplicate O(n) O(n)
Maximum subarray O(n) O(1)
Anagram O(n) O(1) for a fixed alphabet
Unique substring O(n) O(k)
Run-length encoding O(n) O(n) for the output
Merge sorted O(n + m) O(n + m)
Merge intervals O(n log n) O(n)
Subsets O(n * 2^n) O(n) recursion depth
Brackets O(n) O(n)
Islands O(rows * columns) O(rows * columns) worst case
Rotate matrix O(n^2) O(1)

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Why does the two-sum solution look up target - number before inserting the current number?

    If you inserted first, a number could match its own complement (for example 3 and target 6). Looking first only pairs it with earlier elements.
  2. 2. In Kadane's algorithm, why is the best sum initialized to the first element instead of 0?

    The slice must be non-empty, so the answer for [-5, -2, -9] is -2. Starting from 0 would claim an empty slice.
  3. 3. What is the time complexity of merging intervals, and where does the cost come from?

    The merge pass is linear, but sorting the intervals first dominates at O(n log n).
  4. 4. Why does the island counter overwrite visited land with "0"?

    Flood fill must not visit a cell twice. Turning land into water is a simple visited marker (the function works on a copy, so the caller's data is unchanged).
  5. 5. What is the point of current.removeLast() in the subsets function?

    Backtracking shares one mutable array across branches, so each choice must be undone after its recursive call returns.

Summary

  • Many array and string problems fall to a few patterns: a dictionary for fast lookup, a sliding window, two pointers over sorted data, a stack for nesting and sort-then-sweep.
  • Always state the brute force first, then its cost, then the improvement.
  • Recursion with backtracking explores all choices and undoes each one; flood fill marks visited cells.
  • Check edge cases: empty input, one element, all negative numbers, duplicates and touching intervals.
  • Write down time and space complexity for every solution, as in the table above.

Next: Practice Problems: Protocols and Generics