learning/swift-dsa

DSA

If the input array is sorted then: use Binary search or Two pointers patterns/technique.
If asked for all permutations or subsets then use the Backtracking technique.
If given a tree then use DFS or BFS.
If given a graph then use DFS or BFS.
If given a linked list then use the Two Pointers technique with probably the Fast/Slot Pointers technique.
If recursion is banned then use a Stack.
If must solve in-place then you can Swap corresponding values or Store one or more different values in the same pointer.
If asked for maximum/minimum subarray/subset/options then Dynamic programming.
If asked for top/least K items then Heap or QuickSelect algorithms.
If asked for common strings then Dictionaries and Trie data structures.
 

And if none of the above helps you… Always remember Dictionary or Set for O(1) time & O(n) space and Sort the input for O(nlogn) time O(1) space.

Top problems Leetcode Patterns #weblinks

Knowing What to Track

Hash Maps

Tree DFS, BFS, Trie

Stacks

Cyclic, Topological sort

Dynamic Programming

Backtracking

Greedy techniques

K-way Merge

Top K Elements

Union Find

Here is some sample Swift code that you can use to count the number of islands in a 2D binary grid:

func countIslands(grid: [[Int]]) -> Int {
    // Create a copy of the grid to mark visited cells
    var grid = grid
    var count = 0

    // Iterate over all cells in the grid
    for i in 0..<grid.count {
        for j in 0..<grid[i].count {
            // If the cell is land and has not been visited yet,
            // it is part of a new island
            if grid[i][j] == 1 {
                count += 1
                // Mark all cells in the island as visited
                markIsland(grid: &grid, i: i, j: j)
            }
        }
    }

    return count
}

func markIsland(grid: inout [[Int]], i: Int, j: Int) {
    // Check if the indices are within the bounds of the grid
    // and if the cell is land
    if i >= 0 && i < grid.count && j >= 0 && j < grid[i].count && grid[i][j] == 1 {
        // Mark the cell as visited
        grid[i][j] = 0
        // Mark all adjacent cells as visited
        markIsland(grid: &grid, i: i-1, j: j)
        markIsland(grid: &grid, i: i+1, j: j)
        markIsland(grid: &grid, i: i, j: j-1)
        markIsland(grid: &grid, i: i, j: j+1)
    }
}

let grid = [[1, 1, 0, 0, 0],
            [1, 1, 0, 0, 0],
            [0, 0, 1, 0, 0],
            [0, 0, 0, 1, 1]]

let count = countIslands(grid: grid)
print(count) // Outputs: 3

This code uses a depth-first search algorithm to identify and mark all cells in an island as visited. It then counts the number of times it had to start a new search, which corresponds to the number of islands in the grid.

Modified Binary Search

Subsets - Permutations, Combinations

Two Heaps

https://www.educative.io/courses/grokking-coding-interview-patterns-java/3w0npwNBAkO
- As the name suggests, the two heaps pattern uses either two min-heaps, two max-heaps, or a min-heap and a max-heap simultaneously to solve the problem.
- A min-heap is used to find the smallest element of a set of data, and a max-heap is used to find the largest element. Both heaps take O(log⁡k)O(logk) time to insert an element, O(log⁡k)O(logk) time to pop an element, and give O(1)O(1) time access to the smallest or largest element.
- In some problems, we’re given a set of data such that it can be divided into two parts. We can either use the first part to find the smallest element using the min-heap and the second part to find the largest element using the max-heap, or we can do the reverse and use the first part to find the largest element using the max-heap and the second part to find the smallest element using the min-heap.
- There might be cases where we need to find the two largest numbers from two different data sets. We’ll use two max-heaps to store two different data sets in that case. In other cases, we might need to find the two smallest numbers from two different data sets, and then we would use two min-heaps.

+ 

+

Reverse Linked List

Given the head of a singly linked list, reverse the linked list and return its updated head.

class ListNode {
    var val: Int
    var next: ListNode?
    
    init(val: Int, next: ListNode?) {
        self.val = val
        self.next = next
    }
}

func reverseList(head: ListNode?) -> ListNode? {
    var prev: ListNode? = nil
    var current: ListNode? = head
    var next: ListNode? = head?.next
    
    // reverse the linked list using the three pointers
    while current != nil {
        current?.next = prev
        prev = current
        current = next
        next = next?.next
    }
    
    return prev
}

let head = ListNode(val: 1, next: ListNode(val: 2, next: ListNode(val: 3, next: nil)))
let reversedHead = reverseList(head: head)

Merge Intervals

We’re given an array of closed intervals as input where each interval has a start and end timestamp. The input array is sorted by starting timestamps. Merge the overlapping intervals and return a new output array.

struct Interval {
    var start: Int
    var end: Int
}

