<?xml version="1.0" encoding="UTF-8"?><rss xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:content="http://purl.org/rss/1.0/modules/content/" xmlns:atom="http://www.w3.org/2005/Atom" version="2.0" xmlns:cc="http://cyber.law.harvard.edu/rss/creativeCommonsRssModule.html">
    <channel>
        <title><![CDATA[Stories by Alexander Danilyak on Medium]]></title>
        <description><![CDATA[Stories by Alexander Danilyak on Medium]]></description>
        <link>https://medium.com/@alexanderdanilyak?source=rss-20a6c65e5985------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/1*6VY-hMOC-qjCH--LYFtR-w.jpeg</url>
            <title>Stories by Alexander Danilyak on Medium</title>
            <link>https://medium.com/@alexanderdanilyak?source=rss-20a6c65e5985------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Wed, 18 Nov 2026 04:51:01 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@alexanderdanilyak/feed" rel="self" type="application/rss+xml"/>
        <webMaster><![CDATA[yourfriends@medium.com]]></webMaster>
        <atom:link href="http://medium.superfeedr.com/" rel="hub"/>
        <item>
            <title><![CDATA[[Swifty LeetCode #2] Disjoint-set (Union-find)]]></title>
            <link>https://medium.com/@alexanderdanilyak/swifty-leetcode-2-disjoint-set-union-find-e38efd5053aa?source=rss-20a6c65e5985------2</link>
            <guid isPermaLink="false">https://medium.com/p/e38efd5053aa</guid>
            <category><![CDATA[union-find]]></category>
            <category><![CDATA[disjoint-set]]></category>
            <category><![CDATA[leetcode]]></category>
            <category><![CDATA[swift]]></category>
            <category><![CDATA[coding-interviews]]></category>
            <dc:creator><![CDATA[Alexander Danilyak]]></dc:creator>
            <pubDate>Fri, 19 Jan 2024 20:32:53 GMT</pubDate>
            <atom:updated>2024-01-20T12:02:36.169Z</atom:updated>
            <content:encoded><![CDATA[<p>Hello! Welcome to the second article in our series on Data Structures from an iOS engineer’s perspective. In our <a href="https://medium.com/@alexanderdanilyak/swifty-leetcode-1-binary-heap-f3fe0e56ce59">first article</a>, we delved into the world of <strong>Heaps</strong>, with a special focus on<strong> Binary Heaps</strong>. If you missed it, I recommend checking it out.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*SZTcVFurhPonn7XPpgf0_w.png" /></figure><p>Today, we’re exploring the <strong>disjoint-set</strong>, an easy to create yet incredibly powerful data structure that proves invaluable for solving a broad spectrum of coding challenges.</p><h4>Disjoint-set</h4><p>A <strong>disjoint-set</strong> is a data structure that stores a collection of non-overlapping sets. Typically, it provides at least two essential methods: <em>union</em>, for merging two sets, and <em>find</em>, for identifying a representative member of a set. Due to these operations, it’s often referred to as a <strong>union-find</strong>.</p><h4>Implementation</h4><p>There are a lot of ways to implement a disjoint-set, but the most common approach is using a forest — a collection of trees (connected acyclic undirected graph). In that case, each tree represents a separate set.</p><p>To simplify the implementation, we’ll assume that each node stores only a pointer to its parent if it’s not the root of a tree, and a pointer to itself if it is. For storing these nodes, we’ll utilize an array.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*JVEOYcvI1VOw-IAtgmM8Yw.png" /><figcaption>Parent array for 8 sets</figcaption></figure><h4>Find</h4><p>The find is a main method of disjoint-set that provides a representative member of a set. In our implementation with <a href="https://en.wikipedia.org/wiki/Parent_pointer_tree"><em>parent pointer trees</em></a>, this task simplifies to ascending the tree until we reach the root, which will be our representative element. Now, let’s jump into the code.</p><pre>var parent = = Array(0..&lt;n)<br><br>func find(_ x: Int) -&gt; Int {<br>    if x == parent[x] {<br>        return x<br>    } else {<br>        return find(parent[x])<br>    }<br>}</pre><p>That was relatively straightforward 🙂. When considering the time complexity, this naive approach operates at <em>O(n)</em> because our trees in the forest has no height control. Consequently, we can end up with trees having a height of <em>O(n)</em>. For instance:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*FPFrU7Tf52JHtc8jWjT6MQ.png" /><figcaption>Parent array with one set with height 8 for 8 elements</figcaption></figure><p>Let’s address this issue with a simple trick. Whenever we use the find method recursively, we&#39;ll redirect the current node&#39;s pointer to the result of the find for the current node&#39;s pointer. This technique is known as <strong>path compression</strong>, significantly improving the time complexity to <em>O(log(n))</em>.</p><pre>func find(_ x: Int) -&gt; Int {<br>    if x == parent[x] {<br>        return x<br>    } else {<br>        parent[x] = find(parent[x])<br>        return parent[x]<br>    }<br>}</pre><p>The example above will transform to this:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*3nMOiEv97fEzMhwRVu3kWA.png" /><figcaption>Parent array with one set with height 2 for 8 elements</figcaption></figure><p>As a result, our tree has now shrunk to a height of 2.</p><h4>Union</h4><p>The union operation is used to merge two sets together, replacing them with a single set containing all elements from the two initial sets. Since we use a tree representation for sets, the merging algorithm is simple. We just find the representative elements for both sets and make one of them point to the other. Let&#39;s dive into the code.</p><pre>func union(_ x: Int, _ y: Int) -&gt; Bool {<br>    // Searching for representatives of each set<br>    let xi = find(x)<br>    let yi = find(y)<br>    <br>    // If they are equal, sets are already merged<br>    guard xi != yi else { return false }<br>    <br>    // We can do parent[xi] = yi instead, it doesn&#39;t matter now <br>    parent[yi] = xi<br><br>    return true<br>}</pre><p>The time complexity for this solution is <em>O(log(n))</em>. However, can we do better? When considering the two options for merging trees: setting parent[yi] = xi and parent[xi] = yi, it becomes clear that it’s more beneficial to add the smaller tree as a sub-tree to the root of the larger tree. This approach helps maintain a smaller height for the resulting tree.</p><p>To determine which tree is larger, we’ll create an additional array, componentSize, to keep track of changes inside the union function—the only way to increase the size of a particular tree.</p><pre>// Initially all trees have a height 1<br>var componentSize = Array(repeating: 1, count: n)<br><br>func union(_ x: Int, _ y: Int) -&gt; Bool {<br>    let xi = find(x)<br>    let yi = find(y)<br><br>    guard xi != yi else { return false }<br>    <br>    // Checking sizes of both trees and merging smaller tree to the bigger one <br>    if componentSize[xi] &gt; componentSize[yi] {<br>        componentSize[xi] += componentSize[yi]<br>        parent[yi] = xi<br>    } else {<br>        componentSize[yi] += componentSize[xi]<br>        parent[xi] = yi<br>    }<br>    <br>    return true<br>}</pre><p>This optimisation is known as <strong>union by size</strong>. By combining both path compression and union by size, we can bring the time complexity of each operation in disjoint-set to <em>Θ(𝛼(n))</em>, where <em>𝛼(n)</em> is the <a href="https://en.wikipedia.org/wiki/Ackermann_function#Inverse">inverse Ackermann function</a>. While the proof is complex and can be found <a href="https://codeforces.com/blog/entry/98275#:~:text=The%20complexity%20of%20union%2Dfind,)%CE%B1(n)).">here</a>, it’s unlikely you’ll ever need it 🫠. The crucial point about the inverse Ackermann function is its exceptionally slow growth.</p><h4>Component count</h4><p>In my practice several times I faced a case where it was crucial to know how much components we have right now. We can easily achieve it by tracking a number of components in the union method.</p><pre>var componentSize = Array(repeating: 1, count: n)<br>var componentCount = n<br><br>func union(_ x: Int, _ y: Int) -&gt; Bool {<br>    let xi = find(x)<br>    let yi = find(y)<br><br>    guard xi != yi else { return false }<br>    <br>    if componentSize[xi] &gt; componentSize[yi] {<br>        componentSize[xi] += componentSize[yi]<br>        parent[yi] = xi<br>    } else {<br>        componentSize[yi] += componentSize[xi]<br>        parent[xi] = yi<br>    }<br>    <br>    componentCount -= 1<br>    return true<br>}</pre><p>As you can see, adding this doesn’t change the asymptotic, and accessing componentCount is an O(1) operation.</p><h4>Outro</h4><p>The complete implementation can be found <a href="https://github.com/adanilyak/swifty-leetcode/blob/main/DS/Sources/DS/DisjointSet.swift">here</a>. For those eager to practice solving challenges using disjoint-set, here’s a selected list:</p><ol><li><a href="https://leetcode.com/problems/longest-consecutive-sequence/description/">Longest Consecutive Sequence</a> (<a href="https://leetcode.com/problems/longest-consecutive-sequence/solutions/4589448/solution-swift-union-find-o-n/">my solution</a>)</li><li><a href="https://leetcode.com/problems/min-cost-to-connect-all-points/">Min Cost to Connect All Points</a> (<a href="https://leetcode.com/problems/min-cost-to-connect-all-points/solutions/4589463/solution-swift-union-find-kruskal/">my solution</a>)</li><li><a href="https://leetcode.com/problems/remove-max-number-of-edges-to-keep-graph-fully-traversable/">Remove Max Number of Edges to Keep Graph Fully Traversable</a> (<a href="https://leetcode.com/problems/remove-max-number-of-edges-to-keep-graph-fully-traversable/solutions/3469950/solution-swift-unionfind/">my solution</a>)</li></ol><p>P.S. One of the most common applications of disjoint-set is <a href="https://en.wikipedia.org/wiki/Kruskal%27s_algorithm">Kruskal’s algorithm</a>, which you can practice in problem #2 above.</p><p>And remember, consistency is a key. See you in the next one!</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=e38efd5053aa" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[[Swifty LeetCode #1] Binary Heap]]></title>
            <link>https://medium.com/@alexanderdanilyak/swifty-leetcode-1-binary-heap-f3fe0e56ce59?source=rss-20a6c65e5985------2</link>
            <guid isPermaLink="false">https://medium.com/p/f3fe0e56ce59</guid>
            <category><![CDATA[coding-interviews]]></category>
            <category><![CDATA[heap]]></category>
            <category><![CDATA[leetcode]]></category>
            <category><![CDATA[swift]]></category>
            <category><![CDATA[ios-development]]></category>
            <dc:creator><![CDATA[Alexander Danilyak]]></dc:creator>
            <pubDate>Sat, 13 Jan 2024 18:31:16 GMT</pubDate>
            <atom:updated>2024-01-13T18:31:16.170Z</atom:updated>
            <content:encoded><![CDATA[<p>Hello! Today is my <a href="https://leetcode.com/adanilyak/"><strong>600-day anniversary</strong></a> of completing LeetCode daily challenges. So, I’ve decided to start a blog featuring short materials aimed at helping iOS engineers prepare for DSA interviews.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/960/1*1uINph40UCxlopMBYv1h3g.png" /></figure><h4>Approach</h4><p>The most crucial aspect of solving coding problems is to identify the right approach. Often, choosing the appropriate data structure can lead you to an optimal solution. Keeping this in mind, let’s delve into data structures.</p><p>I plan to skip basic structures that iOS engineers use on a daily basis, like Array, Set and Dictionary. Instead, I will focus on more specific ones that aren’t provided by the standard library.</p><h4>Heap</h4><p>Heap is a special tree-like data structure that satisfies the <strong>heap property</strong>, for the max-heap it is: <em>For any two nodes N1 and N2, if N1 is a parent of N2, key (value) of N1 is greater than key (value) of N2.</em></p><p>As you can see, this constraint leaves us a lot of space for different implementations. I propose focusing our attention on the binary heap, as it is sufficient for <strong>99%</strong> of real-world coding problems 🙂</p><h4>Binary Heap</h4><p>Here is the list of key points to remember about the implementation of a binary heap:</p><ol><li>It uses an array underneath</li><li>If the node has an index <strong><em>i</em></strong> in the array, its left and right child will have indexes <em>2 × i + 1</em> and <em>2 × i + 2 </em>respectively</li><li>We only need two functions to maintain heap property: siftUp and siftDown</li></ol><p>The first one doesn’t need explanation, so jump to the second one. We will illustrate it with example:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*Zgn9XzetAP2Xl27YtbMYdw.png" /><figcaption>Array representation of the heap</figcaption></figure><p>Now, if we visualise it as a binary tree:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*86MlADr337CKL_4pwYLLUQ.png" /><figcaption>Tree representation of the heap</figcaption></figure><h4>Insert element</h4><p>Now when we understand how the data stored in the array, let’s try to insert another element into the heap. To achieve this, we simply append a new element to the data array.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*gK1qhOc3EiMN5jlFqwnBPg.png" /><figcaption>Tree representation of the heap after we added 9 to the array</figcaption></figure><p>So far, so good. Now, our next step is to restore the heap property. Upon reviewing the property, we notice that it only constrains the keys (values) of parent and child nodes. In this case, we are interested solely in the highlighted chain of elements.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*rYfd0T3YuBByYNMDH23zKQ.png" /></figure><p>Our task is to elevate the new element, 9, along this chain by swapping positions until the heap property is satisfied. This action is called siftUp.</p><p>Before we dive into the code, it’s worth noting that, if a node has index <em>i</em>, its parent will have an index ⎣<em>(i - 1) / 2</em>⎦.</p><pre>var elements = [Int]()<br><br>func sift(up index: Int) {<br>    var i = index<br>    <br>    // Compare i-th element&#39;s key(value) with its parents key(value)<br>    while elements[i] &gt; elements[(i - 1) / 2] {<br>        // Swap elements until heap property is satisfied<br>        elements.swapAt(i, (i - 1) / 2)<br>        i = (i - 1) / 2<br>    }<br>}</pre><p>The time complexity of siftUp is <em>O(log(n))</em>. Now we can use siftUp function to create insert function.</p><pre>func insert(_ element: Int) {<br>    elements.append(element)<br>    sift(up: elements.count - 1)<br>}</pre><p>The time complexity of insert is <em>O(log(n))</em>.</p><h4>Poll element (Extract max)</h4><p>Let’s remove the first (root) element and replace it with the last element.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*9aOtwjspVzQViEpAu74Xaw.png" /><figcaption>Heap after removing the first (root) element</figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*n7kVJCODCiPgx5nfeGxIUw.png" /><figcaption>Heap after placing the last element at the top</figcaption></figure><p>As the heap property is no longer satisfied, to restore it, we must swap the highlighted node with its largest child.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*e-rz1sjNfo_UoWvH4Kr8kw.png" /><figcaption>Heap after swapping nodes with keys (values) 7 and 1</figcaption></figure><p>We should continue this procedure until the heap property is once again satisfied. That action is called siftDown.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*9Rs8i4Gdkp5cJ2QIHDBcdA.png" /><figcaption>Heap after completion of siftDown</figcaption></figure><p>Now we are ready to write some code.</p><pre>func sift(down index: Int) {<br>    var i = index<br>    <br>    // Checking that at least left child of i-th node <br>    // is inside array&#39;s boundaries<br>    while 2 * i + 1 &lt; size {<br>        let left = 2 * i + 1<br>        let right = 2 * i + 2<br>        <br>        // Checking if right child exists<br>        // And if yes, if it greater that the left child      <br>        var j = left<br>        if right &lt; size, elements[right] &gt; elements[left] {<br>            j = right<br>        }<br>        <br>        // If heap property is satisfied, leave the cycle<br>        if elements[i] &gt; elements[j] {<br>            break<br>        }<br>        <br>        // If not satisfied, swap the nodes&#39; keys (values) and continue<br>        elements.swapAt(i, j)<br>        i = j<br>    }<br>}</pre><p>The time complexity of siftDown is <em>O(log(n))</em>. Now we can use siftDown function to create poll function.</p><pre>func poll() -&gt; T? {<br>    guard !elements.isEmpty else { return nil }<br>    <br>    let pollingElement = elements[0]<br>    <br>    elements[0] = elements[elements.count - 1]<br>    elements.removeLast()<br>    <br>    sift(down: 0)<br>    <br>    return pollingElement<br>}</pre><p>The time complexity of poll is <em>O(log(n))</em>.</p><h4>Init with an array</h4><p>We are approaching the finish line! If we need to build a heap from an array, we can start with an empty heap and iterate over each element of the input array and use insert function. While this approach would work, it might not be the most efficient, with a time complexity of <em>O(n × log(n)).</em></p><p>Let’s observe that if, at some level of a binary heap, all subtrees satisfy the heap property, we can restore the heap property for the upper level by running the siftDown function on all nodes at that level.</p><p>Applying the observation mentioned earlier, we can initialize the heap with an input array and execute the siftDown function in a bottom-up order on all nodes except leaves. This is because each leaf node is already a subtree that satisfies the heap property. Due to the layout of the binary tree, leaf nodes will have indexes ranging from ⎣<em>n / 2</em>⎦ to <em>n - 1</em>.</p><pre>init(from array: [Int]) {<br>    self.elements = array<br>    <br>    (0..&lt;(array.count / 2)).reversed().forEach { i in<br>        sift(down: i)<br>    }<br>}</pre><p>The time complexity of this approach is <em>O(n)</em>. It’s not obvious, here is an <a href="https://www.cs.umd.edu/%7Emeesh/351/mount/lectures/lect14-heapsort-analysis-part.pdf">analysis</a> for ones who want to learn more.</p><h4>Outro</h4><p>We have taken apart the max binary heap with Int nodes. On practice, we also may need a min heap, or a heap with custom T nodes. It’s pretty easy to generalise the code above to support such features, I will skip this part and just provide you with the final <a href="https://github.com/adanilyak/swifty-leetcode/blob/main/DS/Sources/DS/Heap.swift">implementation</a>.</p><p>Also, here are some problems that can be solved using a heap, feel free to try them yourself 🙂.</p><ol><li><a href="https://leetcode.com/problems/last-stone-weight/">Last Stone Weight</a> (<a href="https://leetcode.com/problems/last-stone-weight/solutions/3450088/solution-swift-heap/">my solution</a>)</li><li><a href="https://leetcode.com/problems/cheapest-flights-within-k-stops/">Cheapest Flights Within K Stops</a> (<a href="https://leetcode.com/problems/cheapest-flights-within-k-stops/solutions/3101482/solution-swift-dijkstra-heap/">my solution</a>)</li><li><a href="https://leetcode.com/problems/find-k-pairs-with-smallest-sums/">Find K Pairs with Smallest Sums</a> (<a href="https://leetcode.com/problems/find-k-pairs-with-smallest-sums/solutions/3688819/solution-swift-heap/">my solution</a>)</li><li><a href="https://leetcode.com/problems/sliding-window-maximum/description/">Sliding Window Maximum</a> (<a href="https://leetcode.com/problems/sliding-window-maximum/solutions/3917773/solution-swift-rust-heap/">my solution</a>)</li><li><a href="https://leetcode.com/problems/the-skyline-problem">The Skyline Problem</a> (<a href="https://leetcode.com/problems/the-skyline-problem/solutions/2645163/solution-swift-heap-beats-90/">my solution</a>)</li></ol><p>And remember, consistency is a key. See you in the next one!</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=f3fe0e56ce59" width="1" height="1" alt="">]]></content:encoded>
        </item>
    </channel>
</rss>