<?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 Emmanuel Wilson on Medium]]></title>
        <description><![CDATA[Stories by Emmanuel Wilson on Medium]]></description>
        <link>https://medium.com/@wilsonemmanuel144?source=rss-ae1a8f2b8bdf------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/1*dFj_RrKDwFrIPTJoo_p4YQ@2x.jpeg</url>
            <title>Stories by Emmanuel Wilson on Medium</title>
            <link>https://medium.com/@wilsonemmanuel144?source=rss-ae1a8f2b8bdf------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Sun, 22 Nov 2026 16:58:20 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@wilsonemmanuel144/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[Minimum Operations to Make Array Equal: Understanding the Thought Process for Interviews]]></title>
            <link>https://levelup.gitconnected.com/minimum-operations-to-make-array-equal-understanding-the-thought-process-for-interviews-5dd15d7390e7?source=rss-ae1a8f2b8bdf------2</link>
            <guid isPermaLink="false">https://medium.com/p/5dd15d7390e7</guid>
            <category><![CDATA[arrays]]></category>
            <category><![CDATA[algorithms]]></category>
            <category><![CDATA[coding-interviews]]></category>
            <category><![CDATA[leetcode]]></category>
            <category><![CDATA[math]]></category>
            <dc:creator><![CDATA[Emmanuel Wilson]]></dc:creator>
            <pubDate>Wed, 07 Apr 2021 14:22:41 GMT</pubDate>
            <atom:updated>2021-07-15T02:15:39.289Z</atom:updated>
            <content:encoded><![CDATA[<h3>Minimum Operations to Make Array Equal: Understanding the Thought Process for Interviews and Leetcoding</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*rLFIeRPh-O2jKIIE" /><figcaption>Photo by <a href="https://unsplash.com/@cytonn_photography?utm_source=medium&amp;utm_medium=referral">Cytonn Photography</a> on <a href="https://unsplash.com/?utm_source=medium&amp;utm_medium=referral">Unsplash</a></figcaption></figure><p>This is a standard algorithmic problem confirmed to have been asked in many technical interviews. <a href="https://leetcode.com/problems/minimum-operations-to-make-array-equal/#:~:text=Minimum%20Operations%20to%20Make%20Array%20Equal%20%2D%20LeetCode&amp;text=You%20have%20an%20array%20arr,arr%5By%5D%20%2B%3D%201%20)">This problem appeared in the April 2021 Leetcode monthly challenge</a> with the difficulty of <strong>Medium</strong>. Whether you are prepping for a technical interview or you are just an algorithm lover like me, I strongly believe this post will make an interesting read.</p><p><strong>Problem Statement</strong><br>You have an array arr of length n where arr[i] = (2 * i) + 1 for all valid values of i (i.e. 0 &lt;= i &lt; n).<br>In one operation, you can select two indices x and y where 0 &lt;= x, y &lt; n and subtract 1 from arr[x] and add 1 to arr[y] (i.e. perform arr[x] -=1 and arr[y] += 1). The goal is to make all the elements of the array <strong>equal</strong>. It is <strong>guaranteed</strong> that all the elements of the array can be made equal using some operations.</p><p>Given an integer <strong>n,</strong> the length of the array. Return <em>the minimum number of operations</em> needed to make all the elements of arr equal.</p><p><strong>Example</strong><br><strong>Input:</strong> n = 3<br><strong>Output:</strong> 2<br><strong>Explanation:</strong> arr = [1, 3, 5]<br>First operation choose x = 2 and y = 0, this leads arr to be [2, 3, 4]<br>In the second operation choose x = 2 and y = 0 again, thus arr = [3, 3, 3].</p><p><strong>SOLUTION</strong><br>When faced with this kind of problem in an interview, what would be your first step? Given such an array, <br><strong>1</strong>) How do you find the <strong>target number</strong>, i.e. the number that all other elements should be equal to?<br><strong>2</strong>) Since operations are performed between pairs of elements in the array, how can we <strong>optimally </strong>select which pair to operate on?</p><p><strong>Identify Patterns: Brute-Force</strong><br>The first and best step to solving any algorithmic problems that are new to you is always to try to observe some common patterns using few test cases.<br>Now, we’ll study two test arrays by considering all possible arrangements of pairs of elements in each of the arrays. That way, the first pair in each arrangement will be used to generate the <strong>target number </strong>and we will try to reduce other remaining pairs in the arrangement to the generated target number<strong>.</strong></p><p><strong>TEST 1</strong>: when <strong>n</strong>is even. Let n = 4, arr=[1,3,5,7]<br>There are 6 different arrangement of pairs for this array.<br>{1,3}, {5,7}<br>{1,5},{3,7}<br>{1,7},{3,5}<br>{3,5},{1,7}<br>{5,7},{1,3}</p><p><strong>i.</strong> {1,3} reduces to {2,2} in 1 operation. Then<strong> target number</strong> = 2<br> {5,7}→ It is not possible to reduce elements of this pair to 2.</p><p><strong>ii.</strong> {1,5} reduces to {3,3} in 2 operations. Then <strong>target number</strong> = 3<br> {3,7}→ It is not possible to reduce 7 to 3.</p><p><strong>iii.</strong> {1,7} reduces to {4,4} in 3 operations. Then<strong> target number</strong> =4 <br>{3,5} reduces to {4,4} in 1 operation.<br>Thus, 4 operations are required to reduce all elements to 4.</p><p><strong>iv.</strong> {3,5} reduces to {4,4} in 1 operation. Then <strong>target number </strong>= 4<br> {1,7} reduces to {4,4} in 3 operations.<br>Thus, 4 operations are required to reduce all elements to 4.</p><p><strong>v</strong>. {3,7} reduces to {5,5} in 2 operations. Then <strong>target number</strong> = 5<br> {1,5} → It is not possible to change 1 to 5.</p><p><strong>vi</strong>. {5,7} reduces to {6,6} in 1 operation. Then target number = 6<br> {1,3} → It is not possible to change the elements of this pair to 6</p><p><strong>We Found a Pattern</strong><br>Voila! we found the pattern we’re looking for. <strong>Steps iii and iv </strong>give the required solution. Notice that steps iii and iv are the same process in the opposite direction. Whichever pattern you take will definitely give you a solution. By step <strong>iii</strong>, here are important points to note:<br>1) The <strong>target number</strong> is the number of operations required to make the two middle elements equal. Then the minimum operation is achieved when all other remaining pairs are reduced to this target number.<br>2) A pair is made up of 2 elements that are at the <strong>same distance</strong> from the <strong>center of the array</strong>. See the image below.<br>3) Given a pair of array elements say {a,b}, the number of operations requires to make them equal to the target number is half of the positive difference between the two elements of the pair i.e. (b-a)/2 where b &gt; a. <br>4) From the image below, arr[i] forms a pair with arr[n-i-1]. Since arr[i]=(2*i)+1 and arr[n-i-1] &gt; arr[i], the number of operation required to reduce the pair {arr[i], arr[n-i-1)} to the target number is calculated as follows</p><p>=(arr[n-i-1]-arr[i])/2 <br> = (2(n-i-1) — (2i +1))/2<br> = n-2i-1 <br>Since the total number of valid pairs are always equal to half of the array size i.e. n/2, The total minimum number of operations required to make all elements of an array of size n equal is the sum of alln-2i-1 where i= 0,1,...,(n/2)-1.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/521/1*XKRTE6ItXNG_oyn2Dorysg.png" /><figcaption>Pairs of elements that require min number of operations to make all elements in an array equal when <strong>n</strong> is even</figcaption></figure><p><strong>TEST 2</strong>: When <strong>n </strong>is odd. E.g. Let n= 5, then arr = [1,3,5,7,9]. <br>Notice that in this case, all elements except one can form pairs. This means that since one element can never have a pair, such an element would serve as the <strong>target number</strong>. The question is which of the elements can serve as the target number? It turns out that we have to consider all possible pair arrangements taking each element as the target number. Notice that whenever an element is taken to be the target number, the remaining four elements can form only three distinct pair arrangements. For example, when the target number is 1, the following pairs are considered : {3,5},{7,9}, {3,7},{5,9}, {3,9},{7,5}.</p><p><em>Notice the difference with the previous arrangement when </em><em>n is even. The target number was unknown, hence the </em><strong><em>order </em></strong><em>of pairs arrangement was important since the first pair was always used to generate the target number.</em></p><p>Thus, for each of the 5 possible target numbers, there are 3 possible pairs arrangements. This means that there are 5*3 = 15 arrangements to check. This might be time-consuming and prone to errors during an actual interview. Instead, I would like to apply the same steps we found in Test 1. Since valid pairs are symmetric around the center of the array, the element at the center of the array will always be the <strong>target number</strong>.</p><p>For the current array,Target number = 5, the pair {3,7} requires 2operations to change its elements to 5. Also, the pair {1,9} requires 4operations to change its elements to 5. If you are able to check all other possible arrangements, you will notice that taking the middle element as the target number would give the optimal solution. Thus, when n is odd, the pair formation looks like the image below.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/595/1*L690_U0Tb-UM5ZIv-W3MSw.png" /><figcaption>Pairs of elements that require min number of operations to make all elements in an array equal when <strong>n</strong> is odd</figcaption></figure><p>Having got a valid pattern, we can code our first implementation of the solution.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/7ef8f644584dc861734158a0b393a031/href">https://medium.com/media/7ef8f644584dc861734158a0b393a031/href</a></iframe><p><strong>Analysis of the Above Approach</strong><br>The <strong>time complexity</strong> of the above approach is <strong>O(n</strong>). The <strong>space complexity is constant</strong> since the actual array is never created.<br>Can we do better than this?</p><p><strong>EFFICIENT IMPROVEMENT</strong><br>It’s amazing how the hard-looking problem was reduced to a few lines of understandable code. But we can do more. This time we focus more on the <strong>number of operations needed at each step and the patterns that the numbers follow</strong>.</p><p>1)When n is even. If you take a bigger even number as n and calculate the number of operations i.e. n-2i-1 from i=0,1,2,...,(n/2)-1, you’ll get the following series n-1, n-3, ..., 7, 5, 3, 1 . When the series is reversed, you’ll get 1, 3, 5, 7, ..., n-3, n-1. If you remember from Math class, this is simply a series of odd numbers starting from 1 or an Arithmetic series with first element = 1 and common difference = 2. The number of elements in the series is exactly n/2. The required result is the sum of this series. Using the formula for the Sum of Arithmetic Series with n elements Sum of A.S = n(2a + (n-1)d)/2, where a= first element, d = common difference, we can calculate the minimum number of operations by substituting n = n/2, a= 1, and d= 2 in the Sum of A.S formula. Hence, Result = (n/2)(2a + (n/2 — 1)d)/2. With further simplification, Result = (n*n)/4.</p><p>2) When n is odd. Using the same approach as above, the following series are generated; 2, 4, 6, ..., n-3, n-1. This is the series of even numbers starting from 2. It is also an Arithmetic Series with n/2 elements where first number, a = 2, commonn difference, d = 2. Using the formula for Sum of A.S as above, the total number of operation required to make all elements in the array equal is also (n*n)/4. Below is the code implementation in Java.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/03b5b4faf88cab41939b0f27874af785/href">https://medium.com/media/03b5b4faf88cab41939b0f27874af785/href</a></iframe><p><strong>Analysis </strong><br>This is unbelievably amazing!. Only a single line of code and both <strong>time and space complexity are constant</strong>.</p><p><strong>Conclusion</strong><br>If you got to this point, Kudos! I believe you learned one or two. Always remember to look for patterns whenever you encounter unfamiliar problems. <a href="https://levelup.gitconnected.com/find-the-location-of-the-max-element-in-an-unsorted-array-using-binary-search-96b6d2c9a547">You can also find out how to find an element from an array that is not sorted</a>, or <a href="https://levelup.gitconnected.com/shortest-unsorted-continuous-subarray-b7401e839b7e">how to find the shortest subarray that should be sorted in order to keep the whole array sorted</a>.</p><p>Wilson :-)</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=5dd15d7390e7" width="1" height="1" alt=""><hr><p><a href="https://levelup.gitconnected.com/minimum-operations-to-make-array-equal-understanding-the-thought-process-for-interviews-5dd15d7390e7">Minimum Operations to Make Array Equal: Understanding the Thought Process for Interviews</a> was originally published in <a href="https://levelup.gitconnected.com/">Level Up Coding</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Shortest Unsorted Continuous Subarray]]></title>
            <link>https://levelup.gitconnected.com/shortest-unsorted-continuous-subarray-b7401e839b7e?source=rss-ae1a8f2b8bdf------2</link>
            <guid isPermaLink="false">https://medium.com/p/b7401e839b7e</guid>
            <category><![CDATA[arrays]]></category>
            <category><![CDATA[software-engineering]]></category>
            <category><![CDATA[algorithms]]></category>
            <category><![CDATA[coding-interviews]]></category>
            <dc:creator><![CDATA[Emmanuel Wilson]]></dc:creator>
            <pubDate>Wed, 03 Mar 2021 15:49:00 GMT</pubDate>
            <atom:updated>2021-03-03T16:13:28.401Z</atom:updated>
            <content:encoded><![CDATA[<p>In this post, I will be explaining my solution to one of the <a href="https://leetcode.com/explore/challenge/card/february-leetcoding-challenge-2021/587/week-4-february-22nd-february-28th/3652/">Leetcode algorithmic problems for February 2021 monthly challenge</a>.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/710/1*eBWxsODAf8STjQNcnKZUtA.png" /><figcaption>Shortest Unsorted Continuous Subarray</figcaption></figure><p><strong>PROBLEM STATEMENT</strong><br>Given an integer array nums, you need to find one <strong>continuous subarray</strong> that if you only sort this subarray in ascending order, then the whole array will be sorted in ascending order. Return <em>the shortest such subarray and output its length</em>.</p><p><strong>SOLUTION</strong><br>As can be seen from the above image, a Shortest Continuous Subarray is the shortest unsorted subarray of an array that when sorted would leave the whole array sorted in that order. For example, in the array {1,2,3,4,<strong>6,7,8,10,9,5,</strong>11,15}, the shortest subarray we can sort to keep the whole array sorted in ascending order is subarray starting from index 4 to index 9 i.e. {6,7,8,10,9,5}, hence the solution is 6, which is the length of the subarray.<br>Can you think of any solution to this problem? Of course, the Brute-force approach.</p><p><strong>BRUTE-FORCE APPROACH</strong><br>Surprisingly, even the supposedly easy brute-force approach is not readily intuitive in this case. What do you think would be the brute-force solution to this problem? The following steps explains what I take as the brute-force approach:</p><p><strong>1</strong>. For each value in the array, say <strong>current value;</strong><br><strong>2</strong>. Find the <strong>index </strong>of the <strong>first</strong> value in the array that is <strong>larger</strong> than the <strong>current value</strong> if it exits, starting from the <strong>beginning </strong>of the array to the location of the <strong>current value</strong>. If the index exists, let’s call it left_index.<br><strong>3</strong>. Also, find the index of the first value in the array that is smaller than the current value, if it exists, starting from the <strong>end </strong>of the array to the location of the <strong>current value</strong>. If the index exists, let’s call it right_index.<br><strong>4</strong>. Find all the existing left_index and right_index with respect to all the entries in the array. Let’s min_left represent the min of all left_indexes and min_right the max of all right_indexes. the subarray [min_left, min_right is the shortest unsorted continuous subarray of the original array. If no left_index and right_index exist, then the array is already sorted in ascending order.</p><p>For example, consider the array {11,12,13,16,15,14,17,19}. Let’s perform the above steps on the array from indexes i=0 to 7:<br><strong>When i= 0</strong> with value <strong>11</strong>: There is no value to left of 11 which is greater than 11 and there is no value to the right of 11 which is smaller than 11, hence no left_index and no right_index.<br><strong>When i=1</strong> with value <strong>12:</strong> No left_index and no right_index.<br><strong>When i=2</strong> with value <strong>13</strong>: No left_index and no right_index.<br><strong>When i=3</strong> with value<strong> 16</strong>: No left_index, But right_index = 5(because 14, which is at index 5 from the beginning of the array, is the first element that is smaller than 16.<br><strong>When i=4</strong> with value <strong>15</strong>: left_index = 3(because 16, which is at index 3, is the first element from the beginning of the array, that is smaller than 15). Also right_index = 5.<br><strong>When i=5</strong> with value <strong>14</strong>: left_index = 3 but no right_index.<br><strong>When i=6</strong> with value <strong>17</strong>: no left_index and no right_index.<br><strong>When i=7</strong> with value <strong>19</strong>: no left_index and no right_index.</p><p>The <strong>min </strong>of all left_indexes is 3 while the <strong>max </strong>of all right_indexes is 5, hence the <strong>shortest unsorted continuous subarray</strong> is [3, 5]. You can confirm this by looking at the values in the subarray [3,5] of the given array in the example, which are {16,15,14}. Notice that this subarray is not sorted in ascending order and if it become sorted in ascending order, then the given array would be sorted in ascending order too.<br>Below is the code implementation of the above approach in Java.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/682a201fa2805f38d88b4b5510b65fe1/href">https://medium.com/media/682a201fa2805f38d88b4b5510b65fe1/href</a></iframe><p><strong>ANALYSIS OF THE BRUTE-FORCE APPROACH</strong><br>The time complexity of the brute-force approach is O(N²). Notice that the worst case of the approach occurs when the original array is already sorted in ascending order. In such case, for every entries, the whole array is checked for the left_index and right_index. No auxiliary memory was used.</p><p><strong>APPROACH 2: PREPROCESSING AND 2-POINTERS TECHNIQUE</strong><br>This approach has only 2 major steps;<br><strong>1.</strong> Given an array say <strong>arr</strong>, iterate the given array once and find all occurrences of this format: arr[i] &gt; a[j] for all i &lt; j ,where a[j] is the smaller value and a[i] is the larger value. Keep track of the minimum of all a[j] as <strong>min </strong>and maximum of all a[i] as <strong>max. </strong>If there is no such occurrence, then the given array is already sorted in ascending order.<strong><br>2. </strong>Using the <strong>min </strong>and <strong>max </strong>obtained in Step 1, employ 2-pointer technique to find the index (say left)of the first element in the given array from the beginning, which is <strong>greater </strong>than <strong>min</strong>. Also, find the index (say right) of the first element in the given array from the end, which is <strong>smaller </strong>than <strong>max</strong>.<br>The subarray [left, right] is the <strong>shortest unsorted continuous subarray</strong> of the given array.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/837/1*ZJKFYpEd_tEySdLwcKlhuw.png" /></figure><p><strong>ANALYSIS OF THE SECOND APPROACH</strong><br>The time complexity of the second approach is <strong>O(N)</strong> where N is the length of the given array. Notice that we only linearly iterated the array twice — to find the min and max elements at locations where there are mismatched arrangements, then using 2-pointers technique to find the right locations of min and max. No auxiliary space used.<br>Below is the code implementation of the second approach in Java.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/9665643e19e943c22dfc43d0b5ca6a73/href">https://medium.com/media/9665643e19e943c22dfc43d0b5ca6a73/href</a></iframe><p><strong>Conclusive Remark:</strong><br>Thank you for checking out this post. If you have any comment or suggestion, please let me know in the comment sections. :-)</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=b7401e839b7e" width="1" height="1" alt=""><hr><p><a href="https://levelup.gitconnected.com/shortest-unsorted-continuous-subarray-b7401e839b7e">Shortest Unsorted Continuous Subarray</a> was originally published in <a href="https://levelup.gitconnected.com/">Level Up Coding</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[How to Convert Roman Numerals to Integer]]></title>
            <link>https://wilsonemmanuel144.medium.com/how-to-convert-roman-numerals-to-integer-f9b6764037c?source=rss-ae1a8f2b8bdf------2</link>
            <guid isPermaLink="false">https://medium.com/p/f9b6764037c</guid>
            <category><![CDATA[algorithms]]></category>
            <category><![CDATA[roman-numerals]]></category>
            <category><![CDATA[conversion]]></category>
            <category><![CDATA[leetcode-solution]]></category>
            <category><![CDATA[java]]></category>
            <dc:creator><![CDATA[Emmanuel Wilson]]></dc:creator>
            <pubDate>Tue, 23 Feb 2021 08:46:14 GMT</pubDate>
            <atom:updated>2021-02-23T09:00:55.740Z</atom:updated>
            <content:encoded><![CDATA[<p>In this post, I will be solving one of the interesting and easy algorithmic questions that appeared in the <a href="https://leetcode.com/explore/challenge/card/february-leetcoding-challenge-2021/586/week-3-february-15th-february-21st/3646/">February 2021 Leetcode Monthly challeng</a>e.</p><p><strong>PROBLEM STATEMENT</strong><br>Given the following Roman symbols and their integer representations, write an algorithm to convert Roman Numerals to Integer;</p><pre><strong>Symbol       </strong>Value<br>I             1<br>V             5<br>X             10<br>L             50<br>C             100<br>D             500<br>M             1000</pre><p><strong>Few Explanatory Points</strong><br>Roman numerals are represented by the 7 symbols in the above table and are usually written largest to smallest from left to right. For example, 2 is written as II in Roman numeral, just two ones&#39; added together. 12 is written as XII, which is simply X + II. The number 27 is written as XXVII, which is XX + V + II.</p><p>However, the numeral for 4 is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:</p><ul><li>I can be placed before V (5) and X (10) to make 4 and 9.</li><li>X can be placed before L (50) and C (100) to make 40 and 90.</li><li>C can be placed before D (500) and M (1000) to make 400 and 900.</li></ul><p><strong>Examples</strong><br>II → 1 + 1 = 2<br>XII → 10 + 1 + 1 = 12<br>III → 1 + 1 + 1 = 3<br>LVIII → 50 + 5 + 1 + 1 + 1<br>IV → 5 -1 = 4<br>IX → 10 -1 = 9<br>XL → 50 -10 = 40<br>XC → 100 -10 = 90</p><p>Looking at the few examples above, you’ll observe the patterns between the Roman numerals and integers. The conversion steps are explained below;<br><strong>1</strong>. Store the Base Roman symbols in a hash map as keys and their integers as hash map values<br><strong>2</strong>. Initialize a “sum” variable to zero and iterate the given Roman string to be converted character-wise starting from the right-most character.<br>3. For each character in the given string, fetch its integer value from the hash map. If the fetched value of the current roman character is smaller than the integer value of the previous roman character (in front of it), subtract the fetched value from the “sum”, else add it to the sum. <br>4. Return the “sum” when you get to the left-most character of the given string.<br>Below is the Java code implementation of the conversion steps.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/c05240d27e69f6bdad3be82c5a9a6be5/href">https://medium.com/media/c05240d27e69f6bdad3be82c5a9a6be5/href</a></iframe><p>ANALYSIS<br>Time complexity: O(N) where N is the length of the given string.<br>Auxiliary Space: O(1) — there are only 7 symbols in the map which is not affected by the input size.<br>Thanks for reading! :-)</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=f9b6764037c" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Find the Location of the Max Element in an Unsorted Array Using Binary Search]]></title>
            <link>https://levelup.gitconnected.com/find-the-location-of-the-max-element-in-an-unsorted-array-using-binary-search-96b6d2c9a547?source=rss-ae1a8f2b8bdf------2</link>
            <guid isPermaLink="false">https://medium.com/p/96b6d2c9a547</guid>
            <category><![CDATA[software-engineering]]></category>
            <category><![CDATA[competitive-programming]]></category>
            <category><![CDATA[coding-interviews]]></category>
            <category><![CDATA[binary-search]]></category>
            <category><![CDATA[algorithms]]></category>
            <dc:creator><![CDATA[Emmanuel Wilson]]></dc:creator>
            <pubDate>Tue, 23 Feb 2021 05:49:45 GMT</pubDate>
            <atom:updated>2021-03-03T16:13:23.851Z</atom:updated>
            <content:encoded><![CDATA[<p>In this post, I will be explaining a solution to one of the most interesting algorithmic problems I encountered recently. At the same time, demystify a common misconception about BINARY SEARCH (BS).</p><p><strong>PROBLEM STATEMENT </strong><br>There is an <strong>unsorted </strong>array of size <strong>n</strong> ( 2 ≤<strong> n</strong> ≤ 10⁵). The array contains distinct integer values. You are given the size of the array <strong>n </strong>and your task is to find the <strong>index </strong>( 1 ≤<strong>index</strong>≤n) of the largest element in the array. You are also given access to an <strong>object </strong>from which you can query the position of the second maximum element in any subarray <strong>[left, right]</strong> of the original array using the method format, <strong>object.query(left, right),</strong> (<strong>1 ≤ left &lt; right ≤ n</strong>). You are only allowed to make a maximum of <strong>20 </strong>queries. Your task is to complete the function below.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/cd2f541d56d66a064a10a6d1750d1ee8/href">https://medium.com/media/cd2f541d56d66a064a10a6d1750d1ee8/href</a></iframe><p><strong>EXPLANATION OF THE PROBLEM STATEMENT <br></strong>1. Your task is to write a function that finds the position or index of the MAX value in the array and returns it (<strong>1 ≤ index ≤ n</strong>). Note that the array is not sorted. Also note that the question is not asking for the maximum element, rather its position in the array (not zero-based index).<br>2. The array is already fixed and all query results for a single test case come from the same array, so the position of the max element in the array is fixed.<br>3. You can query the <strong>index </strong>of the second maximum element in a particular subarray of the original array up to <strong>20 </strong>times. For the parameters of the object’s query method, the difference between the <strong>right </strong>and <strong>left </strong>params must be greater or equal to 1.</p><blockquote>This problem recently appeared in a programming contest. The problem intrigued me, so I decided to share the solution and also clear some misconceptions about BS. I have modified the question to suit the purpose of this post since it was an interactive problem.</blockquote><p>If you have read up to this point, I believe you’d be pondering over the problem and how it could be solved using BS. I have always believed that BS can only be applied on a sorted array. However, I learned recently that BS application does not depend on whether the searched array (or space) is sorted or not. <strong>It actually depends on the known properties/features of the searched array</strong>. <br>More formally, Binary Search, as the name implies, <em>is a searching technique that efficiently finds the target element in logarithmic time by constantly splitting the searched space into halves</em>. For BS to work, <strong>there must exist some sort of knowledge/information either within or outside the searched array</strong> that would make it possible to accurately reduce the searched space by almost a half after a single move. <strong>Knowing </strong>that an array is sorted is enough <strong>information </strong>to apply BS since we know that, in a sorted array, every i &lt; j, ai &lt;= ajor ai ≥ aj. However, there could be different knowledge of the array (outside being sorted) that would make it possible to reduce the searched array by half after a single move. Several other problems also employ BS on unsorted arrays.<br>Having said enough about BS, let’s go back to our initial problem and see how it can be solved using BS.</p><p><strong>SOLUTION: APPROACH 1</strong> (Number of queries exceeded)<br>Let’s consider the information available to us for finding the maximum element in our “mystery” array. I used the word “mystery” because we don’t actually know anything about the array values. If so, how do we find the position of the largest element?<br>It turns out that by asking at most 2 queries about the location of the 2nd maximum element in the array or its subarrays (which is available to us), we can know which side of the array the maximum element is located on. That way, we would be able to split the array into halves after making some queries and eventually get to the position of the largest element.</p><p><strong>STEPS</strong><br><strong>1</strong>. Let left and right be the first and last indexes of the current search space. Find the mid index of the array, i.e. mid = (left+right)/2 . Now, mid has divided the current search space into 2 halves: [left,mid] and [mid,right].</p><p><strong>2</strong>. Find the position of the second maximum element between left and right indexes (i.e. the second max element in the current search space), i.e.<br> smax_all = object.query(left,right), where object is the query object given in the function we are asked to complete.</p><p><strong>3 i</strong>. If the second max element in the entire current search space is located in the second half of the array (i.e. mid &lt;= smax_all), then find the second maximum element in the second half (i.e. smax_2nd = object.query(mid, right)). If the second max elements in the entire array and the second max element in the 2nd half of the array are equal (i.e. smax_all == smax_2nd), then the maximum element in the array must be in the second half, hence replace the left pointer with the mid pointer. However, if smax_all != smax_2nd, then the maximum element is not in the second half, hence replace the right pointer with the mid pointer.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/734/1*5VeHvZvDJIs4CBFiQlip4Q.png" /><figcaption>3i) when <strong>mid ≤ smax_all</strong></figcaption></figure><p><strong>3 ii.</strong> If the second max element in the current search space is located in the first half of the array (i.e. mid &gt; smax_all), then find the second maximum element in the first half (i.e. smax_1st = object.query(left, mid)). If the second max elements in the entire array and the second max element in the 1st half of the array are equal (i.e. smax_all == smax_1st), then the maximum element in the array must be in the first half, hence discard the second half by replacing the right index with the mid pointer. However, if smax_all != smax_1st, then the maximum element is not in the first half, hence discard the first half by replacing the left pointer with the mid pointer.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/724/1*WMveLkQQ62_vsdEUjjYIhQ.png" /><figcaption>3ii) When <strong>mid &gt; smax_all</strong></figcaption></figure><p>At this point, the searched array is reduced to half. Recursively/iteratively apply the above steps until the difference between left and right pointers becomes 1, then return the pointer that was not recently updated. Below is the code implementation of the above steps.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/d90bc9262c5f87015e15cbc99b3f3b57/href">https://medium.com/media/d90bc9262c5f87015e15cbc99b3f3b57/href</a></iframe><p><strong>ANALYSIS OF APPROACH 1</strong><br>It is evident that the time complexity of the above approach is O(logn) since we used BS. However, our solution is evaluated by the number of queries we make. Since BS was used, it takes 17 splittings (i.e.log(10^5) = 17 , log is in base 2) to find the maximum element if the array size is 10⁵, which is the input upper bound. However, we used 2 queries every time we split the search space into 2. Based on APPROACH 1, a total of 34 (i.e. 2 * 17) queries would be required to find the max element in an array of size 10⁵ in the worst case. This is obviously against the constraint given in the problem statement (i.e. max of 20 queries). Can we do better than this? Can we do without 2 queries at every step?</p><p><strong>APPROACH 2 </strong>— Number of queries less than max queries allowed<br>In the first approach, we were using 2 queries to split the search space at every step. Do we actually need 2 queries to determine which half of the array to discard at every step?<br>Let’s understand why we needed 2 queries at every step. The first query ( smax_all) was used to identify the index of the second maximum element in the current search space, while the second query ( smax_1st or smax_2nd) was used to verify which half of the current search space to discard based on the the result of the first query. This means that the second query depends on the result of the first query. However, it is only the result of the second query that actually aids the splitting of the current search space. Can we do without the first query at every step? YES! We can.</p><p>If we know the location of the second max element at every step, there is no need for the first query. Notice that the second maximum element in the search space either changes (i.e. decreases) or remains the same after each step. For example, consider the array [1,2,8,4,9,3,40,21]. After the first step of the BS, the searched array reduces to [9,3,40,21] and the second maximum element (i.e. 21) does not change since both the max element and the second max element are on the same half of the array. Whereas, in this array [1,40,3,4,9,5,20,10], the second maximum element changes after the first step of the BS (i.e. [1,40,3,4] — second max changed from 20 to 4). How do we prevent the second maximum element from changing at every step and how can we benefit from that? Let us consider 2 scenarios;</p><p><strong>1ST SCENARIO</strong> — When the second maximum element in the original array is the first element in the subarray that contains the maximum element (i.e. [smax_all,right]). Before applying BS, the left pointer is equal to smax_all.<br><strong>How can we utilize this arrangement?</strong><br>Since we already know the position of the second maximum element, we only need one query, i.e. object.query(smax_all, mid), to reduce the search space by half. Anytime the result of the query is equal to the smax_all, then the max element must be located in the subarray [left, mid]and we can discard the other half [mid, right]. If the result of the query is not equal to smax_all, then the max element must be located in the subarray [mid, right] and we can exclude [left, mid] from the search space. We apply BS repeatedly on the searched space [left, right], finding the mid and always querying the second max element on[smax_all, mid] since it also contains the left half (i.e. [left, mid]). When the difference between right and left pointers become 1, we return the right since it would be pointing at the max element.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/975/1*O90F82NvbuZ054i4WaxVJQ.png" /><figcaption>When the smax is the first element in the subarray that contains the max element</figcaption></figure><p><strong>2ND SCENARIO</strong><br>When the <strong>second max</strong> element in the original array is the <strong>last </strong>element in the subarray that contains the maximum element (i.e. [left,smax_all]). Before applying BS, the right pointer is equal to smax_all.<br>This arrangement works like the first scenario but in opposite direction. We only need one query to split the search space by half at every step. <br>if object.query(mid , smax_all) == smax_all, then the max element must be located in the [mid, right] and we discard [left , mid], else we discard (mid, right]. When the difference between right pointer and left pointer becomes 1, we return the left pointer.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/981/1*-CasI1PEncDMC8r70FO7Gw.png" /><figcaption>When the smax is the last element in the subarray that contains the max element</figcaption></figure><p>If you read up to this point, KUDOS!<br>By the way, were you able to notice the problem with the second Approach? Recall that the first approach was using more queries than required (max of 34 queries instead of 20). So, the second approach is supposed to solve this problem of excess queries. We have discussed 2 scenarios where the second approach can be applied but as you may already notice, any input array is highly unlikely to have the second max element located either at its first or last position. In that case, how do we apply the second approach if the second max element in the array is <strong>neither </strong>in the first nor last position?<br>It turns out that we can fix this problem using only 2 queries. How? The pseudocode below explains;</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/e9f12f4506aee69a78c4aed49fba4d7d/href">https://medium.com/media/e9f12f4506aee69a78c4aed49fba4d7d/href</a></iframe><p><strong>ANALYSIS OF THE SECOND APPROACH</strong><br>We have successfully eliminated the use of 2 queries at every step of the BS.<br>However, we also introduced extra 2 queries to determine which scenario to take. In total, it will take a maximum of <strong>2 + Log(10^5) = 2 + 17 = 19</strong> queries when the array size is 10^5, which the input upper bound. Below is the Java code implementation of the second approach.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/759afd9b810e57bc398873e50fc2f30d/href">https://medium.com/media/759afd9b810e57bc398873e50fc2f30d/href</a></iframe><p><strong>CONCLUSION<br></strong>I would also like to add that if the max element in the array is not unique (i.e. if the array contains non-distinct values), the above approach would still return the index of one of the max elements. <a href="https://github.com/Wilson-Emmanuel/Medium-Posts">If you are interested to try this problem, I have created large randomly generated input test cases to test your solution. Also included is the implementation of the SecondMaximum blueprint in Java</a>.</p><p>It was really a long (and perhaps difficult) post and I believe, by getting this far, you have enjoyed it, and possibly learned something new about Binary Search. In your next searching journey, I suggest you check ways that BS could be used to solve the problem by studying the properties of the searched array or other information available to you even if your array is not sorted. In my subsequent post, I will be writing about other algorithmic problems that can be easily solved using BS even when it is not immediately clear that BS can be used. Thank you for taking the time to read this post. I hope you learned or relearned something.</p><p>Wilson Chuks :-)</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=96b6d2c9a547" width="1" height="1" alt=""><hr><p><a href="https://levelup.gitconnected.com/find-the-location-of-the-max-element-in-an-unsorted-array-using-binary-search-96b6d2c9a547">Find the Location of the Max Element in an Unsorted Array Using Binary Search</a> was originally published in <a href="https://levelup.gitconnected.com/">Level Up Coding</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
    </channel>
</rss>