func mergeIntervals(intervals: [Interval]) -> [Interval] {
    var result: [Interval] = []
    
    // sort the intervals by start timestamps
    let sortedIntervals = intervals.sorted { $0.start < $1.start }
    
    var current = sortedIntervals[0]
    for i in 1..<sortedIntervals.count {
        let interval = sortedIntervals[i]
        
        // if the current interval overlaps with the next interval, merge them
        if interval.start <= current.end {
            current = Interval(start: current.start, end: max(current.end, interval.end))
        } else {
            // if the intervals don't overlap, add the current interval to the result and start a new interval
            result.append(current)
            current = interval
        }
    }
    
    // add the last interval to the result
    result.append(current)
    
    return result
}

let intervals = [
    Interval(start: 1, end: 5),
    Interval(start: 3, end: 8),
    Interval(start: 4, end: 10),
    Interval(start: 10, end: 12)
]
let mergedIntervals = mergeIntervals(intervals: intervals)

Fast, Slow Pointers

Here is a solution in Swift that checks if a linked list contains a cycle or not:

class ListNode {
    var val: Int
    var next: ListNode?
    
    init(val: Int, next: ListNode?) {
        self.val = val
        self.next = next
    }
}

func hasCycle(head: ListNode?) -> Bool {
    var slow: ListNode? = head
    var fast: ListNode? = head
    
    // use a slow and fast pointer to detect cycles
    while fast != nil && fast?.next != nil {
        slow = slow?.next
        fast = fast?.next?.next
        
        if slow === fast {
            return true
        }
    }
    
    return false
}

let head = ListNode(val: 1, next: ListNode(val: 2, next: nil))
let result = hasCycle(head: head)

A "happy number" is a number that follows a sequence that ends in 1 after following the steps below:

Replace the number with the sum of the squares of its digits.
Repeat this process until the number equals 1 or enters an infinite loop.
Here is a solution in Swift that determines if a number n is a happy number:

func isHappy(n: Int) -> Bool {
    var slow = n
    var fast = n
    
    // use a slow and fast pointer to detect infinite loops
    while fast != 1 {
        slow = calcSquares(n: slow)
        fast = calcSquares(n: calcSquares(n: fast))
        
        // if the slow and fast pointers meet, it means there is an infinite loop
        if slow == fast {
            return false
        }
    }
    
    return true
}

func calcSquares(n: Int) -> Int {
    var sum = 0
    var num = n
    
    // sum the squares of the digits of the number
    while num > 0 {
        let digit = num % 10
        sum += digit * digit
        num /= 10
    }
    
    return sum
}

Two Pointers

Write a function that takes a string as input and checks whether it can be a valid palindrome by removing at most one character from it.

Here is a solution in Swift that reverses the order of the words in a given sentence without affecting the order of letters within each word:

func reverseWords(sentence: String) -> String {
    // split the sentence into an array of words
    let words = sentence.split(separator: " ")
    
    // reverse the order of the words
    let reversedWords = words.reversed()
    
    // join the reversed words into a single string
    return reversedWords.joined(separator: " ")
}

Here is a solution in Swift that checks if there are any three integers in the `nums` array whose sum equals the target `target`:

func threeSum(nums: [Int], target: Int) -> Bool {
    let n = nums.count
    if n < 3 {
        return false
    }
    
    // sort the array
    let sortedNums = nums.sorted()
    
    for i in 0..<n-2 {
        // check if the current number is greater than the target,
        // if it is, there is no need to continue the loop
        if sortedNums[i] > target {
            break
        }
        
        // initialize the left and right pointers
        var left = i + 1
        var right = n - 1
        
        // find the two numbers that sum to the target
        while left < right {
            let sum = sortedNums[i] + sortedNums[left] + sortedNums[right]
            if sum == target {
                return true
            } else if sum < target {
                left += 1
            } else {
                right -= 1
            }
        }
    }
    
    return false
}

Problem: Determine if a string is a permutation of another string

func isPermutation(string1: String, string2: String) -> Bool {
  // Check if the strings have different lengths
  if string1.count != string2.count {
    return false
  }

  // Create an array of integers to store the frequency of each character in the strings
  var frequency = [Int](repeating: 0, count: 256)

  // Increment the frequency of each character in string1
  for character in string1 {
    let charInt = Int(character.asciiValue!)
    frequency[charInt] += 1
  }

  // Decrement the frequency of each character in string2
  for character in string2 {
    let charInt = Int(character.asciiValue!)
    frequency[charInt] -= 1
  }

  // Check if the frequency array contains only zeros
  for count in frequency {
    if count != 0 {
      return false
    }
  }

  return true
}

let string1 = "abcdefg"
let string2 = "gfedcba"

if isPermutation(string1: string1, string2: string2) {
  print("The strings are permutations of each other.")
} else {
  print("The strings are not permutations of each other.")
}

Sliding Window

Data Structures

Arrays
- Array — SwiftDoc.org #weblinks
- Exploring Swift Array’s Implementation – ankit.im #weblinks
- Explain all the operations, tips and tricks in Swift arrays to ace leetcode algorithms coding questions

