What is a Tree? A Tree is a data structure that has a root and subtrees of children, representing a set of linked nodes. Trees behave similarly to a LinkedList in that they have a collection of nodes starting with a head (root). The main difference is that Trees can have multiple children, whereas a LinkedList, on the other hand, can have only one next child. I’m going to focus on a commonly used type of tree, the Binary Search Tree. ...
What is the sliding window technique? The sliding window technique is a common algorithmic approach used to create a fixed-sized window that moves through the data one step at a time, typically from left to right, to perform specific operations or computations on the elements within the window. What is the sliding window algorithm? The sliding window algorithm is a method for finding a subset of elements that satisfy certain conditions in a given problem. ...
What is a Linked List? A linked list is a common data structure that is similar to an array, but its order is based on pointers to the next element in memory instead of using physical placement (indices). A linked list has two main components: ListNode class: This class has a val property that represents the value and a next property that represents a pointer to the next element in memory. LinkedList class: This class stores a collection of ListNode elements and provides operations like add to tail and add to head. The add to tail operation takes O(n) time because it needs to iterate through the list to find the last element. The add to head operation takes O(1) time because it only needs to set the next pointer of the new node to the current head and update the head with the new node. Where can it be used? A linked list can be used in stacks, queues, and lists. ...
What is binary search? Binary search is an algorithm that helps find an element in a sorted array in O(log n) time. Why should the input be sorted before performing binary search? The input array for binary search needs to be sorted because the algorithm eliminates half of the choices at each step. If the guessed value is greater than the target value, it knows that the right part can’t contain the target value. ...
What is a Stack? A stack is an abstract data type that serves as a collection of elements and implements operations like push, pop, and peek at the end in O(1) time. It uses the LIFO (last in, first out) order. For example, a stack can be a collection of items where adding or removing is practical at the top. Code Example struct Stack<Element> { private var array: [Element] init(array: [Element] = []) { self.array = array } mutating func push(_ element: Element) { array.append(element) } mutating func pop() -> Element? { if array.isEmpty { return nil } return array.popLast() } func peek() -> Element? { if array.isEmpty { return nil } return array.last } } Practical Applications of Stacks You can observe stack-like behavior in many places, such as redo-undo features in text editors, Photoshop, and the forward and backward navigation features in web browsers. ...