LeetCode - Blind 75 - Two Sum

The Problem Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to the target. You may assume that each input would have exactly one solution, and you may not use the same element twice. You can return the answer in any order. Example Input: nums = [2,7,11,15], target = 9 Output: [0,1] Explanation: Because nums[0] + nums[1] == 9, we return [0, 1]....

October 25, 2024 · 2 min · Dmytro Chumakov

DSA - Sorting - Selection Sort

Introduction The selection sort is an in-place comparison sorting algorithm. It’s similar to bubble sort in that it works by repeatedly swapping items in a list and not very efficient on larger lists. source Code Example func selectionSort(_ array: [Int]) -> [Int] { var A = array let N = array.count for i in 0 ..< N { var jMin = i for j in (i + 1) ..< N { if A[j] < A[jMin] { jMin = j } } if jMin !...

October 23, 2024 · 1 min · Dmytro Chumakov

DSA - Sorting - Quick Sort

Introduction The quick sort is an efficient sorting algorithm commonly used widely in production. Quick sort is a divide-and-conquer algorithm. It works by selecting a pivot from the array and partitioning the other elements into two subarrays. source Code example // Sorts a (portion of an) array, divides it into partitions, then sorts those func quickSort(array: inout [Int], low: Int, high: Int) { // Ensure indices are in correct order if low < high { // Partition array and get the pivot index let p = partition(array: &array, low: low, high: high) // Sort the two partitions quickSort(array: &array, low: low, high: p - 1) // Left side of pivot quickSort(array: &array, low: p + 1, high: high) // Right side of pivot } } // Divides array into two partitions func partition(array: inout [Int], low: Int, high: Int) -> Int { let pivot = array[high] // Choose the last element as the pivot // Temporary pivot index var i = low for j in low ....

October 19, 2024 · 2 min · Dmytro Chumakov

DSA - Sorting - Insertion Sort

Introduction The insertion sort algorithm builds a sorted list one item at a time by comparison. It is more efficient on small datasets but much less efficient on larger ones. source source Code Example func insertionSort(_ array: [Int]) -> [Int] { var A = array for i in 0 ..< A.count { var j = i while j > 0 && A[j - 1] > A[j] { let tmp = A[j] A[j] = A[j - 1] A[j - 1] = tmp j -= 1 } } return A } Implementation For each index in the input array: Set the j variable to i....

October 15, 2024 · 2 min · Dmytro Chumakov

DSA - Sorting - Merge Sort

What is Merge Sort? Merge sort is a recursive algorithm that uses the divide and conquer algorithm design paradigm to find the solution. source The merge sort conceptually consists of two separate functions: mergeSort and merge. It works as follows: Divide the unsorted list into two equal halves. Recursively sort the two halves. Merge the two halves to form a sorted array. There are multiple implementations of merge sort. I will be focusing on the top-down implementation using lists....

October 14, 2024 · 2 min · Dmytro Chumakov