Initialization: You can create an empty array by using the initializer syntax []. For example: var numbers = [Int]() You can also create an array with a default value by using the Array(repeating:value, count:Int) initializer. For example: var numbers = Array(repeating: 0, count: 5) will create an array of 5 elements, all initialized to 0.

Accessing elements: You can access the elements of an array using subscript syntax. For example: let firstNumber = numbers[0] will retrieve the first element of the numbers array. You can also use the first and last properties to access the first and last elements of the array, respectively. Modifying elements: You can modify the elements of an array by using subscript syntax. For example: numbers[0] = 10 will set the first element of the numbers array to 10. You can also use the append(_:) method to add a new element to the end of the array. Iteration: You can use a for-in loop to iterate over the elements of an array. For example:

for number in numbers {
    print(number)
}

Sorting: You can use the sorted() method to return a new array that is sorted in ascending order. You can also pass a closure to the sorted() method to specify a custom sort order. For example:

let sortedNumbers = numbers.sorted { $0 > $1 }

Filtering: You can use the filter(_:) method to return a new array that contains only the elements that match a certain condition. For example:

let evenNumbers = numbers.filter { $0 % 2 == 0 }

Transforming: You can use the map(_:) method to transform the elements of an array and return a new array. For example:

let doubledNumbers = numbers.map { $0 * 2 }

Reducing: You can use the reduce(::) method to combine the elements of an array and return a single value. For example:

let sum = numbers.reduce(0, +)

Linked lists
Hash maps

class MyHashMap {

    var array = [Int]()
    
    /** Initialize your data structure here. */
    init() {
        
    }
    
    /** value will always be non-negative. */
    func put(_ key: Int, _ value: Int) {
        if array.count <= key {
            array += Array(repeating: -1, count: key - array.count + 1)
        }
        
        array[key] = value
    }
    
    /** Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key */
    func get(_ key: Int) -> Int {
        guard key < array.count else { return -1 }
        return array[key]
    }
    
    /** Removes the mapping of the specified value key if this map contains a mapping for the key */
    func remove(_ key: Int) {
        guard key < array.count else { return }
        array[key] = -1
    }
}

Stacks
Queues
Heaps
Trees
Graphs

Problem: Implement a min heap with extract_min and insert methods.

struct MinHeap<Element: Comparable> {
    private var elements: [Element]

    init(elements: [Element] = []) {
        self.elements = elements
        buildHeap()
    }

    var isEmpty: Bool {
        return elements.isEmpty
    }

    var count: Int {
        return elements.count
    }

    func peek() -> Element? {
        return elements.first
    }

    mutating func extractMin() -> Element? {
        guard !isEmpty else { return nil }
        swap(elements[0], elements[count - 1])
        let minElement = elements.removeLast()
        siftDown(from: 0)
        return minElement
    }

    mutating func insert(_ element: Element) {
        elements.append(element)
        siftUp(from: count - 1)
    }

    private mutating func siftDown(from index: Int) {
        var parent = index
        while true {
            let left = leftChildIndex(of: parent)
            let right = rightChildIndex(of: parent)
            var candidate = parent
            if left < count && elements[left] < elements[candidate] {
                candidate = left
            }
            if right < count && elements[right] < elements[candidate] {
                candidate = right
            }
            if candidate == parent {
                return
            }
            swap(elements[parent], elements[candidate])
            parent = candidate
        }
    }

    private mutating func siftUp(from index: Int) {
        var child = index
        var parent = parentIndex(of: child)
        while child > 0 && elements[child] < elements[parent] {
            swap(elements[child], elements[parent])
            child = parent
            parent = parentIndex(of: child)
        }
    }

    private func leftChildIndex(of index: Int) -> Int {
        return 2 * index + 1
    }

    private func rightChildIndex(of index: Int) -> Int {
        return 2 * index + 2
    }

    private func parentIndex(of index: Int) -> Int {
        return (index - 1) / 2
    }

    private mutating func buildHeap() {
        for index in (0...count / 2).reversed() {
            siftDown(from: index)
        }
    }
}

Swift
- How can I run XCTest for a swift application from the command line? - Stack Overflow #weblinks

swiftc \
-F/Applications/Xcode.app/Contents/Developer/Platforms/MacOSX.platform/Developer/Library/Frameworks \
-Xlinker -rpath -Xlinker /Applications/Xcode.app/Contents/Developer/Platforms/MacOSX.platform/Developer/Library/Frameworks \
-lswiftCore arrays.swift \
-o arrays

DSA#

Knowing What to Track#

Hash Maps#

Tree DFS, BFS, Trie#

Stacks#

Cyclic, Topological sort#

Dynamic Programming#

Backtracking#

Greedy techniques#

K-way Merge#

Top K Elements#

Union Find#

Modified Binary Search#

Subsets - Permutations, Combinations#

Two Heaps#

Reverse Linked List#

Merge Intervals#

Fast, Slow Pointers#

Two Pointers#

Sliding Window#

Data Structures#

Arrays#

Swift#

DSA