<?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 Alkesh Ghorpade on Medium]]></title>
        <description><![CDATA[Stories by Alkesh Ghorpade on Medium]]></description>
        <link>https://medium.com/@alkesh26?source=rss-5b66f0dd7bcd------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/0*r7OnK51LUIOrY-ra.</url>
            <title>Stories by Alkesh Ghorpade on Medium</title>
            <link>https://medium.com/@alkesh26?source=rss-5b66f0dd7bcd------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Wed, 18 Nov 2026 16:14:51 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@alkesh26/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[Max Sum of Rectangle No Larger Than K]]></title>
            <link>https://alkesh26.medium.com/max-sum-of-rectangle-no-larger-than-k-83b7f94ccd12?source=rss-5b66f0dd7bcd------2</link>
            <guid isPermaLink="false">https://medium.com/p/83b7f94ccd12</guid>
            <category><![CDATA[javascript]]></category>
            <category><![CDATA[leetcode]]></category>
            <category><![CDATA[algorithms]]></category>
            <category><![CDATA[programming]]></category>
            <category><![CDATA[golang]]></category>
            <dc:creator><![CDATA[Alkesh Ghorpade]]></dc:creator>
            <pubDate>Thu, 29 Jun 2023 11:17:11 GMT</pubDate>
            <atom:updated>2023-07-05T03:44:13.929Z</atom:updated>
            <content:encoded><![CDATA[<h4>Given a non-empty 2D matrix and an integer k find the max sum of a rectangle in the matrix such that its sum is no larger than k</h4><h4>Problem Statement</h4><p>Given an m x n matrix matrix and an integer k, return <em>the max sum of a rectangle in the matrix such that its sum is no larger than k</em>.</p><p>It is <strong>guaranteed</strong> that there will be a rectangle with a sum no larger than k.</p><p>Problem statement taken from: <a href="https://leetcode.com/problems/max-sum-of-rectangle-no-larger-than-k">https://leetcode.com/problems/max-sum-of-rectangle-no-larger-than-k</a>.</p><p><strong>Example 1:</strong></p><figure><img alt="Container" src="https://cdn-images-1.medium.com/max/255/0*lP2QH0hyyasI8d5D.png" /></figure><pre>Input: matrix = [[1, 0, 1], [0, -2, 3]], k = 2<br>Output: 2<br>Explanation: Because the sum of the blue rectangle [[0, 1], [-2, 3]] is 2, and 2 is the max number no larger than k (k = 2).</pre><p><strong>Example 2:</strong></p><pre>Input: matrix = [[2, 2, -1]], k = 3<br>Output: 3</pre><p><strong>Constraints:</strong></p><pre>- m == matrix.length<br>- n == matrix[i].length<br>- 1 &lt;= m, n &lt;= 100<br>- -100 &lt;= matrix[i][j] &lt;= 100<br>- -10^5 &lt;= k &lt;= 10^5</pre><p><strong>Follow up:</strong> What if the number of rows is much larger than the number of columns?</p><h4>Solution</h4><h4>Approach 1: Brute force</h4><p>The naive approach is to check all the possible submatrices from the input matrix to compute the max sum of rectangles no larger than K. For each submatrix, we check if the sum of its elements is less than or equal to k or not. We store the sum of the submatrix no larger than k and return the answer.</p><p>A C++ solution of this approach is as follows:</p><pre>class Solution {<br>public:<br>    int maxSumSubmatrix(vector&lt;vector&lt;int&gt;&gt;&amp; matrix, int k) {<br>        int m = matrix.size();<br>        int n = matrix[0].size();<br>        int result = numeric_limits&lt;int&gt;::min();<br><br>        vector&lt;vector&lt;vector&lt;vector&lt;int&gt;&gt;&gt;&gt; computeSum(<br>            m,<br>            vector&lt;vector&lt;vector&lt;int&gt;&gt;&gt;(<br>                n,<br>                vector&lt;vector&lt;int&gt;&gt;(<br>                    m,<br>                    vector&lt;int&gt;(n, 0)<br>                )<br>            )<br>        );<br><br>        for (int rowLength = 0; rowLength &lt; m; ++ rowLength) {<br>            for (int columnLength = 0; columnLength &lt; n; ++columnLength) {<br>                for (int i = 0; i + rowLength &lt; m; ++i) {<br>                    for (int j = 0; j + columnLength &lt; n; ++j) {<br>                        if (rowLength == 0 &amp;&amp; columnLength == 0) {<br>                            computeSum[i][j][i + rowLength][j + columnLength] =<br>                                matrix[i][j];<br>                        } else if (rowLength == 0) {<br>                            computeSum[i][j][i + rowLength][j + columnLength] =<br>                                computeSum[i][j][i + rowLength][j + columnLength - 1]<br>                                +<br>                                matrix[i + rowLength][j + columnLength];<br>                        } else if (columnLength == 0) {<br>                            computeSum[i][j][i + rowLength][j + columnLength] =<br>                                computeSum[i][j][i + rowLength - 1][j + columnLength]<br>                                +<br>                                matrix[i + rowLength][j + columnLength];<br>                        } else {<br>                            computeSum[i][j][i + rowLength][j + columnLength] =<br>                                computeSum[i][j][i + rowLength - 1][j + columnLength]<br>                                +<br>                                computeSum[i][j][i + rowLength][j + columnLength - 1]<br>                                -<br>                                computeSum[i][j][i + rowLength - 1][j + columnLength - 1]<br>                                +<br>                                matrix[i + rowLength][j + columnLength];<br>                        }<br><br>                        if (computeSum[i][j][i + rowLength][j + columnLength] == k) {<br>                            return k;<br>                        } else if (computeSum[i][j][i + rowLength][j + columnLength] &lt; k) {<br>                            result = max(<br>                                result,<br>                                computeSum[i][j][i + rowLength][j + columnLength]<br>                            );<br>                        }<br>                    }<br>                }<br>            }<br>        }<br><br>        return result;<br>    }<br>};</pre><p>The time complexity of this approach is <strong>O(n ^ 4)</strong>. The solution will time out for a huge matrix, which is not the optimal way.</p><h4>Approach 2: Kanade algorithm</h4><p>We can optimize the brute force approach by using the concept of the Kanade algorithm. <strong>Kadane’s algorithm</strong> finds a maximum sum contiguous subarray for a one-dimensional array in <strong>O(n)</strong> time. Using this concept, we will create an integer array that stores each row’s prefix sums from column i to j where <strong>0 &lt; i &lt; j &lt; m</strong>. We will run Kadane’s algorithm on each such array to get the maximum possible sum closest to <strong>k</strong> of any subarray in the same way as we did in approach 1.</p><p>Please refer to this post <a href="https://alkeshghorpade.me/post/leetcode-maximum-subarray">Maximum Subarray</a> for understanding the <strong>Kanade algorithm</strong>.</p><p>Let’s check the algorithm.</p><h4>Algorithm</h4><pre>// maxSumSubmatrix(matrix, k)<br>- set m = matrix.length<br>      n = matrix[0].length<br>      result = INT_MIN<br><br>- loop for i = 0; i &lt; n; i++<br>  // initialize sum of size m with all values in it as 0<br>  - vector&lt;int&gt; sum(m, 0)<br><br>  - loop for j = i; j &lt; n; j++<br>    - loop for r = 0; r &lt; m; r++<br>      - update sum[r] = sum[r] + matrix[r][j]<br>    - for end<br>  - for end<br><br>  - set result = max(result, computeMaxSubarraySum(sum, k))<br>- for end<br><br>- return result<br><br>// computeMaxSubarraySum(sum, k)<br>- set currentSum = 0<br>      maxSum = INT_MIN<br><br>- create set sumValues and insert the value 0<br>  set&lt;int&gt; sumValues<br>  sumValues.insert(0)<br><br>- loop for i = 0; i &lt; sum.size; i++<br>  - update currentSum = currentSum + x<br><br>  - set auto it = sumValues.lower_bound(currentSum - k)<br><br>  - if it != sumValues.end()<br>    - update maxSum = max(maxSum, currentSum - *it)<br>  - if end<br><br>  - sumValues.insert(currentSum)<br>- for end<br><br>- return maxSum</pre><p>The time complexity of this approach is <strong>O(m * n ^ 2 * log(m))</strong>. Where m is the number of rows and n is the number of columns in the input matrix. The space complexity is <strong>O(n)</strong>.</p><p>Let’s check out our solutions in <strong>C++</strong>, <strong>Golang</strong>, and <strong>Javascript</strong>.</p><h4>C++ solution</h4><pre>class Solution {<br>public:<br>    int maxSumSubmatrix(vector&lt;vector&lt;int&gt;&gt;&amp; matrix, int k) {<br>        int m = matrix.size(), n = matrix[0].size();<br>        int result = INT_MIN;<br><br>        for(int i = 0; i &lt; n; i++) {<br>            vector&lt;int&gt; sum(m, 0);<br><br>            for(int j = i; j &lt; n; j++) {<br>                for(int r = 0; r &lt; m; r++) {<br>                    sum[r] += matrix[r][j];<br>                }<br><br>                result = max(result, computeMaxSubarraySum(sum, k));<br>            }<br>        }<br><br>        return result;<br>    }<br><br>    int computeMaxSubarraySum(vector&lt;int&gt; sum, int k) {<br>        int currentSum = 0;<br>        int maxSum = INT_MIN;<br>        set&lt;int&gt; sumValues;<br>        sumValues.insert(0);<br><br>        for(auto x: sum) {<br>            currentSum += x;<br><br>            auto it = sumValues.lower_bound(currentSum - k);<br>            if (it != sumValues.end()) {<br>                maxSum = max(maxSum, currentSum - *it);<br>            }<br><br>            sumValues.insert(currentSum);<br>        }<br><br>        return maxSum;<br>    }<br><br>};</pre><h4>Go solution</h4><pre>func maxSumSubmatrix(matrix [][]int, k int) int {<br> m, n := len(matrix), len(matrix[0])<br> sum := make([]int, n)<br> sumValues := make(sortedIntSet, n)<br> result := math.MinInt32<br><br> for startRow := range matrix {<br>  for i := range sum {<br>   sum[i] = 0<br>  }<br><br>  for row := startRow; row &lt; m; row++ {<br>   for col, val := range matrix[row] {<br>    sum[col] += val<br>   }<br><br>   currentSum := 0<br>   maxSum := sum[0]<br><br>            for _, val := range sum {<br>    currentSum = max(currentSum + val, val)<br>    maxSum = max(maxSum, currentSum)<br>   }<br><br>   if maxSum &lt;= k {<br>    result = max(result, maxSum)<br>    continue<br>   }<br><br>   currentSum = 0<br>   sumValues = sumValues[:1]<br>   sumValues[0] = 0<br><br>   for _, val := range sum {<br>    currentSum += val<br><br>    partnerIdx := sort.SearchInts(sumValues, currentSum-k)<br><br>                if partnerIdx != len(sumValues) {<br>     result = max(result, currentSum - sumValues[partnerIdx])<br>    }<br><br>    sumValues.insert(currentSum)<br>   }<br>  }<br> }<br><br> return result<br>}<br><br>func max(a, b int) int {<br> if a &gt; b {<br>  return a<br> }<br> return b<br>}<br><br>type sortedIntSet []int<br><br>func (s *sortedIntSet) insert(x int) {<br> i := sort.SearchInts(*s, x)<br><br>    if i == len(*s) {<br>  *s = append(*s, x)<br> } else if (*s)[i] != x {<br>  *s = append(*s, 0)<br>  copy((*s)[i+1:], (*s)[i:])<br>  (*s)[i] = x<br> }<br>}</pre><h4>JavaScript solution</h4><pre>/**<br> * @param {number[][]} matrix<br> * @param {number} k<br> * @return {number}<br> */<br>var maxSumSubmatrix = function(matrix, k) {<br>    let m = matrix.length, n = matrix[0].length;<br>    let result = Number.MIN_VALUE;<br><br>    for(let i = 0; i &lt; n; i++) {<br>        let sum = new Array(m).fill(0);<br><br>        for(let j = i; j &lt; n; j++) {<br>            for(let r = 0; r &lt; m; r++) {<br>                sum[r] += matrix[r][j];<br>            }<br><br>            result = Math.max(result, computeMaxSubarraySum(sum, k));<br>        }<br>    }<br><br>    return result;<br>};<br><br>var computeMaxSubarraySum = function(sum, k) {<br>    let currentSum = 0;<br>    let maxSum = Number.MIN_VALUE;<br>    let sumValues = new Set();<br>    sumValues.add(0);<br><br>    for(let r = 0; r &lt; sum.length; r++) {<br>        currentSum += sum[r];<br><br>        let list = Array.from(sumValues);<br>        let it = list.lastIndexOf(currentSum - k)<br><br>        if (it &gt; -1) {<br>            maxSum = Math.max(maxSum, currentSum - it);<br>        }<br><br>        sumValues.add(currentSum);<br>    }<br><br>    return maxSum;<br>};</pre><h4>Dry Run</h4><p>Let’s dry-run our algorithm to see how the solution works.</p><pre>Input: matrix = [[1, 0, 1], [0, -2, 3]]<br>       k = 2<br><br>// maxSumSubmatrix(matrix, k)<br>Step 1: m = matrix.size()<br>          = 2<br>        n = matrix[0].size()<br>          = 3<br>        result = INT_MIN<br><br>Step 2: loop for i = 0; i &lt; n<br>          0 &lt; 3<br>          true<br><br>          vector&lt;int&gt; sum(m, 0)<br>          sum = [0, 0]<br><br>          loop for j = i; j &lt; n; j++<br>            loop for r = 0; r &lt; m; r++<br>              sum[r] = sum[r] + matrix[r][j]<br>            for end<br>          for end<br><br>          so after the above loop<br>          sum = [1, 0]<br><br>          result = max(result, computeMaxSubarraySum(sum, k))<br><br>// computeMaxSubarraySum(sum, 2)<br>// computeMaxSubarraySum([1, 0], 2)<br>Step 3: set currentSum = 0<br>            maxSum = INT_MIN<br>            set&lt;int&gt; sumValues<br>            sumValues.insert(0)<br><br>            loop for auto x: sum<br>              currentSum = currentSum + x<br>                         = 0 + 1<br>                         = 1<br><br>              sumValues = [0]<br>              it = sumValues.lower_bound(currentSum - k)<br>                 = sumValues.lower_bound(1 - 2)<br>                 = sumValues.lower_bound(-1)<br>                 = -1<br><br>              sumValues.add(currentSum)<br>              sumValues.add(1)<br>              sumValues = [0, 1]<br><br>            loop for auto x: sum<br>              currentSum = currentSum + x<br>                         = 1 + 0<br>                         = 1<br><br>              sumValues = [0, 1]<br>              it = sumValues.lower_bound(currentSum - k)<br>                 = sumValues.lower_bound(1 - 2)<br>                 = sumValues.lower_bound(-1)<br>                 = -1<br><br>Step 4: return maxSum<br>        return INT_MIN<br><br>// maxSumSubmatrix(matrix, k)<br>Step 5: result = max(result, computeMaxSubarraySum(sum, k))<br>               = max(INT_MIN, INT_MIN)<br>               = INT_MIN<br>        i++<br>        i = 1<br><br>Step 6: loop for i &lt; n<br>          1 &lt; 3<br>          true<br><br>          vector&lt;int&gt; sum(m, 0)<br>          sum = [0, 0]<br><br>          loop for j = i; j &lt; n; j++<br>            loop for r = 0; r &lt; m; r++<br>              sum[r] = sum[r] + matrix[r][j]<br>            for end<br>          for end<br><br>          so after the above loop<br>          sum = [0, -2]<br><br>          result = max(result, computeMaxSubarraySum(sum, k))<br><br>We compute the same steps for the whole matrix.<br><br>We return the result, and the answer is 2.</pre><p><em>Originally posted at </em><a href="https://alkeshghorpade.me/post/leetcode-max-sum-of-rectangle-no-larger-than-k"><em>https://alkeshghorpade.me</em></a><em>.</em></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=83b7f94ccd12" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Maximum Gap]]></title>
            <link>https://alkesh26.medium.com/maximum-gap-d676cf2ff433?source=rss-5b66f0dd7bcd------2</link>
            <guid isPermaLink="false">https://medium.com/p/d676cf2ff433</guid>
            <category><![CDATA[golang]]></category>
            <category><![CDATA[algorithms]]></category>
            <category><![CDATA[leetcode]]></category>
            <category><![CDATA[programming]]></category>
            <category><![CDATA[javascript]]></category>
            <dc:creator><![CDATA[Alkesh Ghorpade]]></dc:creator>
            <pubDate>Sun, 25 Jun 2023 15:24:56 GMT</pubDate>
            <atom:updated>2023-07-05T03:46:30.773Z</atom:updated>
            <content:encoded><![CDATA[<h4>Given an integer array nums return the maximum difference between two successive elements in its sorted form.</h4><p><strong>Problem statement</strong></p><p>Given an integer array nums, return <em>the maximum difference between two successive elements in its sorted form</em>. If the array contains less than two elements, return 0.</p><p>You must write an algorithm that runs in linear time and uses linear extra space.</p><p>Problem statement taken from: <a href="https://leetcode.com/problems/maximum-gap">https://leetcode.com/problems/maximum-gap</a>.</p><p><strong>Example 1:</strong></p><pre>Input: nums = [3, 6, 9, 1]<br>Output: 3<br>Explanation: The sorted form of the array is [1, 3, 6, 9], either (3, 6) or (6, 9) has the maximum difference 3.</pre><p><strong>Example 2:</strong></p><pre>Input: nums = [10]<br>Output: 0<br>Explanation: The array contains less than 2 elements, therefore return 0.</pre><p><strong>Constraints:</strong></p><pre>- 1 &lt;= nums.length &lt;= 10^5<br>- 0 &lt;= nums[i] &lt;= 10^9</pre><h4>Solution</h4><h4>Approach 1: Brute force</h4><p>The brute force approach sorts the array and finds the maximum difference between two adjacent elements. The time complexity of this approach is <strong>O(n)</strong>, and the space complexity is <strong>O(1)</strong>.</p><p>A C++ snippet of this approach is as below:</p><pre>int maximumGap(vector&lt;int&gt;&amp; nums) {<br>    int n = nums.size();<br><br>    if(n &lt;= 1) {<br>        return 0;<br>    }<br><br>    sort(nums.begin(), nums.end());<br>    int maxDifference = INT_MIN;<br><br>    for(int i = 0; i &lt; n - 1; i++) {<br>        maxDifference = max(maxDifference, nums[i + 1] - nums[i]);<br>    }<br><br>    return maxDifference;<br>}</pre><h4>Approach 2: Pigeonhole Sorting</h4><p>The problem statement mentions solving the problem in linear time, using linear extra space. We can use the concept of <a href="https://en.wikipedia.org/wiki/Pigeonhole_sort">Pigeonhole Sorting</a>. Pigeonhole algorithm is suitable for sorting lists of elements where the number of elements and possible key values is approximately the same. It requires <strong>O(n + Range)</strong> time, where n is the number of elements in the input array and Range is the number of possible values in the array.</p><p>The flow of this algorithm is as follows:</p><pre>- Find the minimum and maximum values in the array. We get the difference between the maximum and minimum value, which we call range. `range = maximum - minimum + 1`.<br><br>- Create an array of empty values (pigeonholes) with a size range.<br><br>- Iterate over the input array and insert each element in its pigeonhole. An element nums[i] is inserted in the hole at index nums[i] - min.<br><br>- Iterate over the pigeonhole array in order and insert the elements from the non-empty pigeonhole back into the original array.</pre><p>We apply the above approach to find the maximum gap between two successive elements in the sorted array.</p><p>Let’s check the algorithm.</p><h4>Algorithm</h4><pre>- set maximum = nums[0]<br>      minimum = nums[0]<br>      n = nums.size()<br><br>- if n &lt;= 1<br>  - return 0<br>- end if<br><br>- loop for i = 1; i &lt; n; i++<br>  // set maximum and minimum<br>  - maximum = max(maximum, nums[i])<br>  - minimum = min(minimum, nums[i])<br>- end for<br><br>// create arrays to store maximum and minimum values in n-1 buckets of range<br>- vector&lt;int&gt; maxBucket(n - 1, INT_MIN)<br>- vector&lt;int&gt; minBucket(n - 1, INT_MAX)<br><br>// calculate the range<br>- range = ceil((maximum - minimum) / (n - 1))<br><br>// traverse through the input array and insert the element in the appropriate bucket<br>// if the bucket is empty else, update bucket values<br>- loop for i = 0; i &lt; n; i++<br>  - if nums[i] == maximum || nums[i] == minimum<br>    - continue<br>  - end if<br><br>  // compute the index of the bucket<br>  - index = ((nums[i] - minimum) / range)<br><br>  - maxBucket[index] = max(maxBucket[index], nums[i])<br>  - minBucket[index] = min(minBucket[index], nums[i])<br>- end for<br><br>// find the maximum gap between the maximum value<br>// of the previous bucket minus a minimum of the current bucket.<br>- set previousValue = minimum<br>      maximumGap = 0<br><br>- loop for i = 0; i &lt; n - 1; i++<br>  - if minBucket[i] == INT_MAX<br>    - continue<br>  - end if<br><br>  - maximumGap = max(maximumGap, minBucket[i] - previousValue)<br>  - previousValue = maxBucket[i]<br>- end for<br><br>- set maximumGap = max(maximumGap, maximum - previousValue)<br><br>- return maximumGap</pre><p>The time complexity of this approach is <strong>O(n)</strong>, and the space complexity if <strong>O(n)</strong>.</p><p>Let’s check out our solutions in <strong>C++</strong>, <strong>Golang</strong>, and <strong>Javascript</strong>.</p><h4>C++ solution</h4><pre>class Solution {<br>public:<br>    int maximumGap(vector&lt;int&gt;&amp; nums) {<br>        int maximum = nums[0], minimum = nums[0];<br>        int n = nums.size(), i;<br><br>        if(n &lt;= 1) {<br>            return 0;<br>        }<br><br>        // find the maximum and minimum in nums[]<br>        for(int i = 1; i &lt; n; i++) {<br>            maximum = max(maximum, nums[i]);<br>            minimum = min(minimum, nums[i]);<br>        }<br><br>        // create arrays to store maximum and minimum values in n-1 buckets of range.<br>        vector&lt;int&gt; maxBucket(n - 1, INT_MIN);<br>        vector&lt;int&gt; minBucket(n - 1, INT_MAX);<br><br>        // calculate the range<br>        int range = ceil((maximum - minimum) / (n - 1));<br><br>        // traverse through the input array and insert the element in the appropriate bucket<br>        // if the bucket is empty else, update bucket values<br>        for (i = 0; i &lt; n; i++) {<br>            if (nums[i] == maximum || nums[i] == minimum)<br>                continue;<br><br>            // compute the index of the bucket<br>            int index = ((nums[i] - minimum) / range);<br><br>            maxBucket[index] = max(maxBucket[index], nums[i]);<br>            minBucket[index] = min(minBucket[index], nums[i]);<br>        }<br><br>        // find the maximum gap between the maximum value<br>        // of the previous bucket minus a minimum of the current bucket.<br>        int previousValue = minimum;<br>        int maximumGap = 0;<br><br>        for (i = 0; i &lt; n - 1; i++) {<br>            if (minBucket[i] == INT_MAX)<br>                continue;<br><br>            maximumGap = max(maximumGap, minBucket[i] - previousValue);<br>            previousValue = maxBucket[i];<br>        }<br><br>        maximumGap = max(maximumGap, maximum - previousValue);<br><br>        return maximumGap;<br>    }<br>};</pre><h4>Go solution</h4><pre>func maximumGap(nums []int) int {<br>    maximum, minimum := nums[0], nums[0]<br>    n, i := len(nums), 0<br><br>    if n &lt;= 1 {<br>        return 0<br>    }<br><br>    // find the maximum and minimum in nums[]<br>    for i = 1; i &lt; n; i++ {<br>        maximum = max(maximum, nums[i])<br>        minimum = min(minimum, nums[i])<br>    }<br><br>    // create arrays to store maximum and minimum values in n-1 buckets of range.<br>    maxBucket := make([]int, n - 1)<br>    minBucket := make([]int, n - 1)<br><br>    for j := range maxBucket {<br>        maxBucket[j] = math.MinInt32<br>        minBucket[j] = math.MaxInt32<br>    }<br><br>    // calculate the range<br>    rangeValue := int(math.Ceil(float64(maximum - minimum) / float64(n - 1)))<br><br>    // traverse through the input array and insert the element in the appropriate bucket<br>    // if the bucket is empty else, update bucket values<br>    for i = 0; i &lt; n; i++ {<br>        if nums[i] == maximum || nums[i] == minimum {<br>            continue<br>        }<br><br>        index := ((nums[i] - minimum) / rangeValue)<br><br>        maxBucket[index] = max(maxBucket[index], nums[i])<br>        minBucket[index] = min(minBucket[index], nums[i])<br>    }<br><br>    // find the maximum gap between the maximum value<br>    // of the previous bucket minus a minimum of the current bucket<br>    previousValue, maximumGap := minimum, 0<br><br>    for i = 0; i &lt; n - 1; i++ {<br>        if minBucket[i] == math.MaxInt32 {<br>            continue<br>        }<br><br>        maximumGap = max(maximumGap, minBucket[i] - previousValue)<br>        previousValue = maxBucket[i]<br>    }<br><br>    return max(maximumGap, maximum - previousValue)<br>}<br><br>func max(a, b int) int {<br>    if a &gt; b {<br>        return a<br>    }<br><br>    return b<br>}<br><br>func min(a, b int) int {<br>    if a &lt; b {<br>        return a<br>    }<br><br>    return b<br>}</pre><h4>JavaScript solution</h4><pre>/**<br> * @param {number[]} nums<br> * @return {number}<br> */<br>var maximumGap = function(nums) {<br>    let maximum = nums[0], minimum = nums[0];<br>    let n = nums.length, i;<br><br>    if(n &lt;= 1) {<br>        return 0;<br>    }<br><br>    // find the maximum and minimum in nums[]<br>    for(i = 1; i &lt; n; i++) {<br>        maximum = Math.max(maximum, nums[i]);<br>        minimum = Math.min(minimum, nums[i]);<br>    }<br><br>    // create arrays to store maximum and minimum values in n-1 buckets of range.<br>    let maxBucket = new Array(n - 1).fill(Number.MIN_SAFE_INTEGER);<br>    let minBucket = new Array(n - 1).fill(Number.MAX_SAFE_INTEGER);<br><br>    // calculate the range<br>    let range = Math.ceil((maximum - minimum) / (n - 1));<br><br>    // traverse through the input array and insert the element in the appropriate bucket<br>    // if the bucket is empty else, update bucket values<br>    for (i = 0; i &lt; n; i++) {<br>        if (nums[i] == maximum || nums[i] == minimum)<br>            continue;<br><br>        // compute the index of the bucket<br>        let index = ((nums[i] - minimum) / range);<br><br>        maxBucket[index] = Math.max(maxBucket[index], nums[i]);<br>        minBucket[index] = Math.min(minBucket[index], nums[i]);<br>    }<br><br>    // find the maximum gap between the maximum value<br>    // of the previous bucket minus a minimum of the current bucket.<br>    let previousValue = minimum;<br>    let maximumGap = 0;<br><br>    for (i = 0; i &lt; n - 1; i++) {<br>        if (minBucket[i] == Number.MAX_SAFE_INTEGER)<br>            continue;<br><br>        maximumGap = Math.max(maximumGap, minBucket[i] - previousValue);<br>        previousValue = maxBucket[i];<br>    }<br><br>    maximumGap = Math.max(maximumGap, maximum - previousValue);<br><br>    return maximumGap;<br>};</pre><h4>Dry Run</h4><p>Let’s dry-run our algorithm to see how the solution works.</p><pre>Input: nums = [3, 6, 9, 1]<br><br>Step 1: maximum = nums[0]<br>                = 3<br>        minimum = nums[0]<br>                = 3<br>        n = nums.size()<br>          = 4<br><br>Step 2: if n &lt;= 1<br>           4 &lt;= 1<br>           false<br><br>Step 3: // find the maximum and minimum in nums[]<br>        loop for int i = 1; i &lt; n; i++<br><br>        // at the end of this loop we get max<br>        // and min<br>        maximum = 9<br>        minimum = 1<br><br>Step 4: vector&lt;int&gt; maxBucket(n - 1, INT_MIN)<br>        maxBucket = [INT_MIN, INT_MIN, INT_MIN]<br><br>        vector&lt;int&gt; minBucket(n - 1, INT_MAX)<br>        minBucket = [INT_MAX, INT_MAX, INT_MAX]<br><br>Step 5: range = ceil((maximum - minimum) / (n - 1))<br>              = ceil(9 - 1 / 4 - 1)<br>              = ceil(8 / 3)<br>              = 2<br><br>Step 6: loop for i = 0; i &lt; n<br>          0 &lt; 4<br>          true<br><br>          if nums[i] == maximum || nums[i] == minimum<br>             nums[0] == 9 || nums[0] == 1<br>             3 == 9 || 3 == 1<br>             false<br><br>          index = ((nums[i] - minimum) / range)<br>                = ((nums[0] - 1) / 2)<br>                = (3 - 1) / 2<br>                = 1<br><br>          maxBucket[index] = max(maxBucket[index], nums[i])<br>          maxBucket[1] = max(maxBucket[1], nums[0])<br>                       = max(INT_MIN, 3)<br>                       = 3<br>          maxBucket = [INT_MIN, 3, INT_MIN]<br><br>          minBucket[index] = min(minBucket[index], nums[i])<br>          minBucket[1] = max(minBucket[1], nums[0])<br>                       = max(INT_MAX, 3)<br>                       = 3<br>          minBucket = [INT_MAX, 3, INT_MIN]<br><br>          i++<br>          i = 1<br><br>        loop for i &lt; 4<br>          1 &lt; 4<br>          true<br><br>          if nums[i] == maximum || nums[i] == minimum<br>            nums[1] == 9 || nums[1] == 1<br>            6 == 9 || 6 == 1<br>            false<br><br>          index = ((nums[i] - minimum) / range)<br>                = ((nums[1] - 1) / 2)<br>                = (6 - 1) / 2<br>                = 2<br><br>          maxBucket[index] = max(maxBucket[index], nums[i])<br>          maxBucket[2] = max(maxBucket[2], nums[1])<br>                       = max(INT_MIN, 6)<br>                       = 6<br>          maxBucket = [INT_MIN, 3, 6]<br><br>          minBucket[index] = min(minBucket[index], nums[i])<br>          minBucket[2] = max(minBucket[2], nums[1])<br>                       = max(INT_MAX, 6)<br>                       = 6<br>          minBucket = [INT_MAX, 3, 6]<br><br>          i++<br>          i = 2<br><br>        loop for i &lt; 4<br>          2 &lt; 4<br>          true<br><br>          if nums[i] == maximum || nums[i] == minimum<br>            nums[2] == 9 || nums[2] == 1<br>            9 == 9 || 9 == 1<br>            true<br>            continue<br><br>          i++<br>          i = 3<br><br>        loop for i &lt; 4<br>          3 &lt; 4<br>          true<br><br>          if nums[i] == maximum || nums[i] == minimum<br>            nums[3] == 9 || nums[3] == 1<br>            1 == 9 || 1 == 1<br>            true<br>            continue<br><br>          i++<br>          i = 4<br><br>        loop for i &lt; 4<br>          4 &lt; 4<br>          false<br><br>Step 7: previousValue = minimum<br>                      = 1<br>        maximumGap = 0<br><br>Step 8: loop for i = 0; i &lt; n - 1<br>          0 &lt; 4 - 1<br>          0 &lt; 3<br>          true<br><br>          if minBucket[i] == INT_MAX<br>             minBucket[0] == INT_MAX<br>             true<br><br>             continue<br><br>          i++<br>          i = 1<br><br>        loop for i &lt; n - 1<br>          1 &lt; 4 - 1<br>          1 &lt; 3<br>          true<br><br>          if minBucket[i] == INT_MAX<br>             minBucket[1] == INT_MAX<br>             3 == INT_MAX<br>             false<br><br>          maximumGap = max(maximumGap, minBucket[i] - previousValue)<br>                     = max(0, minBucket[1] - previousValue)<br>                     = max(0, 3 - 1)<br>                     = max(0, 2)<br>                     = 2<br><br>          previousValue = maxBucket[i]<br>                        = maxBucket[1]<br>                        = 3<br><br>          i++<br>          i = 2<br><br>        loop for i &lt; n - 1<br>          2 &lt; 4 - 1<br>          2 &lt; 3<br>          true<br><br>          if minBucket[i] == INT_MAX<br>             minBucket[1] == INT_MAX<br>             6 == INT_MAX<br>             false<br><br>          maximumGap = max(maximumGap, minBucket[i] - previousValue)<br>                     = max(2, minBucket[2] - previousValue)<br>                     = max(2, 6 - 3)<br>                     = max(2, 3)<br>                     = 3<br><br>          previousValue = maxBucket[i]<br>                        = maxBucket[2]<br>                        = 6<br><br>          i++<br>          i = 3<br><br>        loop for i &lt; n - 1<br>          3 &lt; 4 - 1<br>          3 &lt; 3<br>          false<br><br>Step 9: maximumGap = max(maximumGap, maximum - previousValue)<br>                   = max(3, 9 - 6)<br>                   = max(3, 3)<br>                   = 3<br><br>Step 10: return maximumGap<br><br>We return the answer as 3.</pre><p><em>Originally posted at </em><a href="https://alkeshghorpade.me/post/leetcode-maximum-gap"><em>https://alkeshghorpade.me</em></a><em>.</em></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=d676cf2ff433" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Odd Even Linked List]]></title>
            <link>https://alkesh26.medium.com/odd-even-linked-list-7e4cf608e8bd?source=rss-5b66f0dd7bcd------2</link>
            <guid isPermaLink="false">https://medium.com/p/7e4cf608e8bd</guid>
            <category><![CDATA[programming]]></category>
            <category><![CDATA[leetcode]]></category>
            <category><![CDATA[javascript]]></category>
            <category><![CDATA[golang]]></category>
            <category><![CDATA[algorithms]]></category>
            <dc:creator><![CDATA[Alkesh Ghorpade]]></dc:creator>
            <pubDate>Thu, 22 Jun 2023 12:28:45 GMT</pubDate>
            <atom:updated>2023-07-05T03:47:00.275Z</atom:updated>
            <content:encoded><![CDATA[<h4>Problem statement</h4><p>Given the head of a singly linked list, group all the nodes with odd indices together followed by the nodes with even indices, and return <em>the reordered list</em>.</p><p>The <strong>first</strong> node is considered <strong>odd</strong>, and the <strong>second</strong> node is <strong>even</strong>, and so on.</p><p>Note that the relative order inside both the even and odd groups should remain as it was in the input.</p><p>You must solve the problem in O(1) extra space complexity and O(n) time complexity.</p><p>Problem statement taken from: <a href="https://leetcode.com/problems/odd-even-linked-list">https://leetcode.com/problems/odd-even-linked-list</a>.</p><p><strong>Example 1:</strong></p><figure><img alt="Container" src="https://cdn-images-1.medium.com/max/542/0*4cqk9iA86nzPHna3.png" /></figure><pre>Input: head = [1, 2, 3, 4, 5]<br>Output: [1, 3, 5, 2, 4]</pre><p><strong>Example 2:</strong></p><figure><img alt="Container" src="https://cdn-images-1.medium.com/max/782/0*eeuGPGJ7tk9G92lD.png" /></figure><pre>Input: head = [2, 1, 3, 5, 6, 4, 7]<br>Output: [2, 3, 6, 7, 1, 5, 4]</pre><p><strong>Constraints:</strong></p><pre>- The number of nodes in the linked list is in the range [0, 10^4].<br>- -10^6 &lt;= Node.val &lt;= 10^6</pre><h4>Solution</h4><h4>Approach 1: Using additional</h4><p>The naive approach is to create two separate linked lists, one for the odd-indices nodes and the other for the even-indices nodes. We iterate the original linked list, and for each node, we will check the node’s position using a counter. If the linked list position node is odd, we append it to the odd-indices linked list, or if the position is even, we append it to the even-indices linked list. Once the complete linked list is traversed, we append the even-indices linked list at the end of the odd-indices linked list.</p><p>A C++ snippet of this approach is as follows:</p><pre>ListNode* oddEvenList(ListNode* head) {<br>    // initialize oddHead and evenHead pointers<br>    ListNode* oddHead = new ListNode(0);<br>    ListNode* odd = oddHead;<br>    ListNode* evenHead = new ListNode(0);<br>    ListNode* even = evenHead;<br>    ListNode* currend = head;<br>    int counter = 1;<br><br>    // traverse the linked list till the end<br>    while(current) {<br>        // odd-indices node<br>        if(counter % 2 == 1) {<br>            odd-&gt;next = current;<br>            odd = odd-&gt;next;<br>        } else {<br>            // even-indices node<br>            even-&gt;next = current;<br>            even = even-&gt;next;<br>        }<br><br>        current = current-&gt;next;<br>        counter++;<br>    }<br><br>    // append even-indices linked list<br>    // at the end of the odd-indices linked list<br>    odd-&gt;next = evenHead-&gt;next;<br>    even-&gt;next = NULL;<br><br>    return oddHead-&gt;next;<br>};</pre><p>The time complexity of the above algorithm is <strong>O(n)</strong>, and the space complexity is <strong>O(1)</strong>.</p><h4>Approach 2: Sorting in-place</h4><p>We can tweak the above algorithm to solve the odd-even linked list problem. The counter variable can be eliminated, and instead of pointing the oddHead and evenHead to a new node, we can point them to head and head-&gt;next, respectively.</p><p>When working on the solution, it’s important to ensure we are covering all the edge cases.</p><ol><li>Empty linked list or a linked list with a single node.</li><li>A linked list with only two nodes.</li><li>A linked list with odd numbers of nodes.</li><li>A linked list with an even number of nodes.</li></ol><p>Let’s check the algorithm first.</p><h4>Algorithm</h4><pre>// if the list is empty or has only one node<br>- if head == NULL || head-&gt;next == NULL<br>  - return head<br>- end if<br><br>// initialize the odd and even pointers<br>- oddPointer = head<br>  evenPointer = head-&gt;next<br>  evenHead = head-&gt;next<br><br>// loop while even pointer is not NULL<br>// or even pointer next is not NULL<br>- loop while evenPointer != NULL &amp;&amp; evenPointer-&gt;next != NULL<br><br>  // skip the next node and point the current odd index node to<br>  // the next odd index node<br>  - oddPointer-&gt;next = oddPointer-&gt;next-&gt;next<br>  - oddPointer = oddPointer-&gt;next<br><br>  // skip the next node and point the current even index node to<br>  // the even odd index node<br>  - evenPointer-&gt;next = evenPointer-&gt;next-&gt;next<br>  - evenPointer = evenPointer-&gt;next<br>- while end<br><br>- oddPointer-&gt;next = evenHead<br><br>- return head</pre><p>We initialized three-pointers oddPointer, evenPointer and evenHead. oddPointer will point to the head and the evenPointer will point to the head&#39;s next node. In each iteration, the oddPointer and evenPointer will skip the next node point to the next odd and even index node. Once the iteration over the linked list is done, we point the oddPointer next to the start of evenHead.</p><p>The time complexity of the above algorithm is <strong>O(n)</strong>, and the space complexity is <strong>O(1)</strong>.</p><p>Let’s check out our solutions in <strong>C++</strong>, <strong>Golang</strong>, and <strong>Javascript</strong>.</p><h4>C++ solution</h4><pre>/**<br> * Definition for singly-linked list.<br> * struct ListNode {<br> *     int val;<br> *     ListNode *next;<br> *     ListNode() : val(0), next(nullptr) {}<br> *     ListNode(int x) : val(x), next(nullptr) {}<br> *     ListNode(int x, ListNode *next) : val(x), next(next) {}<br> * };<br> */<br>class Solution {<br>public:<br>    ListNode* oddEvenList(ListNode* head) {<br>        // if the list is empty or has only one node<br>        if(head == NULL || head-&gt;next == NULL) {<br>            return head;<br>        }<br><br>        // initialize the odd and even pointers<br>        ListNode* oddPointer = head;<br>        ListNode* evenPointer = head-&gt;next;<br>        ListNode* evenHead = head-&gt;next;<br><br>        // loop while even pointer is not NULL<br>        // or even pointer next is not NULL<br>        while(evenPointer != NULL &amp;&amp; evenPointer-&gt;next != NULL) {<br><br>            // skip the next node and point the current odd index node to<br>            // the next odd index node<br>            oddPointer-&gt;next = oddPointer-&gt;next-&gt;next;<br>            oddPointer = oddPointer-&gt;next;<br><br>            // skip the next node and point the current even index node to<br>            // the even odd index node<br>            evenPointer-&gt;next = evenPointer-&gt;next-&gt;next;<br>            evenPointer = evenPointer-&gt;next;<br>        }<br><br>        oddPointer-&gt;next = evenHead;<br><br>        return head;<br>    }<br>};</pre><h4>Go solution</h4><pre>/**<br> * Definition for singly-linked list.<br> * type ListNode struct {<br> *     Val int<br> *     Next *ListNode<br> * }<br> */<br>func oddEvenList(head *ListNode) *ListNode {<br>    // if the list is empty or has only one node<br>    if head == nil || head.Next == nil {<br>        return head<br>    }<br><br>    // initialize the odd and even pointers<br>    oddPointer, evenPointer, evenHead := head, head.Next, head.Next<br><br>    // loop while even pointer is not NULL<br>    // or even pointer next is not NULL<br>    for evenPointer != nil &amp;&amp; evenPointer.Next != nil {<br>        // skip the next node and point the current odd index node to<br>        // the next odd index node<br>        oddPointer.Next = oddPointer.Next.Next<br>        oddPointer = oddPointer.Next<br><br>        // skip the next node and point the current even index node to<br>        // the even odd index node<br>        evenPointer.Next = evenPointer.Next.Next<br>        evenPointer = evenPointer.Next<br>    }<br><br>    oddPointer.Next = evenHead<br><br>    return head<br>}</pre><h4>JavaScript solution</h4><pre>/**<br> * Definition for singly-linked list.<br> * function ListNode(val, next) {<br> *     this.val = (val===undefined ? 0 : val)<br> *     this.next = (next===undefined ? null : next)<br> * }<br> */<br>/**<br> * @param {ListNode} head<br> * @return {ListNode}<br> */<br>var oddEvenList = function(head) {<br>    // if the list is empty or has only one node<br>    if(head == null || head.next == null) {<br>        return head;<br>    }<br><br>    // initialize the odd and even pointers<br>    let oddPointer = head;<br>    let evenPointer = head.next;<br>    let evenHead = head.next;<br><br>    // loop while even pointer is not NULL<br>    // or even pointer next is not NULL<br>    while(evenPointer != null &amp;&amp; evenPointer.next != null) {<br>        // skip the next node and point the current odd index node to<br>        // the next odd index node<br>        oddPointer.next = oddPointer.next.next;<br>        oddPointer = oddPointer.next;<br><br>        // skip the next node and point the current even index node to<br>        // the even odd index node<br>        evenPointer.next = evenPointer.next.next;<br>        evenPointer = evenPointer.next;<br>    }<br><br>    oddPointer.next = evenHead;<br><br>    return head;<br>};</pre><h4>Dry Run</h4><p>Let’s dry-run our algorithm to see how the solution works.</p><pre>Input: head = [1, 2, 3, 4, 5]<br><br>Step 1: if head == NULL || head-&gt;next == NULL<br>           head -&gt; 1<br>           head-&gt;next -&gt; 2<br>           false<br><br>Step 2: ListNode* oddPointer = head<br>                  oddPointer -&gt; 1<br><br>        ListNode* evenPointer = head-&gt;next<br>                  evenPointer -&gt; 2<br><br>        ListNode* evenHead = head-&gt;next<br>                  evenHead -&gt; 2<br><br>Step 3: loop while evenPointer != NULL &amp;&amp; evenPointer-&gt;next != NULL<br>          evenPointer -&gt; 2<br>          evenPointer-&gt;next -&gt; 4<br><br>          2 != NULL &amp;&amp; 4 != NULL<br>          true<br><br>          oddPointer-&gt;next = oddPointer-&gt;next-&gt;next<br>          oddPointer-&gt;next -&gt; 2<br>          oddPointer-&gt;next-&gt;next -&gt; 3<br><br>          oddPointer -&gt; 1 -&gt; 3<br><br>          oddPointer = oddPointer-&gt;next<br>          oddPointer -&gt; 3<br><br>          evenPointer-&gt;next = evenPointer-&gt;next-&gt;next<br>          evenPointer-&gt;next -&gt; 3<br>          evenPointer-&gt;next-&gt;next -&gt; 4<br><br>          evenPointer -&gt; 2 -&gt; 4<br><br>          evenPointer = evenPointer-&gt;next<br>          evenPointer -&gt; 4<br><br>Step 4: loop while evenPointer != NULL &amp;&amp; evenPointer-&gt;next != NULL<br>          evenPointer -&gt; 4<br>          evenPointer-&gt;next -&gt; 5<br><br>          2 != NULL &amp;&amp; 5 != NULL<br>          true<br><br>          oddPointer-&gt;next = oddPointer-&gt;next-&gt;next<br>          oddPointer-&gt;next -&gt; 4<br>          oddPointer-&gt;next-&gt;next -&gt; 5<br><br>          oddPointer -&gt; 1 -&gt; 3 -&gt; 5<br><br>          oddPointer = oddPointer-&gt;next<br>          oddPointer -&gt; 5<br><br>          evenPointer-&gt;next = evenPointer-&gt;next-&gt;next<br>          evenPointer-&gt;next -&gt; 5<br>          evenPointer-&gt;next-&gt;next -&gt; NULL<br><br>          evenPointer -&gt; 2 -&gt; 4 -&gt; NULL<br><br>          evenPointer = evenPointer-&gt;next<br>          evenPointer -&gt; NULL<br><br>Step 5: loop while evenPointer != NULL &amp;&amp; evenPointer-&gt;next != NULL<br>          evenPointer -&gt; NULL<br><br>          NULL != NULL<br>          false<br><br>Step 6: oddPointer-&gt;next = evenHead<br>        1 -&gt; 3 -&gt; 5 -&gt; 2 -&gt; 4<br><br>Step 7: return head<br><br>We return the answer as 1 -&gt; 3 -&gt; 5 -&gt; 2 -&gt; 4.</pre><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=7e4cf608e8bd" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Sudoku Solver]]></title>
            <link>https://alkesh26.medium.com/sudoku-solver-6369a1aef456?source=rss-5b66f0dd7bcd------2</link>
            <guid isPermaLink="false">https://medium.com/p/6369a1aef456</guid>
            <category><![CDATA[algorithms]]></category>
            <category><![CDATA[javascript]]></category>
            <category><![CDATA[leetcode]]></category>
            <category><![CDATA[golang]]></category>
            <category><![CDATA[programming]]></category>
            <dc:creator><![CDATA[Alkesh Ghorpade]]></dc:creator>
            <pubDate>Thu, 15 Jun 2023 19:19:51 GMT</pubDate>
            <atom:updated>2023-06-18T15:43:03.524Z</atom:updated>
            <content:encoded><![CDATA[<h4>Write a program to solve a Sudoku puzzle by filling in the empty cells.</h4><p>Write a program to solve a Sudoku puzzle by filling the empty cells.</p><p>A sudoku solution must satisfy <strong>all of the following rules:</strong></p><p>Each of the digits 1-9 must occur exactly once in each row. Each of the digits 1-9 must occur exactly once in each column. Each of the digits 1-9 must occur exactly once in each of the 9 3x3 sub-boxes of the grid. The &#39;.&#39; character indicates empty cells.</p><p>Problem statement taken from: <a href="https://leetcode.com/problems/sudoku-solver">https://leetcode.com/problems/sudoku-solver</a>.</p><p><strong>Example 1:</strong></p><figure><img alt="Container" src="https://cdn-images-1.medium.com/max/250/0*FeiLYG3jjQQ2oA2Q.png" /></figure><pre>Input: board = [[&#39;5&#39;, &#39;3&#39;, &#39;.&#39;, &#39;.&#39;, &#39;7&#39;, &#39;.&#39;, &#39;.&#39;, &#39;.&#39;, &#39;.&#39;],<br>  [&#39;6&#39;, &#39;.&#39;, &#39;.&#39;, &#39;1&#39;, &#39;9&#39;, &#39;5&#39;, &#39;.&#39;, &#39;.&#39;, &#39;.&#39;],<br>  [&#39;.&#39;, &#39;9&#39;, &#39;8&#39;, &#39;.&#39;, &#39;.&#39;, &#39;.&#39;, &#39;.&#39;, &#39;6&#39;, &#39;.&#39;],<br>  [&#39;8&#39;, &#39;.&#39;, &#39;.&#39;, &#39;.&#39;, &#39;6&#39;, &#39;.&#39;, &#39;.&#39;, &#39;.&#39;, &#39;3&#39;],<br>  [&#39;4&#39;, &#39;.&#39;, &#39;.&#39;, &#39;8&#39;, &#39;.&#39;, &#39;3&#39;, &#39;.&#39;, &#39;.&#39;, &#39;1&#39;],<br>  [&#39;7&#39;, &#39;.&#39;, &#39;.&#39;, &#39;.&#39;, &#39;2&#39;, &#39;.&#39;, &#39;.&#39;, &#39;.&#39;, &#39;6&#39;],<br>  [&#39;.&#39;, &#39;6&#39;, &#39;.&#39;, &#39;.&#39;, &#39;.&#39;, &#39;.&#39;, &#39;2&#39;, &#39;8&#39;, &#39;.&#39;],<br>  [&#39;.&#39;, &#39;.&#39;, &#39;.&#39;, &#39;4&#39;, &#39;1&#39;, &#39;9&#39;, &#39;.&#39;, &#39;.&#39;, &#39;5&#39;],<br>  [&#39;.&#39;, &#39;.&#39;, &#39;.&#39;, &#39;.&#39;, &#39;8&#39;, &#39;.&#39;, &#39;.&#39;, &#39;7&#39;, &#39;9&#39;]<br>]<br><br>Output: [[&#39;5&#39;, &#39;3&#39;, &#39;4&#39;, &#39;6&#39;, &#39;7&#39;, &#39;8&#39;, &#39;9&#39;, &#39;1&#39;, &#39;2&#39;],<br>  [&#39;6&#39;, &#39;7&#39;, &#39;2&#39;, &#39;1&#39;, &#39;9&#39;, &#39;5&#39;, &#39;3&#39;, &#39;4&#39;, &#39;8&#39;],<br>  [&#39;1&#39;, &#39;9&#39;, &#39;8&#39;, &#39;3&#39;, &#39;4&#39;, &#39;2&#39;, &#39;5&#39;, &#39;6&#39;, &#39;7&#39;],<br>  [&#39;8&#39;, &#39;5&#39;, &#39;9&#39;, &#39;7&#39;, &#39;6&#39;, &#39;1&#39;, &#39;4&#39;, &#39;2&#39;, &#39;3&#39;],<br>  [&#39;4&#39;, &#39;2&#39;, &#39;6&#39;, &#39;8&#39;, &#39;5&#39;, &#39;3&#39;, &#39;7&#39;, &#39;9&#39;, &#39;1&#39;],<br>  [&#39;7&#39;, &#39;1&#39;, &#39;3&#39;, &#39;9&#39;, &#39;2&#39;, &#39;4&#39;, &#39;8&#39;, &#39;5&#39;, &#39;6&#39;],<br>  [&#39;9&#39;, &#39;6&#39;, &#39;1&#39;, &#39;5&#39;, &#39;3&#39;, &#39;7&#39;, &#39;2&#39;, &#39;8&#39;, &#39;4&#39;],<br>  [&#39;2&#39;, &#39;8&#39;, &#39;7&#39;, &#39;4&#39;, &#39;1&#39;, &#39;9&#39;, &#39;6&#39;, &#39;3&#39;, &#39;5&#39;],<br>  [&#39;3&#39;, &#39;4&#39;, &#39;5&#39;, &#39;2&#39;, &#39;8&#39;, &#39;6&#39;, &#39;1&#39;, &#39;7&#39;, &#39;9&#39;]<br>]<br><br>Explanation: The input board is shown above and the only valid solution is shown below:</pre><figure><img alt="Container" src="https://cdn-images-1.medium.com/max/250/0*sTkGK1CD4IjAIeTP.png" /></figure><p><strong>Constraints:</strong></p><pre>- board.length == 9<br>- board[i].length == 9<br>- board[i][j] is a digit or &#39;.&#39;<br>- It is guaranteed that the input board has only one solution.</pre><h4>Solutions for Sudoku Solver</h4><h4>Approach 1: Sudoku using Brute Force</h4><p>The naive approach is to generate all possible numbers 1 to 9 configurations to fill the empty cells. We try every combination one by one until we get a valid sudoku. For every empty cell, we fill the position with numbers from 1 to 9. Once the sudoku is filled, we check if the sudoku is valid or not. If the sudoku is invalid, we recur for other cases.</p><p>A C++ snippet of this approach is as follows:</p><pre>class Solution {<br>public:<br>    bool isValid(vector&lt;vector&lt;char&gt;&gt;&amp; board, int i, int j, char value){<br>        // check for a valid row<br>        for(int row = 0; row &lt; 9; row++) {<br>            if(board[row][j] == value) {<br>                return false;<br>            }<br>        }<br><br>        // check for a valid column<br>        for(int col = 0; col &lt; 9; col++) {<br>            if(board[i][col] == value) {<br>                return false;<br>            }<br>        }<br><br>        // check for a valid 3 * 3 matrix<br>        for(int k = 0; k &lt; 9; k++) {<br>            if(board[3 * (i / 3) + k % 3][3 * (j / 3) + k / 3] == value) {<br>                return false;<br>            }<br>        }<br><br>        return true;<br>    }<br><br>    bool solveSudokuHelper(vector&lt;vector&lt;char&gt;&gt;&amp; board, int row, int column) {<br>        // if we reached the last cell of the board<br>        // we should avoid further backtracking<br>        // return true in this case<br>        if (row == 8 &amp;&amp; column == 9)<br>            return true;<br><br>        // if the column value becomes 9,<br>        // we move to the next row<br>        if (column == 9) {<br>            row++;<br>            column = 0;<br>        }<br><br>        // if the current cell of the board already contains<br>        // any value from 1-9, we iterate for the next column<br>        if (board[row][column] != &#39;.&#39;)<br>            return solveSudokuHelper(board, row, column + 1);<br><br>        for (int num = 1; num &lt;= 9; num++) {<br>            // Check if it is safe to place<br>            // the num (1-9) in the<br>            // given cell<br>            if (isValid(board, row, column, num)) {<br>                // assign the value to the corresponding cell<br>                board[row][column] = char(num);<br><br>                // fill in the values for the next column<br>                if (solveSudokuHelper(board, row, column + 1))<br>                    return true;<br>            }<br><br>            // if, in the previous step, the sudoku was invalid<br>            // update the cell to an empty value. In this case, &#39;.&#39;<br>            board[row][column] = &#39;.&#39;;<br>        }<br><br>        return false;<br>    }<br><br>    void solveSudoku(vector&lt;vector&lt;char&gt;&gt;&amp; board) {<br>        solveSudokuHelper(board, 0, 0);<br>    }<br>};</pre><p>The time complexity of this approach is <strong>O(9 ^ (n * n))</strong>. We are filling every empty cell of the board with all 9 possible combinations.</p><p>The space complexity is <strong>O(1)</strong>.</p><h4>Approach 2: Sudoku using Backtracking</h4><p>Sudoku is solved by assigning numbers one by one to empty cells. In this approach, we first check if assigning a number to the cell is safe. If the placement is valid, we then move to the next column. To validate the cell value, we check if the number is not present in the current row, column, or 3 * 3 subgrid. After validating the cell, we recursively check whether this assignment leads to the solution. We try the next number if the assignment doesn’t lead to a solution.</p><p>The code flow of this approach is as follows:</p><pre>- Create a HashMap for the row, column and 3 * 3 subgrid.<br>- Create a function that validates the assignment of the current cell of the grid.<br>- If any number from 1-9 has a value greater than 1 in the HashMap, return false else, return true.<br>- Create a recursive function that accepts the sudoku board as a param.<br>- Check for an empty cell (&#39;.&#39;)<br>  - if the cell is empty, assign a number from 1 to 9<br>  - check if assigning the number to the current cell, makes the sudoku safe or not<br>  - if the sudoku is valid, recursively call the function for all safe cases from 0 to 9.<br>  - if any recursive call returns true, we end the loop.</pre><p>A C++ snippet of this approach is as below:</p><pre>class Solution {<br>public:<br>    bool numPresentInRow(vector&lt;vector&lt;char&gt;&gt;&amp; board, int row, int num) {<br>        for (int column = 0; column &lt; 9; column++)<br>            if (grid[row][column] == num)<br>                return true;<br><br>        return false;<br>    }<br><br>    bool numPresentInColum(vector&lt;vector&lt;char&gt;&gt;&amp; board, int column, int num) {<br>        for (int row = 0; row &lt; 9; row++)<br>            if (grid[row][column] == num)<br>                return true;<br><br>        return false;<br>    }<br><br>    bool numPresentInSubGrid(vector&lt;vector&lt;char&gt;&gt;&amp; board, int subGridRowStartIndex, int subGridColumnStartIndex, int num) {<br>        for (int row = 0; row &lt; 3; row++)<br>            for (int col = 0; col &lt; 3; col++)<br>                if (grid[row + subGridRowStartIndex][col + subGridColumnStartIndex] == num)<br>                    return true;<br><br>        return false;<br>    }<br><br>    bool isSafe(vector&lt;vector&lt;char&gt;&gt;&amp; board, int row, int column, char num) {<br>        return !numPresentInRow(board, row, num)<br>           &amp;&amp; !numPresentInColum(board, column, num)<br>           &amp;&amp; !numPresentInSubGrid(board, row - row % 3, column - column % 3, num)<br>           &amp;&amp; board[row][column] == &#39;.&#39;;<br>    }<br><br>    // function to check if there are any empty cells in the sudoku<br>    // if yes, the row and column parameters (passed by reference)<br>    // will be set to the location that is empty and true is returned<br>    bool hasEmptyCell(vector&lt;vector&lt;char&gt;&gt;&amp; board, int&amp; row, int&amp; column) {<br>        for (row = 0; row &lt; 9; i++)<br>            for (column = 0; column &lt; 9; column++)<br>                if (grid[row][column] == &#39;.&#39;)<br>                    return true;<br><br>        return false;<br>    }<br><br>    bool solveSudokuHelper(vector&lt;vector&lt;char&gt;&gt;&amp; board) {<br>        int row, column;<br><br>        // return true if there are no empty cells<br>        if (!hasEmptyCell(board, row, column))<br>            return true;<br><br>        // loop from 1 to 9<br>        for (int num = 1; num &lt;= 9; num++) {<br>            // check if the assignment of num is safe<br>            if (isSafe(board, row, column, num)) {<br>                // make a tentative assignment<br>                board[row][column] = char(num);<br><br>                // return true if the current assignment is valid<br>                if (solveSudokuHelper(board))<br>                    return true;<br><br>                // if the assignment is unsafe,<br>                // assign the empty value<br>                board[row][column] = &#39;.&#39;;<br>            }<br>        }<br><br>        // this triggers backtracking<br>        return false;<br>    }<br><br>    void solveSudoku(vector&lt;vector&lt;char&gt;&gt;&amp; board) {<br>        solveSudokuHelper(board);<br>    }<br>};</pre><p>The worst-case time complexity of this approach remains the same as the <strong>Brute Force</strong> approach, that is <strong>O(9 ^ (n * n))</strong>. But since we are validating the assignment, we are avoiding a few unnecessary iterations; hence, the average-case time complexity will be better.</p><h4>Approach 3: Sudoku using BitMask</h4><p>This approach is a slight optimization to the <strong>Backtracing</strong> solution. Instead of looping over each row, column and subgrid to check whether the number is already present, we use bit masks to verify the same.</p><p>Let’s check the algorithm first.</p><h4>Algorithm</h4><pre>// function solveSudoku(board)<br>- set vector&lt;int&gt; rows(9, 0), columns(9, 0), subgrids(9, 0)<br><br>// this will mask the bits in the row, columns and subgrids array<br>// for non-empty cells<br>- call setBits(board, rows, columns, subgrids)<br><br>// function to backtrack and generate the possible solutions<br>- backtrack(board, index, rows, columns, subgrids)<br><br><br>// function setBits(board, rows, columns, subgrids)<br>- loop for row = 0; row &lt; 9; row++<br>  - loop for column = 0; column &lt; 9; column++<br>    - if board[row][column] != &#39;.&#39;<br>      - set bitMask = 1 &lt;&lt; (board[row][column] - &#39;1&#39;)<br>      - set subgrid = (row / 3) * 3 + (column / 3)<br><br>      // mask the values in the row, column and subgrid array<br>      - rows[row] |= bitMask<br>      - columns[column] |= bitMask<br>      - subgrids[subgrid] |= bitMask<br>    - end if<br>  - end inner for loop<br>- end outer for loop</pre><p>Check out our solutions in <strong>C++</strong>, <strong>Golang</strong>, and <strong>Javascript</strong>.</p><h4>C++ solution</h4><pre>class Solution {<br>public:<br>    void setBits(vector&lt;vector&lt;char&gt;&gt;&amp; board, vector&lt;int&gt;&amp; rows, vector&lt;int&gt;&amp; columns, vector&lt;int&gt;&amp; subgrids) {<br>        for(int row = 0; row &lt; 9; row++) {<br>            for(int column = 0; column &lt; 9; column++) {<br>                if(board[row][column] != &#39;.&#39;) {<br>                    int bitMask = 1 &lt;&lt; (board[row][column] - &#39;1&#39;);<br>                    int subgrid = (row / 3) * 3 + (column / 3);<br><br>                    rows[row] |= bitMask;<br>                    columns[column] |= bitMask;<br>                    subgrids[subgrid] |= bitMask;<br>                }<br>            }<br>        }<br>    }<br><br>    bool backtrack(vector&lt;vector&lt;char&gt;&gt;&amp; board, int index, vector&lt;int&gt;&amp; rows, vector&lt;int&gt;&amp; columns, vector&lt;int&gt;&amp; subgrids) {<br>        if (index &gt; 80)<br>            return true;<br><br>        int row = index / 9;<br>        int column = index % 9;<br><br>        if (board[row][column] != &#39;.&#39;)<br>            return backtrack(board, index + 1, rows, columns, subgrids);<br><br>        int subgrid = (row / 3) * 3 + (column / 3);<br><br>        for (int i = 0; i &lt; 9; ++i) {<br>            int mask = 1 &lt;&lt; i;<br>            if (rows[row] &amp; mask || columns[column] &amp; mask || subgrids[subgrid] &amp; mask)<br>                continue;<br><br>            board[row][column] = i + &#39;1&#39;;<br>            rows[row] |= mask;<br>            columns[column] |= mask;<br>            subgrids[subgrid] |= mask;<br><br>            if (backtrack(board, index + 1, rows, columns, subgrids))<br>                return true;<br><br>            board[row][column] = &#39;.&#39;;<br>            rows[row] ^= mask;<br>            columns[column] ^= mask;<br>            subgrids[subgrid] ^= mask;<br>        }<br><br>        return false;<br>    }<br><br>    void solveSudoku(vector&lt;vector&lt;char&gt;&gt;&amp; board) {<br>        vector&lt;int&gt; rows(9, 0), columns(9, 0), subgrids(9, 0);<br><br>        setBits(board, rows, columns, subgrids);<br><br>        backtrack(board, 0, rows, columns, subgrids);<br>    }<br>};</pre><h4>Golang solution</h4><pre>func setBits(board [][]byte, rows []int, columns []int, subgrids []int) {<br>    for row := 0; row &lt; 9; row++ {<br>        for column := 0; column &lt; 9; column++ {<br>            if board[row][column] != &#39;.&#39; {<br>                bitMask := 1 &lt;&lt; (board[row][column] - &#39;1&#39;)<br>                subgrid := (row / 3) * 3 + (column / 3)<br><br>                rows[row] |= bitMask<br>                columns[column] |= bitMask<br>                subgrids[subgrid] |= bitMask<br>            }<br>        }<br>    }<br>}<br><br>func backtrack(board [][]byte, index int, rows []int, columns []int, subgrids []int) bool {<br>    if index &gt; 80 {<br>        return true<br>    }<br><br>    row := index / 9<br>    column := index % 9<br><br>    if board[row][column] != &#39;.&#39; {<br>        return backtrack(board, index + 1, rows, columns, subgrids)<br>    }<br><br>    subgrid := (row / 3) * 3 + (column / 3)<br><br>    for i := 0; i &lt; 9; i++ {<br>        mask := 1 &lt;&lt; i<br><br>        if (rows[row] &amp; mask != 0) || (columns[column] &amp; mask != 0) || (subgrids[subgrid] &amp; mask != 0) {<br>            continue<br>        }<br><br>        board[row][column] = byte(i + 1 + &#39;0&#39;)<br>        rows[row] |= mask<br>        columns[column] |= mask<br>        subgrids[subgrid] |= mask<br><br>        if backtrack(board, index + 1, rows, columns, subgrids) {<br>            return true<br>        }<br><br>        board[row][column] = &#39;.&#39;<br>        rows[row] ^= mask<br>        columns[column] ^= mask<br>        subgrids[subgrid] ^= mask<br>    }<br><br>    return false<br>}<br><br>func solveSudoku(board [][]byte)  {<br>    rows, columns, subgrids := make([]int, 9), make([]int, 9), make([]int, 9)<br><br>    setBits(board, rows, columns, subgrids)<br><br>    backtrack(board, 0, rows, columns, subgrids)<br>}</pre><h4>JavaScript solution</h4><pre>var setBits = function(board, rows, columns, subgrids) {<br>    for(let row = 0; row &lt; 9; row++) {<br>        for(let column = 0; column &lt; 9; column++) {<br>            if(board[row][column] != &#39;.&#39;) {<br>                let bitMask = 1 &lt;&lt; (parseInt(board[row][column]) - 1);<br>                let subgrid = Math.floor(row / 3) * 3 + Math.floor(column / 3);<br><br>                rows[row] |= bitMask;<br>                columns[column] |= bitMask;<br>                subgrids[subgrid] |= bitMask;<br>            }<br>        }<br>    }<br>}<br><br>var backtrack = function(board, index, rows, columns, subgrids) {<br>    if (index &gt; 80)<br>            return true;<br><br>    let row = Math.floor(index / 9);<br>    let column = Math.floor(index % 9);<br><br>    if (board[row][column] != &#39;.&#39;)<br>        return backtrack(board, index + 1, rows, columns, subgrids);<br><br>    let subgrid = Math.floor(row / 3) * 3 + Math.floor(column / 3);<br><br>    for (let i = 0; i &lt; 9; ++i) {<br>        let mask = 1 &lt;&lt; i;<br>        if (rows[row] &amp; mask || columns[column] &amp; mask || subgrids[subgrid] &amp; mask)<br>            continue;<br><br>        board[row][column] = (i + 1).toString();<br>        rows[row] |= mask;<br>        columns[column] |= mask;<br>        subgrids[subgrid] |= mask;<br><br>        if(backtrack(board, index + 1, rows, columns, subgrids))<br>            return true;<br><br>        board[row][column] = &#39;.&#39;;<br>        rows[row] ^= mask;<br>        columns[column] ^= mask;<br>        subgrids[subgrid] ^= mask;<br>    }<br><br>    return false;<br>}<br><br>/**<br> * @param {character[][]} board<br> * @return {void} Do not return anything, modify board in-place instead.<br> */<br>var solveSudoku = function(board) {<br>    let rows = Array(9).fill(0), columns = Array(9).fill(0), subgrids = Array(9).fill(0);<br><br>    setBits(board, rows, columns, subgrids);<br><br>    backtrack(board, 0, rows, columns, subgrids);<br>};</pre><p><em>Originally posted at </em><a href="https://alkeshghorpade.me/post/leetcode-sudoku-solver"><em>https://alkeshghorpade.me</em></a><em>.</em></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=6369a1aef456" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Implement LRU Cache]]></title>
            <link>https://alkesh26.medium.com/implement-lru-cache-f834a05b97f0?source=rss-5b66f0dd7bcd------2</link>
            <guid isPermaLink="false">https://medium.com/p/f834a05b97f0</guid>
            <category><![CDATA[golang]]></category>
            <category><![CDATA[leetcode]]></category>
            <category><![CDATA[programming]]></category>
            <category><![CDATA[algorithms]]></category>
            <category><![CDATA[javascript]]></category>
            <dc:creator><![CDATA[Alkesh Ghorpade]]></dc:creator>
            <pubDate>Sun, 11 Jun 2023 13:13:56 GMT</pubDate>
            <atom:updated>2023-06-12T17:32:25.677Z</atom:updated>
            <content:encoded><![CDATA[<h3>Problem statement</h3><p>Design a data structure that follows the constraints of a <a href="https://en.wikipedia.org/wiki/Cache_replacement_policies#LRU">Least Recently Used (LRU) cache</a>.</p><p>Implement the <strong>LRUCache</strong> class:</p><ul><li>LRUCache(int capacity) Initialize the LRU cache with positive size capacity.</li><li>int get(int key) Return the value of the key if the key exists, otherwise return -1.</li><li>void put(int key, int value) Update the value of the key if the key exists. Otherwise, add the key-value pair to the cache. If the number of keys exceeds the capacity from this operation, evict the least recently used key.</li></ul><p>The functions get and put must each run in O(1) average time complexity.</p><p>Problem statement taken from: <a href="https://leetcode.com/problems/lru-cache">https://leetcode.com/problems/lru-cache</a>.</p><p><strong>Example 1:</strong></p><pre>Input<br>[&#39;LRUCache&#39;, &#39;put&#39;, &#39;put&#39;, &#39;get&#39;, &#39;put&#39;, &#39;get&#39;, &#39;put&#39;, &#39;get&#39;, &#39;get&#39;, &#39;get&#39;]<br>[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]<br>Output<br>[null, null, null, 1, null, -1, null, -1, 3, 4]<br><br>Explanation<br>LRUCache lRUCache = new LRUCache(2);<br>lRUCache.put(1, 1); // cache is {1 = 1}<br>lRUCache.put(2, 2); // cache is {1 = 1, 2 = 2}<br>lRUCache.get(1);    // return 1<br>lRUCache.put(3, 3); // LRU key was 2, evicts key 2, cache is {1 = 1, 3 = 3}<br>lRUCache.get(2);    // returns -1 (not found)<br>lRUCache.put(4, 4); // LRU key was 1, evicts key 1, cache is {4 = 4, 3 = 3}<br>lRUCache.get(1);    // return -1 (not found)<br>lRUCache.get(3);    // return 3<br>lRUCache.get(4);    // return 4</pre><p><strong>Constraints:</strong></p><pre>- 1 &lt;= capacity &lt;= 3000<br>- 0 &lt;= key &lt;= 10^4<br>- 0 &lt;= value &lt;= 10^5<br>- At most 2 * 10^5 calls will be made to get and put.</pre><h3>What is an LRU cache?</h3><p>A cache provides a high-speed data storage layer which stores a subset of data. It ensures future requests for the same data get served faster than fetching the data from the primary storage location.</p><p>When our application’s data size is vast, we cannot cache the whole data. Caching complete data is also not optimal and cost-effective, so we only store the subset of data in the cache. But what data goes into the cache depends entirely on the application, because of which we have different caching mechanisms.</p><p>A <a href="https://en.wikipedia.org/wiki/Cache_replacement_policies#LRU">Least Recently Used (LRU) cache</a> is one such type of caching. LRU is a cache eviction algorithm that organizes the elements in order of use. LRU will remove the element that has not been referenced or used for a long time.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/681/1*4yztA9VIaG7Uu_2jfJSmpw.png" /></figure><p>Source: Geeksforgeeks</p><p>As seen in the above image, the cache size is 3, and initially, it’s empty. We add 1 to the cache, and it gets stored at the beginning of the cache. We next add 2 and 3 to the cache. 3 gets added at the front of the cache list, and 1 gets stored at the tail of the cache. When we try to add 1 to the cache again, we see the cache is full. The least recently used element, which is 2, is present at the tail end of the cache. We remove the element and insert 1 at the front of the cache.</p><h3>How to implement an LRU cache?</h3><p>As seen in the above image, we know that the elements get added to a queue, and we follow FIFO (First-In-First-Out) approach.</p><ul><li>We need to use the Queue data structure. The queue will have a limited capacity.</li><li>Whenever an element gets added, we add it to the head of the queue.</li><li>When the queue size is complete, and we want to add a new element, we pop the elements from the tail of the queue.</li><li>Adding and removing the elements to the queue must be done in constant time. It can be solved using a <a href="https://www.geeksforgeeks.org/data-structures/linked-list/doubly-linked-list/">Doubly Linked List</a>.</li><li>Since it’s a cache, we also need to ensure the element we are looking for can be fetched quickly in <strong>O(1)</strong> time. It can be done using a HashMap. Apart from storing elements in the doubly linked list, we also store them in the HashMap.</li></ul><p>LRU cache will be a combination of Doubly Linked List and HashMap.</p><h3>Algorithm for LRU</h3><p>We need to follow these basic steps since we know what data structures to use for implementing an LRU.</p><ul><li>If the key is present in the HashMap, we call that a cache hit, and we return the value</li><li>If the key is absent, it’s a cache-miss; we must follow these two steps a. Add the new element in front of the queue. b. Add a new entry for the element in the HashMap and update the head.</li><li>If it’s a cache-hit a. We remove the element from the queue and add it as the head of the queue. b. We update the HashMap with a new reference to the head of the list.</li></ul><p>Let’s check the algorithm below:</p><h4>Algorithm</h4><pre>// define a Node struct<br>- struct Node {<br>      // since it&#39;s a doubly linked list, a node will have two pointers<br>      // next and prev that stores the address of the next and previous nodes<br>      // of the linked list.<br><br>      // key is the element we search<br>      // value is the data we want to store in the cache for this key<br>      Public: {<br>          Node *next;<br>          Node *prev;<br>          int value;<br>          int key;<br>      }<br>  }<br><br>// define the class LRU Cache<br>- class LRUCache<br>    Public: {<br>        // initialize the head and tail of the doubly linked list<br>        Node *head = new Node()<br>        Node *tail = new Node()<br><br>        // create a HashMap that stores the element and helps in fetching<br>        // the data in **O(1)** time.<br>        unordered_map&lt;int, Node*&gt; nodeMap<br><br>        // the size of the doubly linked list<br>        int capacity<br><br>        // function to initialize the LRU cache class<br>        // Since the cache is empty<br>        // we point the head next to tail and tail previous to head<br>        LRUCache(int capacity) {<br>            this-&gt;capacity = capacity;<br>            head-&gt;next = tail;<br>            tail-&gt;prev= head;<br>        }<br><br>        // function to get the element from the cache<br>        // the function expects a key element<br>        int get(int key) {<br>            // if the element is present in the cache, a cache-hit<br>            // we remove the element from the doubly linked list<br>            // and place it at the head of the list.<br><br>            // if it&#39;s a cache hit, in this case, we just return -1.<br><br>            if(nodeMap.find(key) != nodeMap.end()){<br>                Node* node = nodeMap[key];<br>                removeNode(node);<br>                addNode(node);<br>                return node-&gt;value;<br>            } else {<br>                return -1;<br>            }<br>        }<br><br>        // function to add the element in the cache<br>        void put(int key, int value) {<br>            // if the key is present in the cache<br>            // we update the value associated with the key.<br>            // We remove the node from the list<br>            // and since it was recently searched, we update<br>            // it as the head of the queue<br><br>            // if the key is not present in the cache<br>            // we first check if the cache is full<br>            // if the cache is full we remove the tail from the<br>            // list and remove the associated key from the hash map,<br>            // since it was not searched recently.<br><br>            // we add the new element as the head of the cache<br>            // and create an entry in the hash map<br>            if(nodeMap.find(key) != nodeMap.end()){<br>                Node* node = nodeMap[key];<br>                node-&gt;value = value;<br>                removeNode(node);<br>                addNode(node);<br>            } else {<br>                if(nodeMap.size() == capacity) {<br>                    Node* node = tail-&gt;prev;<br>                    removeNode(node);<br>                    nodeMap.erase(node-&gt;key);<br>                }<br><br>                Node* node = new Node();<br>                node-&gt;value = value;<br>                node-&gt;key = key;<br>                addNode(node);<br>                nodeMap[key] = node;<br>            }<br>        }<br><br>        // function to create a new entry in the list<br>        // the new element will be head of the list<br>        void addNode(Node* node){<br>            node-&gt;next = head-&gt;next;<br>            node-&gt;prev = head;<br>            (node-&gt;next)-&gt;prev = node;<br>            head-&gt;next = node;<br>        }<br><br>        // function to remove the tail node from the list<br>        void removeNode(Node* node){<br>            Node* prevNode = node-&gt;prev;<br>            Node* nextNode = node-&gt;next;<br>            prevNode-&gt;next = nextNode;<br>            nextNode-&gt;prev = prevNode;<br>        }<br>    }</pre><p>The time complexity for searching, adding and deleting an element is <strong>O(1)</strong>. The space complexity is <strong>O(n)</strong> since we are using an additional space HashMap and a Doubly Linked list.</p><p>Check out our solutions in <strong>C++</strong>, <strong>Golang</strong>, and <strong>JavaScript</strong>.</p><h4>C++ solution</h4><pre>struct Node{<br>    public:<br>        Node* next;<br>        Node* prev;<br>        int value;<br>        int key;<br>};<br><br>class LRUCache {<br>public:<br>    Node* head = new Node();<br>    Node* tail = new Node();<br>    unordered_map&lt;int, Node*&gt; nodeMap;<br>    int capacity;<br><br>    LRUCache(int capacity) {<br>        this-&gt;capacity = capacity;<br>        head-&gt;next = tail;<br>        tail-&gt;prev= head;<br>    }<br><br>    int get(int key) {<br>        if(nodeMap.find(key) != nodeMap.end()){<br>            Node* node = nodeMap[key];<br>            removeNode(node);<br>            Node* temp = head;<br>            addNode(node);<br>            temp = head;<br>            temp = tail;<br>            return node-&gt;value;<br>        } else {<br>            Node* temp = head;<br>            temp = tail;<br>            return -1;<br>        }<br>    }<br><br>    void put(int key, int value) {<br>        if(nodeMap.find(key) != nodeMap.end()){<br>            Node* node = nodeMap[key];<br>            node-&gt;value = value;<br>            removeNode(node);<br>            addNode(node);<br>        } else {<br>            if(nodeMap.size() == capacity) {<br>                Node* node = tail-&gt;prev;<br>                removeNode(node);<br>                nodeMap.erase(node-&gt;key);<br>            }<br><br>            Node* node = new Node();<br>            node-&gt;value = value;<br>            node-&gt;key = key;<br>            addNode(node);<br>            Node* temp = head;<br>            temp=tail;<br>            nodeMap[key] = node;<br>        }<br>    }<br><br>    void addNode(Node* node){<br>        node-&gt;next = head-&gt;next;<br>        node-&gt;prev = head;<br>        (node-&gt;next)-&gt;prev = node;<br>        head-&gt;next = node;<br>        Node* temp = head;<br>    }<br><br>    void removeNode(Node* node){<br>        Node* prevNode = node-&gt;prev;<br>        Node* nextNode = node-&gt;next;<br>        prevNode-&gt;next = nextNode;<br>        nextNode-&gt;prev = prevNode;<br>        Node* temp = head;<br>        temp = tail;<br>    }<br>};</pre><h4>Golang solution</h4><pre>type Node struct {<br>    next *Node<br>    prev *Node<br>    value int<br>    key int<br>}<br><br>type LRUCache struct {<br>    nodeMap map[int]*Node<br>    head, tail *Node<br>    capacity int<br>}<br><br>func Constructor(capacity int) LRUCache {<br>    head := &amp;Node{nil, nil, 0, 0}<br>    tail := &amp;Node{nil, nil, 0, 0}<br>    head.next = tail<br>    tail.next = head<br><br>    return LRUCache {<br>        capacity: capacity,<br>        nodeMap: make(map[int]*Node),<br>        head: head,<br>        tail: tail,<br>    }<br>}<br><br>func (this *LRUCache) Get(key int) int {<br>    if node, ok := this.nodeMap[key]; ok {<br>        this.removeNode(node)<br>        this.addNode(node)<br>        return node.value<br>    } else {<br>        return -1<br>    }<br>}<br><br>func (this *LRUCache) Put(key int, value int)  {<br>    if node, ok := this.nodeMap[key]; ok {<br>        node.value = value<br>        this.removeNode(node)<br>        this.addNode(node)<br>    } else {<br>        if len(this.nodeMap) == this.capacity {<br>            node = this.tail.prev<br>            this.removeNode(node)<br>            delete(this.nodeMap, node.key)<br>        }<br><br>        node := &amp;Node{nil, nil, 0, 0}<br>        node.value = value<br>        node.key = key<br>        this.addNode(node)<br>        this.nodeMap[key] = node<br>    }<br>}<br><br>func (this *LRUCache) addNode(node *Node) {<br>    node.prev = this.head<br>    node.next = this.head.next<br>    node.next.prev = node<br>    this.head.next = node<br>}<br><br>func (this *LRUCache) removeNode(node *Node) {<br>    prevNode := node.prev<br>    nextNode := node.next<br>    prevNode.next = nextNode<br>    nextNode.prev = prevNode<br>}</pre><h4>JavaScript solution</h4><pre>class Node {<br>    /**<br>     * @param {number} value<br>     * @param {Node} prev<br>     * @param {Node} next<br>     * @return {void}<br>     */<br>    constructor(key = 0, value = 0, prev = null, next = null) {<br>        this.key = key;<br>        this.value = value;<br>        this.prev = prev;<br>        this.next = next;<br>    }<br>}<br><br>/**<br> * @param {number} capacity<br> */<br>var LRUCache = function (capacity) {<br>    this.capacity = capacity;<br>    this.head = new Node(Infinity, Infinity);<br>    this.tail = new Node(-Infinity, -Infinity);<br>    this.head.next = this.tail;<br>    this.tail.prev = this.head;<br>    this.nodeMap = new Map([<br>        [this.head.key, this.head],<br>        [this.tail.key, this.tail],<br>    ]);<br>};<br><br>/**<br> * @param {Node} node<br> * @return {void}<br> */<br>LRUCache.prototype.addNode = function (node) {<br>    node.prev = null;<br>    node.next = this.head;<br>    this.head.prev = node;<br>    this.head = node;<br>};<br><br>/**<br> * @param {Node} node<br> * @return {void}<br> */<br>LRUCache.prototype.removeNode = function (node) {<br>    const { prev, next } = node;<br><br>    if (prev &amp;&amp; next) {<br>        [prev.next, next.prev] = [next, prev];<br>    } else if (prev) {<br>        prev.next = null;<br>        this.tail = prev;<br>    } else if (next) {<br>        next.prev = null;<br>        this.head = next;<br>    }<br>};<br><br>/**<br> * @param {number} key<br> * @return {number}<br> */<br>LRUCache.prototype.get = function (key) {<br>    const node = this.nodeMap.get(key);<br><br>    if (!node) {<br>        return -1;<br>    }<br><br>    this.removeNode(node);<br>    this.addNode(node);<br><br>    return node.value;<br>};<br><br>/**<br> * @param {number} key<br> * @param {number} value<br> * @return {void}<br> */<br>LRUCache.prototype.put = function (key, value) {<br>    const node = new Node(key, value);<br><br>    if (this.nodeMap.has(key)) {<br>        this.removeNode(this.nodeMap.get(key));<br>    }<br><br>    this.addNode(node);<br>    this.nodeMap.set(key, node);<br>    const n = this.nodeMap.size - this.capacity;<br><br>    for (i = 0; i &lt; n; ++i) {<br>        this.nodeMap.delete(this.tail.key);<br>        this.removeNode(this.tail);<br>    }<br><br>    return null;<br>};progra</pre><p><em>Originally published at </em><a href="https://alkeshghorpade.me/post/leetcode-lru-cache"><em>https://alkeshghorpade.me</em></a><em>.</em></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=f834a05b97f0" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Insert Interval]]></title>
            <link>https://alkesh26.medium.com/insert-interval-57545dbb9574?source=rss-5b66f0dd7bcd------2</link>
            <guid isPermaLink="false">https://medium.com/p/57545dbb9574</guid>
            <category><![CDATA[go]]></category>
            <category><![CDATA[leetcode]]></category>
            <category><![CDATA[algorithms]]></category>
            <category><![CDATA[javascript]]></category>
            <category><![CDATA[programming]]></category>
            <dc:creator><![CDATA[Alkesh Ghorpade]]></dc:creator>
            <pubDate>Thu, 08 Jun 2023 13:34:49 GMT</pubDate>
            <atom:updated>2023-06-12T17:32:42.915Z</atom:updated>
            <content:encoded><![CDATA[<h3>Problem statement</h3><p>You are given an array of non-overlapping intervals intervals where intervals[i] = [starti, endi] represent the start and the end of the ith interval and intervals is sorted in ascending order by starti. You are also given an interval newInterval = [start, end] that represents the start and end of another interval.</p><p>Insert newInterval into intervals such that intervals is still sorted in ascending order by starti and intervals still does not have any overlapping intervals (merge overlapping intervals if necessary).</p><p>Return intervals after the insertion.</p><p>Problem statement taken from: <a href="https://leetcode.com/problems/insert-interval">https://leetcode.com/problems/insert-interval</a>.</p><p><strong>Example 1:</strong></p><pre>Input: intervals = [[1, 3], [6, 9]], newInterval = [2, 5]<br>Output: [[1, 5], [6, 9]]</pre><p><strong>Example 2:</strong></p><pre>Input: intervals = [[1, 2], [3, 5], [6, 7], [8, 10], [12, 16]], newInterval = [4, 8]<br>Output: [[1, 2], [3, 10], [12, 16]]<br>Explanation: Because the new interval [4, 8] overlaps with [3, 5], [6, 7], [8, 10].</pre><p><strong>Constraints:</strong></p><pre>- 0 &lt;= intervals.length &lt;= 10^4<br>- intervals[i].length == 2<br>- 0 &lt;= starti &lt;= endi &lt;= 10^5<br>- intervals is sorted by starti in ascending order.<br>- newInterval.length == 2<br>- 0 &lt;= start &lt;= end &lt;= 10^5</pre><h3>Solutions for Insert Interval</h3><h4>Approach 1: Handle all cases</h4><p>When working on these kinds of problems, we first consider all the cases we need to handle when inserting a new interval. Here are the five cases we need to handle in our code:</p><p>Let’s assume the new interval that gets inserted is [a, b].</p><ol><li><strong>Case 1:</strong> b &lt; start value of the first interval in list <br>Insert the interval at the beginning of the list.</li><li><strong>Case 2:</strong> end value of the last interval in list &lt; a <br>Insert the interval at the end of the list</li><li><strong>Case 3:</strong> a &lt; (start value of the first interval) and b &gt; (end value of the last interval) <br>The new interval is a superset of this list. It contains all the intervals of the list. We return the new interval as a result.</li><li><strong>Case 4:</strong> The new interval falls in between any two intervals in the list and is not overlapping with any interval <br>We simply insert the interval in the correct position in the list. For eg.</li></ol><pre>Input: List : [23, 46], [49, 65], [100, 120] <br>New interval : [70, 89] <br>Output: [23, 46], [49, 65], [70, 89], [100, 120]</pre><p>5. <strong>Case 5:</strong> When new interval overlaps with the intervals of the list <br>We merge the new interval with overlapping intervals. To understand this case, please refer to the previous blog, <a href="https://alkeshghorpade.me/post/leetcode-merge-intervals">Merge Intervals</a>.</p><p>A C++ snippet of this approach is as follows:</p><pre>vector&lt;vector&lt;int&gt;&gt; insertNewInterval (vector&lt;vector&lt;int&gt;&gt;&amp; intervals, interval newInterval) {<br>    vector&lt;vector&lt;int&gt;&gt; result;<br>    int n = intervals.size();<br><br>    // if the set is empty, then simply insert newInterval and return.<br>    if (n == 0) {<br>        result.push_back(newInterval);<br>        return result;<br>    }<br><br>    // case 1 and case 2 (new interval is not overlapping with any interval)<br>    if (newInterval[1] &lt; intervals[0][0] || newInterval[0] &gt; intervals[n - 1][1]) {<br>        if (newInterval[1] &lt; intervals[0][0])<br>            result.push_back(newInterval);<br><br>        for (int i = 0; i &lt; n; i++)<br>            result.push_back(intervals[i]);<br><br>        if (newInterval[0] &gt; intervals[n - 1][1])<br>            result.push_back(newInterval);<br><br>        return result;<br>    }<br><br>    // case 3 (New interval covers all existing)<br>    if (newInterval[0] &lt;= intervals[0][0] &amp;&amp; newInterval[1] &gt;= intervals[n - 1][1]) {<br>        result.push_back(newInterval);<br>        return result;<br>    }<br><br>    // case 4 and case 5<br>    // Two cases need to check whether intervals overlap or not.<br>    bool overlap = true;<br><br>    for (int i = 0; i &lt; n; i++) {<br>        overlap = doesOverlap(intervals[i], newInterval);<br>        if (!overlap) {<br>            result.push_back(intervals[i]);<br><br>            // case 4<br>            if (i &lt; n &amp;&amp; newInterval[0] &gt; intervals[i][1] &amp;&amp; newInterval[1] &lt; intervals[i + 1][0])<br>                result.push_back(newInterval);<br><br>            continue;<br>        }<br><br>        // case 5: Merge Overlapping intervals.<br>        vector&lt;int&gt; temp;<br>        temp[0] = min(newInterval[0], intervals[i][0]);<br><br>        // Traverse the set until intervals are overlapping<br>        while (i &lt; n &amp;&amp; overlap) {<br>            // ending time of the newly merged interval is the maximum ending time of both<br>            // overlapping intervals.<br>            temp[1] = max(newInterval[1], intervals[i][1]);<br><br>            if (i == n - 1)<br>                overlap = false;<br>            else<br>                overlap = doesOverlap(intervals[i + 1], newInterval);<br>            i++;<br>        }<br><br>        i--;<br>        result.push_back(temp);<br>    }<br><br>    return result;<br>}<br><br>bool doesOverlap(vector&lt;int&gt; a, vector&lt;int&gt; b) {<br>    return (min(a[1], b[1]) &gt;= max(a[0], b[0]));<br>}</pre><p>The time complexity of this approach is <strong>O(n)</strong>, and the space complexity is <strong>O(n)</strong>.</p><h4>Approach 2: Using Merge Intervals</h4><p>As mentioned above, we can use the <a href="https://alkeshghorpade.me/post/leetcode-merge-intervals">Merge Intervals</a> approach to solve this problem.</p><p>We insert the new interval in the list and use the merge intervals solution.</p><p>A C++ snippet of this approach is as follows:</p><pre>vector&lt;vector&lt;int&gt;&gt; merge(vector&lt;vector&lt;int&gt;&gt;&amp; intervals, vector&lt;int&gt; newInterval) {<br>    intervals.push_back(newInterval);<br>    sort(intervals.begin(), intervals.end());<br><br>    vector&lt;vector&lt;int&gt;&gt; result;<br><br>    for(auto interval: intervals){<br>        if(result.empty() || (result.back()[1] &lt; interval[0])){<br>            result.push_back({interval[0], interval[1]});<br>        } else {<br>            result.back()[1] = max(result.back()[1], interval[1]);<br>        }<br>    }<br><br>    return result;<br>}</pre><p>The time complexity of this approach is <strong>O(n * log n)</strong> because we are sorting the list. The space complexity is <strong>O(1)</strong>.</p><h4>Approach 3: Using Stack</h4><p>We use stack to identify the interval in which it can be merged or placed at the correct position.</p><p>The C++ snippet of this approach is as follows:</p><pre>vector&lt;vector&lt;int&gt;&gt; merge(vector&lt;vector&lt;int&gt;&gt;&amp; intervals, vector&lt;int&gt; newInterval) {<br>    stack&lt; pair&lt;int, int&gt; &gt; st;<br><br>    // push the first interval to stack<br>    st.push(intervals[0]);<br><br>    // store the top element of the stack<br>    vector&lt;int&gt; top = st.top();<br><br>    // Checking is newInterval[0] is less than top[1]<br>    if (newInterval[0] &lt; top[1]) {<br>        // pop the top element as it will merge with the<br>        // previous range<br>        st.pop();<br><br>        // re-assign top[0]<br>        top[0] = min(top[0], newInterval[0]);<br><br>        // re-assign top[1]<br>        top[1] = max(top[1], newInterval[1]);<br><br>        // push the current interval<br>        st.push(top);<br>    } else {<br>       st.push(newInterval);<br>    }<br><br>    // iterate from i = 1 to n - 1<br>    for (int i = 1; i &lt; n; i++) {<br>        // store the top element of the stack st<br>        vector&lt;int&gt; top = st.top();<br><br>        // if intervals[i][0] is less than top[1]<br>        if (intervals[i][0] &lt; top[1]) {<br>            st.pop();<br><br>            // re-assign top[0]<br>            top[0] = min(top[0], intervals[i][0]);<br><br>            // re-assign top[1]<br>            top[1] = max(top[1], intervals[i][1]);<br><br>            // push the current interval<br>            st.push(top);<br>        } else {<br>            st.push(intervals[i]);<br>        }<br>    }<br><br>    // storing the final intervals<br>    stack&lt;vector&lt;vector&lt;int&gt;&gt;&gt; result;<br><br>    // popping the stack elements<br>    while (st.empty() != true) {<br>        vector&lt;int&gt; element = st.top();<br>        st.pop();<br><br>        result.push(element);<br>    }<br><br>    return result;<br>}</pre><p>The time complexity of this approach is <strong>O(n)</strong>, and the space complexity is <strong>O(n)</strong>.</p><h4>Approach 4: Optimized solution without using additional space</h4><p>We can solve this problem without using any additional space. In <strong>Approach 1</strong>, we handled five cases. We need to handle only cases 1 and 4 explicitly, and the rest of the cases can be handled in a single loop.</p><p>Let’s check the algorithm first.</p><h4>Algorithm</h4><pre>// set size of intervals array<br>- n = intervals.size()<br>  i = 0<br><br>// iterate over the intervals list till the new interval start value is less than<br>// any of the interval&#39;s end values in the list<br>- loop while i &lt; n &amp;&amp; intervals[i][1] &lt; newInterval[0]<br><br>  // keep adding the intervals to the final result<br>  - result.push_back(intervals[i])<br><br>  - increment i; i++<br>- end while<br><br>// once we find the correct slot, now loop till the new interval end value is greater than<br>// any of the interval&#39;s start values in the list<br>- loop while i &lt; n &amp;&amp; newInterval[1] &gt;= intervals[i][0]<br><br>  // this code will handle the merging of the intervals based on<br>  // new interval start and end values<br>  // we also update the values of the new interval<br>  - newInterval[0] = min(newInterval[0], intervals[i][0])<br>  - newInterval[1] = max(newInterval[1], intervals[i][1])<br><br>  - increment i; i++<br>- end while<br><br>// append the new interval to result<br>- result.push_back(newInterval)<br><br>// append the remaining intervals of the list to the result<br>- loop while i &lt; n<br>  - result.push_back(intervals[i])<br>  - increment i; i++<br>- end while<br><br>- return result</pre><p>The time complexity of this approach is <strong>O(n)</strong>, and the space complexity is <strong>O(1)</strong>.</p><p>Check out our solutions in <strong>C++</strong>, <strong>Golang</strong>, and <strong>Javascript</strong>.</p><h4>C++ solution</h4><pre>class Solution {<br>public:<br>    vector&lt;vector&lt;int&gt;&gt; insert(vector&lt;vector&lt;int&gt;&gt;&amp; intervals, vector&lt;int&gt;&amp; newInterval) {<br>        int n = intervals.size(), i = 0;<br>        vector&lt;vector&lt;int&gt;&gt; result;<br><br>        while(i &lt; n &amp;&amp; intervals[i][1] &lt; newInterval[0]){<br>            result.push_back(intervals[i]);<br>            i++;<br>        }<br><br>        while(i &lt; n &amp;&amp; newInterval[1] &gt;= intervals[i][0]){<br>            newInterval[0] = min(newInterval[0], intervals[i][0]);<br>            newInterval[1] = max(newInterval[1], intervals[i][1]);<br>            i++;<br>        }<br><br>        result.push_back(newInterval);<br><br>        while(i &lt; n){<br>            result.push_back(intervals[i]);<br>            i++;<br>        }<br><br>        return result;<br>    }<br>};</pre><h4>Golang solution</h4><pre>func insert(intervals [][]int, newInterval []int) [][]int {<br>    n, i := len(intervals), 0<br>    var result [][]int<br><br>    for i &lt; n &amp;&amp; intervals[i][1] &lt; newInterval[0] {<br>        result = append(result, intervals[i])<br>        i++<br>    }<br><br>    for i &lt; n &amp;&amp; newInterval[1] &gt;= intervals[i][0] {<br>        newInterval[0] = min(newInterval[0], intervals[i][0])<br>        newInterval[1] = max(newInterval[1], intervals[i][1])<br>        i++<br>    }<br><br>    result = append(result, newInterval)<br><br>    for i &lt; n {<br>        result = append(result, intervals[i])<br>        i++<br>    }<br><br>    return result<br>}<br><br>func min(a, b int) int {<br>    if a &lt; b {<br>        return a<br>    }<br><br>    return b<br>}<br><br>func max(a, b int) int {<br>    if a &gt; b {<br>        return a<br>    }<br><br>    return b<br>}</pre><h4>JavaScript solution</h4><pre>/**<br> * @param {number[][]} intervals<br> * @param {number[]} newInterval<br> * @return {number[][]}<br> */<br>var insert = function(intervals, newInterval) {<br>    let n = intervals.length, i = 0;<br>    let result = [];<br><br>    while(i &lt; n &amp;&amp; intervals[i][1] &lt; newInterval[0]){<br>        result.push(intervals[i]);<br>        i++;<br>    }<br><br>    while(i &lt; n &amp;&amp; newInterval[1] &gt;= intervals[i][0]){<br>        newInterval[0] = Math.min(newInterval[0], intervals[i][0]);<br>        newInterval[1] = Math.max(newInterval[1], intervals[i][1]);<br>        i++;<br>    }<br><br>    result.push(newInterval);<br><br>    while(i &lt; n){<br>        result.push(intervals[i]);<br>        i++;<br>    }<br><br>    return result;<br>};</pre><h4>Dry Run</h4><p>Let’s dry-run our algorithm to see how the solution works.</p><pre>Input: intervals = [[1, 2], [3, 5], [6, 7], [8, 10], [12, 16]]<br>       newInterval = [4, 8]<br><br>Step 1: n = intervals.size()<br>          = 5<br>        i = 0<br>        vector&lt;vector&lt;int&gt;&gt; result<br><br>Step 2: loop while i &lt; n &amp;&amp; intervals[i][1] &lt; newInterval[0]<br>          0 &lt; 5 &amp;&amp; intervals[0][1] &lt; newInterval[0]<br>          true &amp;&amp; 2 &lt; 4<br>          true<br><br>          result.push_back(intervals[i])<br>          result.push_back(intervals[0])<br>          result.push_back([1, 2])<br>          result = [[1, 2]]<br><br>          i++<br>          i = 1<br><br>        loop while i &lt; n &amp;&amp; intervals[i][1] &lt; newInterval[0]<br>          1 &lt; 5 &amp;&amp; intervals[1][1] &lt; newInterval[0]<br>          true &amp;&amp; 5 &lt; 4<br>          false<br><br>Step 3: loop while i &lt; n &amp;&amp; newInterval[1] &gt;= intervals[i][0]<br>          1 &lt; 5 &amp;&amp; newInterval[1] &gt;= intervals[1][0]<br>          true &amp;&amp; 8 &gt;= 3<br>          true<br><br>          newInterval[0] = Math.min(newInterval[0], intervals[i][0])<br>                         = Math.min(newInterval[0], intervals[1][0])<br>                         = Math.min(4, 3)<br>                         = 3<br><br>          newInterval[1] = Math.max(newInterval[1], intervals[i][1])<br>                         = Math.max(newInterval[1], intervals[1][1])<br>                         = Math.max(8, 5)<br>                         = 8<br><br>          newInterval = [3, 8]<br><br>          i++<br>          i = 2<br><br>        loop while i &lt; n &amp;&amp; newInterval[1] &gt;= intervals[i][0]<br>          2 &lt; 5 &amp;&amp; newInterval[1] &gt;= intervals[2][0]<br>          true &amp;&amp; 8 &gt;= 6<br>          true<br><br>          newInterval[0] = Math.min(newInterval[0], intervals[i][0])<br>                         = Math.min(newInterval[0], intervals[1][0])<br>                         = Math.min(3, 6)<br>                         = 3<br><br>          newInterval[1] = Math.max(newInterval[1], intervals[i][1])<br>                         = Math.max(newInterval[1], intervals[1][1])<br>                         = Math.max(8, 7)<br>                         = 8<br><br>          newInterval = [3, 8]<br><br>          i++<br>          i = 3<br><br>        loop while i &lt; n &amp;&amp; newInterval[1] &gt;= intervals[i][0]<br>          3 &lt; 5 &amp;&amp; newInterval[1] &gt;= intervals[3][0]<br>          true &amp;&amp; 8 &gt;= 8<br>          true<br><br>          newInterval[0] = Math.min(newInterval[0], intervals[i][0])<br>                         = Math.min(newInterval[0], intervals[3][0])<br>                         = Math.min(3, 8)<br>                         = 3<br><br>          newInterval[1] = Math.max(newInterval[1], intervals[i][1])<br>                         = Math.max(newInterval[1], intervals[3][1])<br>                         = Math.max(8, 10)<br>                         = 10<br><br>          newInterval = [3, 10]<br><br>          i++<br>          i = 4<br><br>        loop while i &lt; n &amp;&amp; newInterval[1] &gt;= intervals[i][0]<br>          4 &lt; 5 &amp;&amp; newInterval[1] &gt;= intervals[4][0]<br>          true &amp;&amp; 8 &gt;= 12<br>          false<br><br>Step 4: result.push_back(newInterval)<br>        result.push_back([3, 10])<br>        result = [[1, 2], [3, 10]]<br><br>Step 5: loop while i &lt; n<br>          4 &lt; 5<br>          true<br><br>          result.push_back(intervals[i])<br>          result.push_back(intervals[4])<br>          result.push_back([12, 16])<br>          result = [[1, 2], [3, 10], [12, 16]]<br><br>          i++<br>          i = 5<br><br>        loop while i &lt; n<br>          5 &lt; 5<br>          false<br><br>Step 6: return result<br><br>We return the answer as [[1, 2], [3, 10], [12, 16]].</pre><p><em>Originally published at </em><a href="https://alkeshghorpade.me/post/leetcode-insert-interval"><em>https://alkeshghorpade.me</em></a><em>.</em></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=57545dbb9574" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Kth Largest Element in an Array]]></title>
            <link>https://alkesh26.medium.com/kth-largest-element-in-an-array-614898a77166?source=rss-5b66f0dd7bcd------2</link>
            <guid isPermaLink="false">https://medium.com/p/614898a77166</guid>
            <category><![CDATA[programming]]></category>
            <category><![CDATA[javascript]]></category>
            <category><![CDATA[golang]]></category>
            <category><![CDATA[algorithms]]></category>
            <category><![CDATA[leetcode]]></category>
            <dc:creator><![CDATA[Alkesh Ghorpade]]></dc:creator>
            <pubDate>Sun, 04 Jun 2023 17:48:49 GMT</pubDate>
            <atom:updated>2023-06-05T14:18:02.515Z</atom:updated>
            <content:encoded><![CDATA[<h4>Problem statement</h4><p>Given an integer array nums and an integer k, <em>return the Kth largest element in the array</em>.</p><p>Note that it is the Kth largest element in the sorted order, not the Kth distinct element.</p><p>You must solve it in O(n) time complexity.</p><p>Problem statement taken from: <a href="https://leetcode.com/problems/Kth-largest-element-in-an-array">https://leetcode.com/problems/Kth-largest-element-in-an-array</a>.</p><p><strong>Example 1:</strong></p><pre>Input: nums = [3, 2, 1, 5, 6, 4], k = 2<br>Output: 5</pre><p><strong>Example 2:</strong></p><pre>Input: nums = [3, 2, 3, 1, 2, 4, 5, 5, 6], k = 4<br>Output: 4</pre><p><strong>Constraints:</strong></p><pre>- 1 &lt;= k &lt;= nums.length &lt;= 10^5<br>- -10^4 &lt;= nums[i] &lt;= 10^4</pre><h4>Solutions for Kth Largest Element in an Array</h4><h4>Approach 1: Bubble sort</h4><p>We can use <a href="https://www.geeksforgeeks.org/bubble-sort/">Bubble sort</a> to find the Kth largest element in an array.</p><ol><li>We modify the Bubble sort to run the outer loop at most K times.</li><li>At the end of the last loop, print the K — 1 th element.</li></ol><p>A C++ snippet of this approach is as follows:</p><pre>// A function to implement bubble sort<br>void bubbleSort(vector&lt;int&gt;&amp; nums, int n){<br>    int i, j;<br><br>    // run the outer loop k - 1 times<br>    for (i = 0; i &lt; k; i++)<br>        for (j = 0; j &lt; n - i - 1; j++)<br>            if (nums[j] &gt; nums[j + 1])<br>                swap(nums[j], nums[j + 1]);<br><br>    return nums[k - 1];<br>}</pre><p>The time complexity of the Bubble sort is <strong>O(n ^ 2)</strong>. But in this case, we are running the outer loop k times. The time complexity of this approach is <strong>O(n * k)</strong>.</p><p>We are not using additional space, so the space complexity is <strong>O(1)</strong>.</p><h4>Approach 2: Sorting</h4><p>The naive approach is to sort the given array in descending order and return the k — 1 index (0 — Based indexing) element.</p><p>A C++ snippet of the above approach looks as below:</p><pre>// C++ code for K largest elements in an array<br>int findKthLargest(vector&lt;int&gt;&amp; nums, int k) {<br>    int n = nums.size();<br><br>    sort(nums, nums + n, greater&lt;int&gt;());<br><br>    return nums[k - 1];<br>}</pre><p>The time complexity of this approach is <strong>O(n * log(n)),</strong> and the space complexity is <strong>O(1)</strong>.</p><h4>Approach 3: Min-Heap</h4><p>We create a <a href="https://en.wikipedia.org/wiki/Min-max_heap">Min Heap</a> of size K and compare the root of the Min Heap with other elements on the array. If the element is greater than the root, we swap the values and heapify the heap.</p><p>We need to execute the following steps to find the Kth largest element in an array:</p><ol><li>Build a Min Heap for the first k elements of the array: nums[0] to nums[k — 1].</li><li>Iterate over the remaining elements from nums[k] to nums[n — 1].</li><li>Compare the array element with the root of the heap.</li><li>If the element is greater than the root, heapify the heap else, do nothing.</li><li>After the above steps are done, our Min heap has the K largest elements of the array, and the root is the Kth largest element.</li></ol><p>A C++ snippet of this approach is as follows:</p><pre>int swap(int&amp; x, int&amp; y) {<br>    int temp = x;<br>    x = y;<br>    y = temp;<br>}<br><br>// Min Heap Class<br>class MinHeap {<br>    int size;<br>    int* arr;<br><br>public:<br>    MinHeap(int size, int input[]);<br>    void heapify(int i);<br>    void buildHeap();<br>};<br><br>MinHeap::MinHeap(int size, int input[]) {<br>    this-&gt;size = size;<br>    this-&gt;arr = input;<br><br>    buildHeap();<br>}<br><br>// Min Heapify function, that assumes<br>// 2 * i + 1 and 2 * i + 2 are min heap and<br>// fix min heap property for i<br>void MinHeap::heapify(int i) {<br>    // if Leaf Node, simply return<br>    if (i &gt;= size / 2)<br>        return;<br><br>    int smallest;<br><br>    // index of left node<br>    int left = 2 * i + 1;<br><br>    // index of right node<br>    int right = 2 * i + 2;<br><br>    // Select minimum from left node and<br>    // current node i, and store the minimum<br>    // index in smallest variable<br>    smallest = arr[left] &lt; arr[i] ? left : i;<br><br>    // If right child exist, compare and<br>    // update the smallest variable<br>    if (right &lt; size)<br>        smallest = arr[right] &lt; arr[smallest] ? right : smallest;<br><br>    // If Node i violates the min heap<br>    // property, swap  current node i with<br>    // smallest to fix the min-heap property<br>    // and recursively call heapify for node smallest.<br>    if (smallest != i) {<br>        swap(arr[i], arr[smallest]);<br>        heapify(smallest);<br>    }<br>}<br><br>// Build Min Heap<br>void MinHeap::buildHeap() {<br>    // Calling Heapify for all non leaf nodes<br>    for (int i = size / 2 - 1; i &gt;= 0; i--) {<br>        heapify(i);<br>    }<br>}<br><br>int findKthLargest(vector&lt;int&gt;&amp; nums[], int size, int k) {<br>    // create Min Heap for given array with only k elements<br>    MinHeap* m = new MinHeap(k, nums);<br><br>    // Loop For each element in array<br>    // after the kth element<br>    for (int i = k; i &lt; size; i++) {<br>        // if current element is smaller<br>        // than minimum element, do nothing<br>        // and continue to next element<br>        if (nums[0] &gt; nums[i])<br>            continue;<br><br>        // Otherwise Change minimum element to<br>        // current element, and call heapify to<br>        // restore the heap property<br>        else {<br>            nums[0] = nums[i];<br>            m-&gt;heapify(0);<br>        }<br>    }<br><br>    // now min heap contains k maximum elements, print the root element as it is the<br>    // Kth largest element of the array<br>    return nums[0];<br>}</pre><p>The time complexity of this approach is <strong>O(n * log k)</strong> and the space complexity is <strong>O(k)</strong>.</p><h4>Approach 4: Priority Queue</h4><p>Instead of Min Heap, we can use a <a href="https://www.geeksforgeeks.org/priority-queue-in-cpp-stl">Priority queue</a> to get the Kth largest element.</p><p><strong>Note:</strong> A Priority Queue is implemented as Max Heap by default in C++.</p><p>We need to execute the following steps to find the Kth largest element in an array:</p><ol><li>Iterate over the array and insert the elements in the priority queue.</li><li>If the queue size exceeds k, pop the element from the priority queue.</li><li>Once we have iterated over the array, return the top element of the priority queue.</li></ol><p>A C++ snippet of this approach is as follows:</p><pre>int findKthLargest(vector&lt;int&gt;&amp; nums, int k) {<br>    // initialize priority queue<br>    priority_queue&lt;int, vector&lt;int&gt;, greater&lt;int&gt;&gt; pq;<br><br>    // push all the elements<br>    for (int i = 0; i &lt; nums.size(); i++) {<br>        pq.push(nums[i]);<br><br>        // if the queue side exceeds k, pop the top element<br>        if (pq.size() &gt; k) {<br>            pq.pop();<br>        }<br>    }<br><br>    // return the top element of the priority queue<br>    return pq.top();<br>}</pre><p>The time complexity of this approach is <strong>O(n * log k)</strong> and the space complexity is <strong>O(k)</strong>.</p><h4>Approach 5: Using a Binary Search Tree</h4><p>We can create a <a href="https://www.geeksforgeeks.org/introduction-to-binary-search-tree-data-structure-and-algorithm-tutorials/">Binary Search Tree</a> from the array elements and get the K largest elements of the array.</p><p>We need to execute the following steps:</p><ol><li>Create a BST by iterating over the array elements.</li><li>Traverse the BST in reverse inorder for K times.</li><li>Return the Kth largest element.</li></ol><p>A C++ snippet of this approach is as follows:</p><pre>struct Node {<br>    int data;<br>    struct Node* left;<br>    struct Node* right;<br>};<br><br>class Tree {<br>public:<br>    Node* root = NULL;<br>    void addNode(int data) {<br>        Node* newNode = new Node();<br>        newNode-&gt;data = data;<br><br>        if (!root) {<br>            root = newNode;<br>        } else {<br>            Node* cur = root;<br>            while (cur) {<br>                if (cur-&gt;data &gt; data) {<br>                    if (cur-&gt;left) {<br>                        cur = cur-&gt;left;<br>                    } else {<br>                        cur-&gt;left = newNode;<br>                        return;<br>                    }<br>                } else {<br>                    if (cur-&gt;right) {<br>                        cur = cur-&gt;right;<br>                    } else {<br>                        cur-&gt;right = newNode;<br>                        return;<br>                    }<br>                }<br>            }<br>        }<br>    }<br><br>    void printGreatest(int&amp; K, vector&lt;int&gt;&amp; sol, Node* node) {<br>        if (!node || K == 0)<br>            return;<br><br>        printGreatest(K, sol, node-&gt;right);<br><br>        if (K &lt;= 0)<br>            return;<br><br>        sol.push_back(node-&gt;data);<br>        K--;<br><br>        printGreatest(K, sol, node-&gt;left);<br>    }<br>};<br><br>int findKthLargest(vector&lt;int&gt;&amp; nums, int k) {<br>    vector&lt;int&gt; sol;<br>    Tree tree = new Tree();<br><br>    for (int i = 0; i &lt; nums.size(); i++) {<br>        tree.addNode(nums[i]);<br>    }<br><br>    tree.printGreatest(k, sol, tree.root);<br><br>    return sol[k - 1];<br>}</pre><p>The time complexity of this approach is <strong>O(n * log(n))</strong>. The space complexity is <strong>O(n)</strong>.</p><h4>Approach 6: Using Quick Sort</h4><p>We can modify the <a href="https://www.geeksforgeeks.org/quick-sort">Quick Sort algorithm</a> to find the Kth largest element. Let’s check the algorithm directly.</p><p>Algorithm</p><pre>// findKthLargest(vector&lt;int&gt;&amp; nums, int k)<br>- set n = nums.size()<br><br>- if n == 1<br>  - return nums[0]<br>- end if<br><br>- set l = 0, h = n - 1<br>  target = n - k<br><br>- loop while l &lt;= h<br>  - set pivot = partition(nums, l, h)<br><br>  - if pivot &lt; target<br>    - set l = pivot + 1<br>  - else if pivot &gt; target<br>    - set h = pivot - 1<br>  - else<br>    - return nums[pivot]<br>  - end if<br>- end while<br><br>- return -1<br><br>// partition(vector&lt;int&gt; &amp;nums, int l, int h)<br>- set high = nums[h]<br>      start = l<br><br>- loop for i = l; i &lt; h; i++<br>  - if nums[i] &lt; high<br>    - swap(nums[start], nums[i])<br>    - start++<br>  - end if<br>- end for<br><br>- swap(nums[start], nums[h])<br><br>- return start</pre><p>The time complexity of the above approach is <strong>O(n * log(n))</strong>, and the space complexity is <strong>O(1)</strong>.</p><p>Check out our solutions in <strong>C++</strong>, <strong>Golang</strong>, and <strong>Javascript</strong>.</p><h4>C++ solution</h4><pre>class Solution {<br>public:<br>    int findKthLargest(vector&lt;int&gt;&amp; nums, int k) {<br>        int n = nums.size();<br><br>        // if nums size is 1 return the first element<br>        if (n == 1) {<br>            return nums[0];<br>        }<br><br>        int l = 0, h = n - 1;<br><br>        // set target to n - k<br>        int target = n - k;<br><br>        while (l &lt;= h) {<br>            // set pivot with the value returned by partition function<br>            int pivot = partition(nums, l, h);<br><br>            // if the pivot is less than the target, search the right side<br>            if (pivot &lt; target) {<br>                l = pivot + 1;<br>            } else if (pivot &gt; target) {<br>                // if the pivot is greater than the target, search the left side<br>                h = pivot - 1;<br>            } else {<br>                // if the pivot is equal to the target, return nums[pivot]<br>                return nums[pivot];<br>            }<br>        }<br><br>        return -1;<br>    }<br><br>    int partition(vector&lt;int&gt; &amp;nums, int l, int h) {<br>        int high = nums[h];<br>        int start = l;<br><br>        for (int i = l; i &lt; h; i++) {<br>            // if nums[i] is less than high, then swap nums[start] with nums[i]<br>            if (nums[i] &lt; high) {<br>                swap(nums[start], nums[i]);<br>                start++;<br>            }<br>        }<br><br>        //swap nums[start] with nums[h]<br>        swap(nums[start], nums[h]);<br><br>        return start;<br>    }<br>};</pre><h4>Golang solution</h4><pre>func findKthLargest(nums []int, k int) int {<br>    n := len(nums)<br><br>    // if nums size is 1 return the first element<br>    if n == 1 {<br>        return nums[0]<br>    }<br><br>    l, h := 0, n - 1<br><br>    // set target to n - k<br>    target := n - k<br><br>    for l &lt;= h {<br>        // set pivot with the value returned by partition function<br>        pivot := partition(nums, l, h)<br><br>        // if the pivot is less than the target, search the right side<br>        if pivot &lt; target {<br>            l = pivot + 1<br>        } else if pivot &gt; target {<br>            // if the pivot is greater than the target, search the left side<br>            h = pivot - 1<br>        } else {<br>            // if the pivot is equal to the target, return nums[pivot]<br>            return nums[pivot]<br>        }<br>    }<br><br>    return -1<br>}<br><br>func partition(nums []int, l, h int) int {<br>    high := nums[h]<br>    start := l<br><br>    for i := l; i &lt; h; i++ {<br>        if nums[i] &lt; high {<br>            // if nums[i] is less than high, then swap nums[start] with nums[i]<br>            nums[start], nums[i] = nums[i], nums[start]<br>            start++<br>        }<br>    }<br><br>    //swap nums[start] with nums[h]<br>    nums[start], nums[h] = nums[h], nums[start]<br><br>    return start<br>}</pre><h4>JavaScript solution</h4><pre>/**<br> * @param {number[]} nums<br> * @param {number} k<br> * @return {number}<br> */<br>var findKthLargest = function(nums, k) {<br>    let n = nums.length;<br><br>    // if nums size is 1 return the first element<br>    if (n == 1) {<br>        return nums[0];<br>    }<br><br>    let l = 0, h = n - 1;<br><br>    // set target to n - k<br>    let target = n - k;<br><br>    while (l &lt;= h) {<br>        // set pivot with the value returned by partition function<br>        let pivot = partition(nums, l, h);<br><br>        // if the pivot is less than the target, search the right side<br>        if (pivot &lt; target) {<br>            l = pivot + 1;<br>        } else if (pivot &gt; target) {<br>            // if the pivot is greater than the target, search the left side<br>            h = pivot - 1;<br>        } else {<br>            // if the pivot is equal to the target, return nums[pivot]<br>            return nums[pivot];<br>        }<br>    }<br><br>    return -1;<br>};<br><br>var partition = function(nums, l, h) {<br>    let high = nums[h];<br>    let start = l;<br><br>    for (let i = l; i &lt; h; i++) {<br>        // if nums[i] is less than high, then swap nums[start] with nums[i]<br>        if (nums[i] &lt; high) {<br>            [nums[start], nums[i]] = [nums[i], nums[start]];<br>            start++;<br>        }<br>    }<br><br>    //swap nums[start] with nums[h]<br>    [nums[start], nums[h]] = [nums[h], nums[start]];<br><br>    return start;<br>}</pre><h4>Dry Run</h4><p>Let’s dry-run our algorithm to see how the solution works.</p><pre>Input: nums = [3, 2, 1, 5, 6, 4]<br>       k = 2<br><br>// findKthLargest(vector&lt;int&gt;&amp; nums, int k)<br>Step 1: n = nums.size()<br>          = 6<br><br>Step 2: if n == 0<br>           6 == 0<br>           false<br><br>Step 3: l = 0<br>        h = n - 1<br>          = 6 - 1<br>          = 5<br><br>        target = n - k<br>               = 6 - 2<br>               = 4<br><br>Step 4: loop while l &lt;= h<br>          0 &lt;= 5<br>          true<br><br>          pivot = partition(nums, l, h)<br>                = partition(nums, 0, 5)<br><br>// partition(nums, 0, 5)<br>Step 5: high = nums[h]<br>             = nums[5]<br>             = 4<br>        start = l<br>              = 0<br><br>        loop for i = l; i &lt; h<br>          i &lt; h<br>          0 &lt; 5<br>          true<br><br>          if nums[i] &lt; high<br>            nums[0] &lt; 4<br>            3 &lt; 4<br>            true<br><br>            swap(nums[start], nums[i])<br>            swap(nums[0], nums[0])<br>            nums = [3, 2, 1, 5, 6, 4]<br><br>            start++<br>            start = 1<br><br>            i++<br>            i = 1<br><br>        loop for i &lt; h<br>          i &lt; h<br>          1 &lt; 5<br>          true<br><br>          if nums[i] &lt; high<br>            nums[1] &lt; 4<br>            2 &lt; 4<br>            true<br><br>            swap(nums[start], nums[i])<br>            swap(nums[1], nums[1])<br>            nums = [3, 2, 1, 5, 6, 4]<br><br>            start++<br>            start = 2<br><br>            i++<br>            i = 2<br><br>        loop for i &lt; h<br>          i &lt; h<br>          2 &lt; 5<br>          true<br><br>          if nums[i] &lt; high<br>            nums[2] &lt; 4<br>            1 &lt; 4<br>            true<br><br>            swap(nums[start], nums[i])<br>            swap(nums[2], nums[2])<br>            nums = [3, 2, 1, 5, 6, 4]<br><br>            start++<br>            start = 3<br><br>            i++<br>            i = 3<br><br>        loop for i &lt; h<br>          i &lt; h<br>          3 &lt; 5<br>          true<br><br>          if nums[i] &lt; high<br>            nums[3] &lt; 4<br>            5 &lt; 4<br>            false<br><br>            i++<br>            i = 4<br><br>        loop for i &lt; h<br>          i &lt; h<br>          4 &lt; 5<br>          true<br><br>          if nums[i] &lt; high<br>            nums[4] &lt; 4<br>            6 &lt; 4<br>            false<br><br>            i++<br>            i = 5<br><br>        loop for i &lt; h<br>          i &lt; h<br>          5 &lt; 5<br>          false<br><br>        swap(nums[start], nums[h])<br>        swap(nums[3], nums[5])<br>        swap(5, 4)<br>        nums = [3, 1, 2, 4, 6, 5]<br><br><br>        return start<br>        return 3<br><br>// findKthLargest(vector&lt;int&gt;&amp; nums, int k)<br>Step 6: pivot = partition(nums, 0, 5)<br>              = 3<br><br>Step 7: if pivot &lt; target<br>           3 &lt; 4<br>           true<br><br>           l = pivot + 1<br>             = 3 + 1<br>             = 4<br><br>Step 8 loop while l &lt;= h<br>         4 &lt;= 5<br>         true<br><br>         pivot = partition(nums, l, h)<br>               = partition(nums, 4, 5)<br><br>// partition(nums, 4, 5)<br>Step 9: high = nums[h]<br>             = nums[5]<br>             = 5<br>        start = l<br>              = 4<br><br>        loop for i = l; i &lt; h<br>          i &lt; h<br>          4 &lt; 5<br>          true<br><br>          if nums[i] &lt; high<br>             nums[4] &lt; 5<br>             6 &lt; 5<br>             false<br><br>          i++<br>          i = 5<br><br>        loop for i &lt; h<br>          5 &lt; 5<br>          false<br><br>        swap(nums[start], nums[h])<br>        swap(nums[4], nums[5])<br>        swap(6, 5)<br><br>        nums = [3, 1, 2, 4, 5, 6]<br><br>        return start<br>        return 4<br><br>// findKthLargest(vector&lt;int&gt;&amp; nums, int k)<br>Step 10: pivot = partition(nums, 4, 5)<br>               = 4<br><br>Step 11: if pivot &lt; target<br>           4 &lt; 4<br>           false<br>         else if pivot &gt; target<br>           4 &gt; 4<br>           false<br>         else<br>           return nums[4]<br>           return 5<br><br>We return the answer as 5.</pre><p><em>Originally posted at </em><a href="https://alkeshghorpade.me/post/leetcode-kth-largest-element-in-an-array"><em>https://alkeshghorpade.me</em></a><em>.</em></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=614898a77166" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Word Ladder — LeetCode]]></title>
            <link>https://alkesh26.medium.com/word-ladder-leetcode-8f292482c4dc?source=rss-5b66f0dd7bcd------2</link>
            <guid isPermaLink="false">https://medium.com/p/8f292482c4dc</guid>
            <category><![CDATA[algorithms]]></category>
            <category><![CDATA[javascript]]></category>
            <category><![CDATA[leetcode]]></category>
            <category><![CDATA[programming]]></category>
            <category><![CDATA[golang]]></category>
            <dc:creator><![CDATA[Alkesh Ghorpade]]></dc:creator>
            <pubDate>Thu, 01 Jun 2023 18:40:01 GMT</pubDate>
            <atom:updated>2023-06-05T14:18:14.706Z</atom:updated>
            <content:encoded><![CDATA[<h3>Word Ladder — LeetCode</h3><h3>Problem statement</h3><p>A <strong>transformation sequence</strong> from word beginWord to word endWord using a dictionary wordList is a sequence of words beginWord -&gt; s1 -&gt; s2 -&gt; ... -&gt; sk such that:</p><p>Given two words, beginWord and endWord, and a dictionary wordList, <em>return the </em><strong><em>number of words</em></strong><em> in the </em><strong><em>shortest transformation sequence</em></strong><em> from beginWord to endWord, or 0 if no such sequence exists.</em></p><p>Problem statement taken from: <a href="https://leetcode.com/problems/word-ladder">https://leetcode.com/problems/word-ladder</a>.</p><p><strong>Example 1:</strong></p><pre>Input: beginWord = &#39;hit&#39;, endWord = &#39;cog&#39;, wordList = [&#39;hot&#39;, &#39;dot&#39;, &#39;dog&#39;, &#39;lot&#39;, &#39;log&#39;, &#39;cog&#39;]<br>Output: 5<br>Explanation: One shortest transformation sequence is &#39;hit&#39; -&gt; &#39;hot&#39; -&gt; &#39;dot&#39; -&gt; &#39;dog&#39; -&gt; cog&#39;, which is 5 words long.</pre><p><strong>Example 2:</strong></p><pre>Input: beginWord = &#39;hit&#39;, endWord = &#39;cog&#39;, wordList = [&#39;hot&#39;, &#39;dot&#39;, &#39;dog&#39;, &#39;lot&#39;, &#39;log&#39;]<br>Output: 0<br>Explanation: The endWord &#39;cog&#39; is not in wordList, therefore there is no valid transformation sequence.</pre><p><strong>Constraints:</strong></p><pre>- 1 &lt;= beginWord.length &lt;= 10<br>- endWord.length == beginWord.length<br>- 1 &lt;= wordList.length &lt;= 5000<br>- wordList[i].length == beginWord.length<br>- beginWord, endWord, and wordList[i] consist of lowercase English letters<br>- beginWord != endWord<br>- All the words in wordList are unique.</pre><h3>Solutions for World Ladder</h3><h4>Approach 1</h4><p>The idea is to use <a href="https://www.geeksforgeeks.org/breadth-first-search-or-bfs-for-a-graph/">BFS traversal</a>. Two adjacent words can be considered as nodes of the graph. The count of the number of different characters between the two words can be considered as the distance. If the difference is 1, we return the count. Else we consider every other word in the wordList and check the difference. If the difference is 1, we push the word to the queue.</p><p>The algorithmic flow of this approach is as follows:</p><pre>- i = 1<br>  q = new Queue()<br>  q.push(beginWord)<br>  set count = 1<br><br>- initialize set&lt;string&gt; s<br>  s.insert(begin)<br><br>- loop while !q.empty()<br>  - size = q.size()<br><br>  - for i = 0; i &lt; size; i++<br>    - currentWord = q.first()<br>    - q.pop()<br><br>    - if currentWord == endWord<br>      - return count<br>    - end if<br><br>    // check stores the count of the number of characters different<br>    // in the currentWord and endWord<br>    - check = 0<br><br>    - for i = 0; i &lt; currentWord.length; i++<br>      - if currentWord[i] != endWord[i]<br>        - count++<br>      - end if<br>    - end for<br><br>    // if the number of different characters is 1, this means<br>    // we have reached the endWord and return count<br>    - if check == 1<br>      - return count<br>    - end if<br><br>    // add the next word to the queue<br>    - loop for j = 0; j &lt; wordList.size(); j++<br>      - set diff = 0<br><br>      - loop for k = 0; k &lt; currentWord.size(); k++<br>        - if currentWord[k] != wordList[j][k]<br>          - increment diff++<br>        - end if<br>      - end for<br><br>      - if diff == 1<br>        - if<br>      - end if<br>    - end for<br>  - end for<br><br>- end while<br><br>// if we cannot reach the endWord, we return -1<br>- return -1</pre><p>The time complexity of this approach is <strong>O(n * n * m)</strong>. Where m is the length of each string. The space complexity is <strong>O(n)</strong>, as we are using an additional space in terms of the queue.</p><h4>Approach 2</h4><p>Another approach is to use BFS traversal along with <a href="https://www.geeksforgeeks.org/introduction-to-trie-data-structure-and-algorithm-tutorials">Trie data structure</a>.</p><p>The algorithmic flow of this approach is as follows:</p><pre>- set TrieNode *root =  new TrieNode<br><br>- q = new Queue()<br>  q.push(beginWord)<br><br>  // create a hash map of visited node<br>  unordered_map&lt;string, int&gt; map;<br><br>  - for i = 0; i &lt; wordList.size; i++<br>    - map[wordList[i]] = 0<br>  - end for<br><br>  map[beginWord] = 1<br><br>  - loop while !q.empty()<br>    - currentWord = q.first()<br>    - q.pop()<br><br>    - if currentWord == endWord<br>      - return map[str]<br>    - end if<br><br>    // initialize allPossible vector<br>    - vector&lt;string&gt; allPossible<br><br>    - allPermutations(root, currentWord, allPossible)<br><br>    - loop for string x: allPossible<br>      - if map.count(x) == 0<br>        - q.push(x)<br>        - map[x] = map[str] + 1<br>      - end if<br>    - end for<br>  - end while<br>-<br><br>// allPermutations(root, currentWord, allPossible, currentString = &#39;&#39;, changed = false, i = 0)<br>- if root == NULL<br>  - return<br>- end if<br><br>- if currentWord.size() == currentString.size()<br>  - if root -&gt; endOfWord<br>    - allPossible.push_back(currentString)<br>    - return<br>  - end if<br>- end if<br><br>- loop for auto x: root -&gt; children<br>  - currentString.push_back(x.first)<br><br>  - if x.first == currentWord[i]<br>    - allPermutations(x.second, currentWord, allPossible, currentString, changed, i + 1)<br>  - else if !changed<br>    - allPermutations(x.second, currentWord, allPossible, currentString, !changed, i + 1)<br>  - end if<br><br>  // BackTrack.<br>  currentString.pop_back();<br>- end for</pre><p>This approach&#39;s time and space complexity is <strong>O(n * m * m)</strong>. Where m is the length of each string.</p><h4>Approach 3</h4><p>Another approach to solving this problem via the BFS approach is using a Queue and Set. To find the shortest path, we start from the beginWord and push it into a queue. If the endWord is found, then we return that level of BFS. If we fail to find the endWord in the first iteration, we generate all the words by replacing each character in the string with a till z. When the endWord is found, we return the length of the shortest chain of words.</p><p>Algorithm</p><p>The algorithmic flow of this approach is as follows:</p><pre>- create set set&lt;string&gt; s(wordList.begin(), wordList.end())<br><br>// If the target endWord is not<br>// present in the set return 0<br>- if s.find(endWord) == s.end()<br>  - return 0<br>- end if<br><br>// initialize queue and push the startWord<br>- queue&lt;string&gt; q<br>  q.push(beginWord)<br><br>- set result = 0<br>  initialize i, j, size<br>  char k<br>  string currentWord<br>  int wordLength = beginWord.size()<br><br>- loop while !q.empty<br>  - ++result<br>  - size = q.size()<br><br>  // update the queue while traversing with words<br>  // that are present in the set<br>  - loop for i = 0; i &lt; size; i++<br>    - currentWord = q.front()<br>    - q.pop()<br><br>    // loop to traverse every character of the word<br>    - loop for j = 0; j &lt; wordLength; j++<br>      - set char originalChar = currentWord[j]<br><br>      // replace the current character in the word<br>      // with every possible alphabhet<br>      - loop for k = &#39;a&#39;; k &lt;= &#39;z&#39;; k++<br>        - set currentWord[j] = k<br><br>        // if we find the endWord, return result + 1<br>        - if currentWord == endWord<br>          - return result + 1<br>        - end if<br><br>        // if the currentWord is not in the set, continue<br>        // the loop else remove it from the set<br>        - if s.find(currentWord) == s.end()<br>          - continue<br>        - end if<br><br>        // push the newly generated word to the queue<br>        q.push(currentWord)<br>      - end for<br><br>      - currentWord[j] = originalChar<br>    - end for<br>  - end for<br><br>- end while<br><br>- return 0</pre><p>The time complexity of the above approach is <strong>O(n)</strong>, and the space complexity is <strong>O(1)</strong>.</p><p>Check out our solutions in <strong>C++</strong>, <strong>Golang</strong>, and <strong>Javascript</strong>.</p><h4>C++ solution</h4><pre>class Solution {<br>public:<br>    int ladderLength(string beginWord, string endWord, vector&lt;string&gt;&amp; wordList) {<br>        set&lt;string&gt; s(wordList.begin(), wordList.end());<br><br>        // If the target endWord is not<br>        // present in the set return 0<br>        if(s.find(endWord) == s.end()) {<br>            return 0;<br>        }<br><br>        queue&lt;string&gt; q;<br>        // push the beginWord to queue<br>        q.push(beginWord);<br><br>        int result = 0;<br>        int i, j, size;<br>        char k;<br>        string currentWord;<br>        int wordLength = beginWord.size();<br><br>        // While the queue is non-empty<br>        while(!q.empty()) {<br>            ++result;<br>            size = q.size();<br><br>            // update the queue while traversing with words<br>            // that are present in the set<br>            for(i = 0; i &lt; size; i++) {<br>                currentWord = q.front();<br>                q.pop();<br><br>                // loop to traverse every character of the word<br>                for(j = 0; j &lt; wordLength; j++) {<br>                    char originalChar = currentWord[j];<br><br>                    // replace the current character in the word<br>                    // with every possible alphabhet<br>                    for(k = &#39;a&#39;; k &lt;= &#39;z&#39;; k++) {<br>                        currentWord[j] = k;<br><br>                        // if we find the endWord, return result + 1<br>                        if(currentWord == endWord) {<br>                            return result + 1;<br>                        }<br><br>                        // if the currentWord is not in the set, continue<br>                        // the loop else remove it from the set<br>                        if(s.find(currentWord) == s.end()) {<br>                            continue;<br>                        }<br>                        s.erase(currentWord);<br><br>                        // push the newly generated word to the queue<br>                        q.push(currentWord);<br>                    }<br><br>                    currentWord[j] = originalChar;<br>                }<br>            }<br>        }<br><br>        return 0;<br>    }<br>};</pre><h4>Golang solution</h4><pre>func ladderLength(beginWord string, endWord string, wordList []string) int {<br>    s := make(map[string]bool)<br>    for _, word := range wordList {<br>        s[word] = true<br>    }<br><br>    // If the target endWord is not<br>    // present in the set return 0<br>    if _, ok := s[endWord]; !ok {<br>        return 0<br>    }<br><br>    q := []string{}<br>    // push the beginWord to queue<br>    q = append(q, beginWord)<br><br>    result := 0<br>    wordLength := len(beginWord)<br><br>    // While the queue is non-empty<br>    for len(q) &gt; 0 {<br>        result += 1<br>        size := len(q)<br><br>        // update the queue while traversing with words<br>        // that are present in the set<br>        for i := 0; i &lt; size; i++ {<br>            currentWord := q[0]<br>            q = q[1:]<br><br>            // loop to traverse every character of the word<br>            for j := 0; j &lt; wordLength; j++ {<br>                originalChar := currentWord[j]<br><br>                // replace the current character in the word<br>                // with every possible alphabhet<br>                for k := &#39;a&#39;; k &lt;= &#39;z&#39;; k++ {<br>                    currentWord = replaceAtIndex(currentWord, k, j)<br><br>                    // if we find the endWord, return result + 1<br>                    if currentWord == endWord {<br>                        return result + 1<br>                    }<br><br>                    // if the currentWord is not in the set, continue<br>                    // the loop else remove it from the set<br>                    if _, ok := s[currentWord]; !ok {<br>                        continue<br>                    }<br><br>                    delete(s, currentWord)<br><br>                    // push the newly generated word to the queue<br>                    q = append(q, currentWord)<br>                }<br><br>                currentWord = replaceAtIndex(currentWord, rune(originalChar), j)<br>            }<br>        }<br>    }<br><br>    return 0<br>}<br><br>func replaceAtIndex(in string, r rune, i int) string {<br>    out := []rune(in)<br>    out[i] = r<br>    return string(out)<br>}</pre><h4>JavaScript solution</h4><pre>/**<br> * @param {string} beginWord<br> * @param {string} endWord<br> * @param {string[]} wordList<br> * @return {number}<br> */<br>var ladderLength = function(beginWord, endWord, wordList) {<br>    var s = new Set(wordList);<br><br>    // If the target endWord is not<br>    // present in the set return 0<br>    if(!s.has(endWord)) {<br>        return 0;<br>    }<br><br>    // variable q will act as queue<br>    var q = [];<br>    // push the beginWord to queue<br>    q.push(beginWord);<br><br>    let result = 0;<br>    let i, j, size;<br>    let k;<br>    let currentWord;<br>    let wordLength = beginWord.length;<br><br>    // While the queue is non-empty<br>    while(q.length !== 0) {<br>        ++result;<br>        size = q.length;<br><br>        // update the queue while traversing with words<br>        // that are present in the set<br>        for(i = 0; i &lt; size; i++) {<br>            currentWord = q.shift();<br><br>            // loop to traverse every character of the word<br>            for(j = 0; j &lt; wordLength; j++) {<br>                let originalChar = currentWord[j];<br><br>                // replace the current character in the word<br>                // with every possible alphabhet<br>                for(k = 97; k &lt;= 122; k++) {<br>                    currentWord = currentWord.substring(0, j) + String.fromCharCode(k) + currentWord.substring(j + 1);<br><br>                    // if we find the endWord, return result + 1<br>                    if(currentWord === endWord) {<br>                        return result + 1;<br>                    }<br><br>                    // if the currentWord is not in the set, continue<br>                    // the loop else remove it from the set<br>                    if(!s.has(currentWord)) {<br>                        continue;<br>                    }<br>                    s.delete(currentWord);<br><br>                    // push the newly generated word to the queue<br>                    q.push(currentWord);<br>                }<br><br>                currentWord = currentWord.substring(0, j) + originalChar + currentWord.substring(j + 1);<br>            }<br>        }<br>    }<br><br>    return 0;<br>};</pre><h4>Dry Run</h4><p>Let’s dry-run our algorithm to see how the solution works.</p><pre>Input: beginWord = &#39;hit&#39;, endWord = &#39;cog&#39;, wordList = [&#39;hot&#39;, &#39;dot&#39;, &#39;dog&#39;, &#39;lot&#39;, &#39;log&#39;, &#39;cog&#39;]<br><br>Step 1: set&lt;string&gt; s(wordList.begin(), wordList.end())<br>        s = [&#39;hot&#39;, &#39;dot&#39;, &#39;dog&#39;, &#39;lot&#39;, &#39;log&#39;, &#39;cog&#39;]<br><br>Step 2: if s.find(endWord) == s.end()<br>           s.find(&#39;cog&#39;) == s.end()<br>           false<br><br>Step 3: queue&lt;string&gt; q<br>        q = []<br>        q.push(startWord)<br>        q = [&#39;hit&#39;]<br><br>        int result = 0<br>        int i, j, size<br>        char k<br>        string currentWord<br>        wordLength = beginWord.size()<br>                   = &#39;hit&#39;.size()<br>                   = 3<br><br>Step 4: loop while !q.empty()<br>          q = [&#39;hit&#39;]<br>          q.empty() = false<br>          !q.empty()<br>          true<br><br>          ++result<br>          result = 1<br><br>          size = q.size()<br>               = 1<br><br>          loop for i = 0; i &lt; size;<br>            i &lt; size<br>            0 &lt; 1<br>            true<br><br>            currentWord = q.front()<br>                        = &#39;hit&#39;<br><br>            q.pop()<br>            q = []<br><br>            loop for j = 0; j &lt; wordLength<br>              j &lt; wordLength<br>              0 &lt; 3<br>              true<br><br>              originalChar = currentWord[j]<br>                           = &#39;hit&#39;[0]<br>                           = &#39;h&#39;<br><br>              loop for k = &#39;a&#39;; k &lt;= &#39;z&#39;;<br>                a &lt;= &#39;z&#39;<br>                true<br><br>                currentWord[j] = k<br>                currentWord[0] = &#39;a&#39;<br>                currentWord = &#39;ait&#39;<br><br>                if currentWord == endWord<br>                   &#39;ait&#39; == &#39;cog&#39;<br>                   false<br><br>                if s.find(currentWord) == s.end()<br>                   s.find(&#39;ait&#39;) == s.end()<br>                   // as the set s does not include &#39;ait&#39; so the condition is true<br>                   s = [&#39;hot&#39;, &#39;dot&#39;, &#39;dog&#39;, &#39;lot&#39;, &#39;log&#39;, &#39;cog&#39;]<br>                   true<br><br>                   continue<br><br>                k++<br><br>                k = &#39;b&#39;<br><br>                the loop continues till &#39;z&#39; as we don&#39;t have any word<br>                &#39;bit&#39;, &#39;cit&#39;,...&#39;hit&#39;...&#39;zit&#39; in the list.<br><br>            currentWord[j] = originalChar<br>            currentWord[0] = &#39;h&#39;<br>            currentWord = &#39;hit&#39;<br><br>            j++<br>            j = 1<br><br>            loop for j &lt; wordLength<br>              j &lt; wordLength<br>              1 &lt; 3<br>              true<br><br>              originalChar = currentWord[j]<br>                           = &#39;hit&#39;[1]<br>                           = &#39;i&#39;<br><br>              loop for k = &#39;a&#39;; k &lt;= &#39;z&#39;;<br>                a &lt;= &#39;z&#39;<br>                true<br><br>                currentWord[j] = k<br>                currentWord[1] = &#39;a&#39;<br>                currentWord = &#39;hat&#39;<br><br>                if currentWord == endWord<br>                   &#39;hat&#39; == &#39;cog&#39;<br>                   false<br><br>                if s.find(currentWord) == s.end()<br>                   s.find(&#39;hat&#39;) == s.end()<br>                   // as the set s does not include &#39;hat&#39; so the condition is true<br>                   s = [&#39;hot&#39;, &#39;dot&#39;, &#39;dog&#39;, &#39;lot&#39;, &#39;log&#39;, &#39;cog&#39;]<br>                   true<br><br>                   continue<br><br>                k++<br><br>                k = &#39;b&#39;<br><br>                the loop continues till &#39;n&#39; as we don&#39;t have any word<br>                &#39;hbt&#39;, &#39;hct&#39;, &#39;hdt&#39;..&#39;hnt&#39; in the list.<br><br>                when k = &#39;o&#39;<br>                we get &#39;hot&#39;<br><br>                currentWord[j] = k<br>                currentWord[1] = &#39;o&#39;<br>                currentWord = &#39;hot&#39;<br><br>                if currentWord == endWord<br>                   &#39;hot&#39; == &#39;cog&#39;<br>                   false<br><br>                if s.find(currentWord) == s.end()<br>                   s.find(&#39;hot&#39;) == s.end()<br>                   // as the set s does include &#39;hot&#39; so the condition is false<br>                   s = [&#39;hot&#39;, &#39;dot&#39;, &#39;dog&#39;, &#39;lot&#39;, &#39;log&#39;, &#39;cog&#39;]<br>                   false<br><br>                s.erase(currentWord)<br>                s.erase(&#39;hot&#39;)<br>                s = [&#39;dot&#39;, &#39;dog&#39;, &#39;lot&#39;, &#39;log&#39;, &#39;cog&#39;]<br><br>                q.push(currentWord)<br>                q.push(&#39;hot&#39;)<br>                q = [&#39;hot&#39;]<br><br>                The loop continues till k is equal to `z` and the loop repeats.<br><br>The sequence we follow goes like<br>&#39;hit&#39; -&gt; &#39;hot&#39; -&gt; &#39;dot&#39; -&gt; &#39;dog&#39; -&gt; &#39;cog&#39;<br><br>We return the result as 5.</pre><p><em>Originally published at </em><a href="https://alkeshghorpade.me/post/leetcode-word-ladder"><em>https://alkeshghorpade.me</em></a><em>.</em></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=8f292482c4dc" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Longest Valid Parentheses — LeetCode]]></title>
            <link>https://alkesh26.medium.com/longest-valid-parentheses-leetcode-e4d7918dc6ca?source=rss-5b66f0dd7bcd------2</link>
            <guid isPermaLink="false">https://medium.com/p/e4d7918dc6ca</guid>
            <category><![CDATA[golang]]></category>
            <category><![CDATA[leetcode]]></category>
            <category><![CDATA[programming]]></category>
            <category><![CDATA[javascript]]></category>
            <category><![CDATA[algorithms]]></category>
            <dc:creator><![CDATA[Alkesh Ghorpade]]></dc:creator>
            <pubDate>Sun, 28 May 2023 09:21:21 GMT</pubDate>
            <atom:updated>2023-06-05T14:20:05.104Z</atom:updated>
            <content:encoded><![CDATA[<h3>Longest Valid Parentheses — LeetCode</h3><h4>Problem statement</h4><p>Given a string containing just the characters ‘(‘ and ‘)’, return <em>the length of the longest valid (well-formed) parentheses substring.</em></p><p>Problem statement taken from: <a href="https://leetcode.com/problems/longest-valid-parentheses">https://leetcode.com/problems/longest-valid-parentheses</a></p><p><strong>Example 1:</strong></p><pre>Input: s = &#39;(()&#39;<br>Output: 2<br>Explanation: The longest valid parentheses substring is &#39;()&#39;.</pre><p><strong>Example 2:</strong></p><pre>Input: s = &#39;)()())&#39;<br>Output: 4<br>Explanation: The longest valid parentheses substring is &#39;()()&#39;.</pre><p><strong>Example 3:</strong></p><pre>Input: s = &#39;&#39;<br>Output: 0</pre><p><strong>Constraints:</strong></p><pre>- 0 &lt;= s.length &lt;= 3 * 10^4<br>- s[i] is &#39;(&#39;, or &#39;)&#39;</pre><h4>Solutions for Longest Valid Parentheses</h4><h4>Approach 1: Brute Force</h4><p>The brute force approach is to generate all the substrings and check whether every string is valid parentheses. If the substring is valid and the length exceeds the maximum length seen so far, then update the maximum length. We return this maximum length as the longest valid parentheses.</p><p>The problem with this approach is the time complexity which is <strong>O(n³)</strong>. Three nested for loops will be used. The first two will generate all the substrings, and the third inner loop will verify whether the substring is valid parentheses.</p><h4>Approach 2: Using Stack</h4><p>An efficient way to solve the longest valid parentheses is using a Stack. The solution is similar to our approach in <a href="https://alkeshghorpade.me/post/leetcode-valid-parentheses">valid parentheses</a> problem. Instead of pushing the open brackets ( to the stack, we push the indexes of the opening brackets.</p><p>The algorithm for this approach is as follows:</p><pre>- initialize stack&lt;int&gt; st<br>  // push -1 to the stack to provide the base<br>  // for the next valid set of parentheses<br>  st.push(-1)<br><br>- set result = 0<br><br>- loop for i = 0; i &lt; str.size(); i++<br>  // if opening bracket, push the index i<br><br>  - if str[i] == &#39;(&#39;<br>    - st.push(i)<br><br>  - else<br>    // if str[i] == &#39;)&#39;<br><br>    // pop the last encountered opening bracket&#39;s index<br>    - if !st.empty()<br>      - st.pop()<br>    - end if<br><br>    // if the length formed with the base of the current valid substring<br>    // is more than max so far<br>    - if !st.empty<br>      - set result = max(result, i - st.top())<br>    - else<br>      - st.push(i)<br>    - end if<br>  - end if<br>- end for<br><br>- return result</pre><p>A C++ snippet of this algorithm is as below:</p><pre>int longestValidParentheses(string s) {<br>    stack&lt;int&gt; stk;<br>    stk.push(-1);<br><br>    int result = 0;<br><br>    for (int i = 0; i &lt; str.size(); i++) {<br>        if (str[i] == &#39;(&#39;) {<br>            stk.push(i);<br>        } else {<br>            if (!stk.empty()) {<br>                stk.pop();<br>            }<br><br>            if (!stk.empty()) {<br>                result = max(result, i - stk.top());<br>            } else {<br>                stk.push(i);<br>            }<br>        }<br>    }<br><br>    return result;<br>}</pre><p>The time complexity of this approach is <strong>O(n)</strong> because we are iterating over the string once. The space complexity is also <strong>O(n)</strong>, as we used an additional data structure, Stack.</p><h4>Approach 3: Using left and right counters</h4><p>Using two counters, we can solve this problem in <strong>O(1)</strong> time.</p><ul><li>The idea is to scan the string from left to right.</li><li>We keep track of the number of open and closed braces using left and right counters. We increment the left and right counter by 1 when identifying an opening ( and closing ) braces.</li><li>When the left and right counters are equal, the length of the current substring is calculated. If it exceeds the previous longest valid parentheses, we update the result with the current substring length.</li><li>At any point while scanning, if the right counter value exceeds the left counter, the substring is not a valid parentheses string. We set the left and right counters to 0.</li><li>We then scan the string from right to left and repeat similar steps above.</li></ul><p>Let’s check the algorithm for this approach.</p><h4>Algorithm</h4><pre>- set left, right, maxLength = 0<br>      n = s.length<br><br>- loop for i = 0; i &lt; n; i++<br>  - if s[i] == &#39;(&#39;<br>    - increment left: left++<br>  - else<br>    - increment right: right++<br>  - end if<br><br>  - if left == right<br>    - update maxLength: maxLength = max(maxLength, 2 * right)<br>  - else if right &gt; left<br>    - set left, right = 0, 0<br>  - end if<br>- end for<br><br>- set left, right = 0, 0<br><br>- loop for i = 0; i &lt; n; i++<br>  - if s[i] == &#39;(&#39;<br>    - increment left: left++<br>  - else<br>    - increment right: right++<br>  - end if<br><br>  - if left == right<br>    - update maxLength: maxLength = max(maxLength, 2 * right)<br>  - else if left &gt; right<br>    - set left, right = 0, 0<br>  - end if<br>- end for<br><br>- return maxLength</pre><p>The time complexity of the above approach is <strong>O(n)</strong>, and the space complexity is <strong>O(1)</strong>.</p><p>Check out our solutions in <strong>C++</strong>, <strong>Golang</strong>, and <strong>Javascript</strong>.</p><h4>C++ solution</h4><pre>class Solution {<br>public:<br>    // Main function to return the length of<br>    // the longest valid parentheses<br>    int longestValidParentheses(string s) {<br>        int left = 0, right = 0, maxLength = 0;<br>        int n = s.length();<br><br>        // iterate the string from left to right<br>        for(int i = 0; i &lt; n; i++) {<br>            if(s[i] == &#39;(&#39;) {<br>                left++;<br>            } else {<br>                right++;<br>            }<br><br>            // if left is equal to right, we found a<br>            // valid parentheses substring<br>            if(left == right) {<br>                maxLength = max(maxLength, 2 * right);<br>            } else if (right &gt; left) {<br>                // reset the left and right counter when we have<br>                // invalid parentheses substring<br>                left = 0;<br>                right = 0;<br>            }<br>        }<br><br>        left = 0;<br>        right = 0;<br><br>        // iterate the string from right to left<br>        for(int i = n - 1; i &gt;= 0; i--) {<br>            if(s[i] == &#39;(&#39;) {<br>                left++;<br>            } else {<br>                right++;<br>            }<br><br>            // if left is equal to right, we found a<br>            // valid parentheses substring<br>            if(left == right) {<br>                maxLength = max(maxLength, 2 * right);<br>            } else if (left &gt; right) {<br>                // reset the left and right counter when we have<br>                // invalid parentheses substring<br>                left = 0;<br>                right = 0;<br>            }<br>        }<br><br>        return maxLength;<br>    }<br>};</pre><h4>Golang solution</h4><pre>// Main function to return the length of<br>// the longest valid parentheses<br>func longestValidParentheses(s string) int {<br>    left, right, maxLength := 0, 0, 0<br>    n := len(s)<br><br>    // iterate the string from left to right<br>    for  i := 0; i &lt; n; i++ {<br>        if s[i] == &#39;(&#39; {<br>            left++<br>        } else {<br>            right++<br>        }<br><br>        // if left is equal to right, we found a<br>        // valid parentheses substring<br>        if left == right {<br>            maxLength = max(maxLength, 2 * right)<br>        } else if (right &gt; left) {<br>            // reset the left and right counter when we have<br>            // invalid parentheses substring<br>            left = 0<br>            right = 0<br>        }<br>    }<br><br>    left = 0<br>    right = 0<br><br>    // iterate the string from right to left<br>    for i := n - 1; i &gt;= 0; i-- {<br>        if s[i] == &#39;(&#39; {<br>            left++<br>        } else {<br>            right++<br>        }<br><br>        // if left is equal to right, we found a<br>        // valid parentheses substring<br>        if left == right {<br>            maxLength = max(maxLength, 2 * right)<br>        } else if (left &gt; right) {<br>            // reset the left and right counter when we have<br>            // invalid parentheses substring<br>            left = 0<br>            right = 0<br>        }<br>    }<br><br>    return maxLength<br>}<br><br>func max(a, b int) int {<br>    if a &gt; b {<br>        return a<br>    }<br><br>    return b<br>}</pre><h4>JavaScript solution</h4><pre>// Main function to return the length of<br>// the longest valid parentheses<br>var longestValidParentheses = function(s) {<br>    let left = 0, right = 0, maxLength = 0;<br>    let n = s.length;<br><br>    // iterate the string from left to right<br>    for(let i = 0; i &lt; n; i++) {<br>        if(s[i] == &#39;(&#39;) {<br>            left++;<br>        } else {<br>            right++;<br>        }<br><br>        // if left is equal to right, we found a<br>        // valid parentheses substring<br>        if(left == right) {<br>            maxLength = Math.max(maxLength, 2 * right);<br>        } else if (right &gt; left) {<br>            // reset the left and right counter when we have<br>            // invalid parentheses substring<br>            left = 0;<br>            right = 0;<br>        }<br>    }<br><br>    left = 0;<br>    right = 0;<br><br>    // iterate the string from right to left<br>    for(let i = n - 1; i &gt;= 0; i--) {<br>        if(s[i] == &#39;(&#39;) {<br>            left++;<br>        } else {<br>            right++;<br>        }<br><br>        // if left is equal to right, we found a<br>        // valid parentheses substring<br>        if(left == right) {<br>            maxLength = Math.max(maxLength, 2 * right);<br>        } else if (left &gt; right) {<br>            // reset the left and right counter when we have<br>            // invalid parentheses substring<br>            left = 0;<br>            right = 0;<br>        }<br>    }<br><br>    return maxLength;<br>};</pre><h4>Dry Run</h4><p>Let’s dry-run our algorithm to see how the solution works.</p><pre>Input: s = &#39;)()())&#39;<br><br>Step 1: set left = 0, right = 0, maxLength = 0<br>        n = s.size()<br>          = 6<br><br>Step 2: loop for i = 0; i &lt; n<br>          0 &lt; 6<br>          true<br><br>          if s[i] == &#39;(&#39;<br>             s[0] == &#39;(&#39;<br>             &#39;)&#39; == &#39;(&#39;<br>             false<br>          else<br>            right++<br>            right = 1<br><br>          if left == right<br>            0 == 1<br>            false<br>          else if right &gt; left<br>            1 &gt; 0<br>            true<br><br>            left = 0<br>            right = 0<br><br>          i++<br>          i = 1<br><br>Step 3: loop for i &lt; n<br>          1 &lt; 6<br>          true<br><br>          if s[i] == &#39;(&#39;<br>            s[1] == &#39;(&#39;<br>            &#39;(&#39; == &#39;(&#39;<br>            true<br>            left++<br>            left = 1<br><br>          if left == right<br>            1 == 0<br>            false<br>          else if right &gt; left<br>            0 &gt; 1<br>            false<br><br>          i++<br>          i = 2<br><br>Step 4: loop for i &lt; n<br>          2 &lt; 6<br>          true<br><br>          if s[i] == &#39;(&#39;<br>             s[2] == &#39;(&#39;<br>             &#39;)&#39; == &#39;(&#39;<br>             false<br>          else<br>            right++<br>            right = 1<br><br>          if left == right<br>            1 == 1<br>            true<br><br>            maxLength = max(maxLength, 2 * right)<br>                      = max(0, 2 * 1)<br>                      = max(0, 2)<br>                      = 2<br><br>          i++<br>          i = 3<br><br>Step 5: loop for i &lt; n<br>          3 &lt; 6<br>          true<br><br>          if s[i] == &#39;(&#39;<br>            s[3] == &#39;(&#39;<br>            &#39;(&#39; == &#39;(&#39;<br>            true<br>            left++<br>            left = 2<br><br>          if left == right<br>            2 == 1<br>            false<br>          else if right &gt; left<br>            1 &gt; 2<br>            false<br><br>          i++<br>          i = 4<br><br>Step 6: loop for i &lt; n<br>          4 &lt; 6<br>          true<br><br>          if s[i] == &#39;(&#39;<br>             s[4] == &#39;(&#39;<br>             &#39;)&#39; == &#39;(&#39;<br>             false<br>          else<br>            right++<br>            right = 2<br><br>          if left == right<br>            2 == 2<br>            true<br><br>            maxLength = max(maxLength, 2 * right)<br>                      = max(2, 2 * 2)<br>                      = max(2, 4)<br>                      = 4<br><br>          i++<br>          i = 5<br><br>Step 7: loop for i &lt; n<br>          5 &lt; 6<br>          true<br><br>          if s[i] == &#39;(&#39;<br>            s[5] == &#39;(&#39;<br>            &#39;)&#39; == &#39;(&#39;<br>            false<br>          else<br>            right++<br>            right = 3<br><br>          if left == right<br>            2 == 3<br>            false<br>          else<br>            left = 0<br>            right = 0<br><br>          i++<br>          i = 6<br><br>Step 8: loop for i &lt; n<br>          6 &lt; 6<br>          false<br><br>Step 9: left = 0<br>        right = 0<br><br>Step 10: loop for i = n - 1; i &gt;= 0<br>           i = 6 - 1 = 5<br>           i &gt;= 0<br>           5 &gt;= 0<br>           true<br><br>           if s[i] == &#39;(&#39;<br>             s[5] == &#39;(&#39;<br>             &#39;)&#39; == &#39;(&#39;<br>             false<br>           else<br>             right++<br>             right = 1<br><br>           if left == right<br>             0 == 1<br>             false<br>           else if left &gt; right<br>             0 &gt; 1<br>             false<br><br>           i--<br>           i = 4<br><br>Step 11: loop for i &gt;= 0<br>           4 &gt;= 0<br>           true<br><br>           if s[i] == &#39;(&#39;<br>             s[4] == &#39;(&#39;<br>             &#39;)&#39; == &#39;(&#39;<br>             false<br>           else<br>             right++<br>             right = 2<br><br>           if left == right<br>             0 == 2<br>             false<br>           else if left &gt; right<br>             0 &gt; 2<br>             false<br><br>           i--<br>           i = 3<br><br>Step 12: loop for i &gt;= 0<br>           3 &gt;= 0<br>           true<br><br>           if s[i] == &#39;(&#39;<br>             s[3] == &#39;(&#39;<br>             &#39;(&#39; == &#39;(&#39;<br>             true<br>             left++<br>             left = 1<br><br>           if left == right<br>             1 == 2<br>             false<br>           else if left &gt; right<br>             1 &gt; 2<br>             false<br><br>          i--<br>          i = 2<br><br>Step 13: loop for i &gt;= 0<br>           2 &gt;= 0<br>           true<br><br>           if s[i] == &#39;(&#39;<br>             s[2] == &#39;(&#39;<br>             &#39;)&#39; == &#39;(&#39;<br>             false<br>           else<br>             right++<br>             right = 3<br><br>           if left == right<br>             1 == 3<br>             false<br>           else if left &gt; right<br>             1 &gt; 3<br>             false<br><br>           i--<br>           i = 1<br><br>Step 14: loop for i &gt;= 0<br>           1 &gt;= 0<br>           true<br><br>           if s[i] == &#39;(&#39;<br>             s[1] == &#39;(&#39;<br>             &#39;(&#39; == &#39;(&#39;<br>             true<br>             left++<br>             left = 2<br><br>           if left == right<br>             2 == 3<br>             false<br>           else if left &gt; right<br>             2 &gt; 3<br>             false<br><br>           i--<br>           i = 0<br><br>Step 15: loop for i &gt;= 0<br>           0 &gt;= 0<br>           true<br><br>           if s[i] == &#39;(&#39;<br>             s[1] == &#39;(&#39;<br>             &#39;)&#39; == &#39;(&#39;<br>             false<br>           else<br>             right++<br>             right = 4<br><br>           if left == right<br>             2 == 4<br>             false<br>           else if left &gt; right<br>             2 &gt; 4<br>             false<br><br>           i--<br>           i = -1<br><br>Step 16: loop for i &gt;= 0<br>           -1 &gt;= 0<br>           false<br><br>Step 17: return maxLength<br><br>We return the answer as 4.</pre><p><em>Originally posted at </em><a href="https://alkeshghorpade.me/post/leetcoode-longest-valid-parentheses"><em>https://alkeshghorpade.me</em></a><em>.</em></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=e4d7918dc6ca" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Merge k Sorted Lists — LeetCode]]></title>
            <link>https://alkesh26.medium.com/merge-k-sorted-lists-leetcode-a82f75edb4f0?source=rss-5b66f0dd7bcd------2</link>
            <guid isPermaLink="false">https://medium.com/p/a82f75edb4f0</guid>
            <category><![CDATA[programming]]></category>
            <category><![CDATA[golang]]></category>
            <category><![CDATA[leetcode]]></category>
            <category><![CDATA[javascript]]></category>
            <category><![CDATA[algorithms]]></category>
            <dc:creator><![CDATA[Alkesh Ghorpade]]></dc:creator>
            <pubDate>Sun, 21 May 2023 12:29:05 GMT</pubDate>
            <atom:updated>2023-05-24T08:24:30.613Z</atom:updated>
            <content:encoded><![CDATA[<h3>Merge k Sorted Lists — LeetCode</h3><h4>Problem statement</h4><p>You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.</p><p><em>Merge all the linked-lists into one sorted linked-list and return it.</em></p><p>Problem statement taken from: <a href="https://leetcode.com/problems/merge-k-sorted-lists">https://leetcode.com/problems/merge-k-sorted-lists</a></p><p><strong>Example 1:</strong></p><pre>Input: lists = [[1, 4, 5], [1, 3, 4], [2, 6]]<br>Output: [1, 1, 2, 3, 4, 4, 5, 6]<br>Explanation: The linked-lists are:<br>[<br>  1-&gt;4-&gt;5,<br>  1-&gt;3-&gt;4,<br>  2-&gt;6<br>]<br>merging them into one sorted list:<br>1-&gt;1-&gt;2-&gt;3-&gt;4-&gt;4-&gt;5-&gt;6</pre><p><strong>Example 2:</strong></p><pre>Input: lists = []<br>Output: []</pre><p><strong>Example 3:</strong></p><pre>Input: lists = [[]]<br>Output: []</pre><p><strong>Constraints:</strong></p><pre>- k == lists.length<br>- 0 &lt;= k &lt;= 10^4<br>- 0 &lt;= lists[i].length &lt;= 500<br>- -10^4 &lt;= lists[i][j] &lt;= 10^4<br>- lists[i] is sorted in ascending order.<br>- The sum of lists[i].length will not exceed 10^4.</pre><h4>Solutions for Merge k Sorted Lists Problem</h4><h4>Approach 1: Brute Force</h4><p>In one of the previous blog posts, we discussed how to <a href="https://alkeshghorpade.me/post/leetcode-sort-list">Sort a single Linked List</a>. In this problem, we need to merge K sorted Linked list.</p><p>A simple solution would be to connect all k linked lists into one list (in any order). Then use the merge sort algorithm discussed in <a href="https://alkeshghorpade.me/post/leetcode-sort-list">Sort List</a> post. The worst-case time complexity of this approach is <strong>O(n * log(n))</strong>, where n is the total number of nodes present in all the k lists. This approach is inefficient as we are not taking advantage of the already sorted lists.</p><p>Let’s check the C++ snippet of this approach below:</p><pre>ListNode* getLastNode(ListNode* head) {<br>    ListNode* current = head;<br>    ListNode* next = current-&gt;next;<br><br>    while(next != NULL) {<br>        current = next;<br>        next = current-&gt;next;<br>    }<br><br>    return current;<br>}<br><br>// Merge k sorted lists: main function<br>ListNode* mergeKSortedLists(vector&lt;ListNode*&gt;&amp; lists) {<br>    if(lists.size() == 0) {<br>        return NULL;<br>    }<br><br>    // connect all k sorted linked lists into one list<br>    for(int i = 0; i &lt; lists.size() - 1; i++) {<br>        // fetch the last node<br>        ListNode* last = getLastNode(lists[i]);<br><br>        last-&gt;next = lists[i + 1];<br>    }<br><br>    // perform merge sort on list[0]<br>    return sortList(lists[0]);<br>}<br><br>// merge sort the two list<br>ListNode* mergelist(ListNode *l1, ListNode *l2) {<br>    ListNode *ptr = new ListNode(0);<br>    ListNode *current = ptr;<br><br>    while(l1 != NULL &amp;&amp; l2 != NULL) {<br>        if(l1-&gt;val &lt;= l2-&gt;val) {<br>            current-&gt;next = l1;<br>            l1 = l1-&gt;next;<br>        } else {<br>            current-&gt;next = l2;<br>            l2 = l2-&gt;next;<br>        }<br><br>        current = current-&gt;next;<br>    }<br><br>    if(l1 != NULL) {<br>        current-&gt;next = l1;<br>        l1 = l1-&gt;next;<br>    }<br><br>    if(l2 != NULL) {<br>        current-&gt;next = l2;<br>        l2 = l2-&gt;next;<br>    }<br><br>    return ptr-&gt;next;<br>}<br><br>ListNode* sortList(ListNode* head) {<br>    if(head == NULL || head-&gt;next == NULL)<br>        return head;<br><br>    ListNode *temp = NULL;<br>    ListNode *slow = head;<br>    ListNode *fast = head;<br><br>    // split the list into two halves<br>    while(fast != NULL &amp;&amp; fast-&gt;next != NULL) {<br>        temp = slow;<br>        slow = slow-&gt;next;<br>        fast = fast-&gt;next-&gt;next;<br>    }<br><br>    temp-&gt;next = NULL;<br><br>    // recursively call the sortList function for the two lists<br>    ListNode* l1 = sortList(head);<br>    ListNode* l2 = sortList(slow);<br><br>    // merge list l1 and l2<br>    return mergelist(l1, l2);<br>}</pre><p>A second brute-force approach to solve the problem is by <a href="https://alkeshghorpade.me/post/leetcode-merge-two-sorted-lists">merging two sorted lists</a> at a time. We merge the first two lists <strong>lists[0]</strong> with <strong>lists[1]</strong> and store the result. We merge the result with the third list <strong>lists[2]</strong> and repeat the process k — 1 time.</p><p>This method is relatively easy. But the time complexity of this approach is <strong>O(n * k)</strong>, where n is the number of elements to be merged.</p><p>A C++ snippet of this approach is as below:</p><pre>// Merge k sorted lists: main function<br>ListNode* mergeKSortedLists(vector&lt;ListNode*&gt;&amp; lists) {<br>    if(lists.size() == 0) {<br>        return NULL;<br>    }<br><br>    return mergeKSortedListsHelper(lists);<br>}<br><br>// Helper function to merge k sorted lists<br>ListNode* mergeKSortedListsHelper(vector&lt;ListNode*&gt;&amp; lists) {<br>    int size = lists.size();<br><br>    // Traverse from the second list to last<br>    for (int i = 1; i &lt;= size; i++) {<br>        while(true) {<br>            ListNode head1 = lists[0], head2 = lists[i];<br><br>            // if the list has ended<br>            if(head1 == NULL) {<br>                break;<br>            }<br><br>            if(head1-&gt;val &gt;= head2-&gt;val) {<br>                lists[i] = head2-&gt;next;<br>                head2-&gt;next = head1;<br>                lists[0] = head2;<br>            } else {<br>                // Traverse the first list<br>                while (head1-&gt;next != NULL) {<br>                    // find the node in the first list which is just<br>                    // greater than second list current node<br>                    if (head1-&gt;next-&gt;val &gt;= head2-&gt;val) {<br>                        lists[i] = head2-&gt;next;<br>                        head2-&gt;next = head1-&gt;next;<br>                        head1-&gt;next = head2;<br>                        break;<br>                    }<br><br>                    head1 = head1-&gt;next;<br>                }<br><br>                if(head1-&gt;next == NULL) {<br>                    lists[i] = head2-&gt;next;<br>                    head2-&gt;next = NULL;<br>                    head1-&gt;next = head2;<br>                    head1-&gt;next-&gt;next = NULL;<br>                    break;<br>                }<br>            }<br>        }<br>    }<br><br>    return lists[0];<br>}</pre><p>The time complexity of the above two approaches is very high, as we are not taking advantage of the sorted lists. We can optimize the approach using an additional data structure: Min Heap.</p><h4>Approach 2: Using Min Heap</h4><p>We can optimize the above approach by using a <a href="https://en.wikipedia.org/wiki/Min-max_heap">Min Heap</a>. The root of the Min Heap is always the smallest element.</p><p>As per the problem statement, all the linked lists are sorted. Therefore, the first element of the list will be the smallest. We add the first elements of all the linked lists into a Min Heap. We extract the smallest element, the Min Heap’s root. After the root is removed, we increment the pointer of the list to which the root element belonged. The next node of this list is added to the Min Heap. We continue removing the root, and keep adding the next node from the lists to the heap until all the lists are traversed, and the heap is empty.</p><p>This algorithm can also be used to merge K sorted arrays. The time complexity of the algorithm is <strong>O(n * log(k))</strong>. Where n is the number of elements across all the lists and k is the number of linked lists. The space complexity is <strong>O(k)</strong> where k is the size of the Min Heap.</p><p>Let’s check the algorithm for this approach.</p><pre>- priority_queue&lt;ListNode*, vector&lt;ListNode*&gt;, compare&gt; pq<br><br>- for int i = 0; i &lt; k; i++<br>  - if lists[i] != NULL<br>    - pq.push(arr[i])<br>  - if end<br>- for end<br><br>- if pq.empty()<br>  - return NULL<br>- if end<br><br>- ListNode* result = new ListNode(0)<br>  ListNode* last = dummp<br><br>- loop while !pq.empty()<br>  - ListNode* current = pq.top()<br>    pq.pop()<br><br>  - last-&gt;next = current<br>    last = last-&gt;next<br><br>  - if current-&gt;next != NULL<br>      pq.push(curr-&gt;next)<br>  - if end<br>- while end<br><br>- return result-&gt;next</pre><p>Let’s check the algorithm in C++ code.</p><pre>ListNode* mergeKSortedLists(vector&lt;ListNode*&gt;&amp; lists) {<br> priority_queue&lt;ListNode*, vector&lt;ListNode*&gt;, compare&gt; pq;<br>    int k = lists.size();<br><br> // Push the first nodes of all the k lists in priority_queue &#39;pq&#39;<br> for (int i = 0; i &lt; k; i++)<br>  if (lists[i] != NULL)<br>   pq.push(lists[i]);<br><br> if (pq.empty())<br>  return NULL;<br><br> ListNode *result = new ListNode(0);<br> ListNode *last = result;<br><br> // Loop till &#39;pq&#39; is not empty<br> while (!pq.empty()) {<br>  // Get the top element of &#39;pq&#39;<br>  ListNode* current = pq.top();<br>  pq.pop();<br><br>  // Add the top element of &#39;pq&#39; to the result list<br>  last-&gt;next = current;<br>  last = last-&gt;next;<br><br>  // If the current next node is not NULL, add it to the priority queue<br>  if (current-&gt;next != NULL) {<br>            pq.push(curr-&gt;next);<br>        }<br> }<br><br> // return the result<br> return result-&gt;next;<br>}</pre><h4>Approach 3: Using Divide and Conquer</h4><p>Using Min Heap, we reduced the time complexity to <strong>O(n * log(k))</strong>, but it takes <strong>O(k)</strong> extra space for the heap. We can solve this problem in constant space using Divide and Conquer technique.</p><p>As mentioned in our Brute force approach, we know how to <a href="https://alkeshghorpade.me/post/leetcode-merge-two-sorted-lists">merge two sorted lists</a>. The idea is to pair up k lists and merge each pair in linear time using the <strong>O(1)</strong> space. After the first iteration, k/2 lists of size 2 * n are left. After the second cycle, k/4 lists are left. We repeat the procedure until we have one list left.</p><p>Let’s check the algorithm first.</p><pre>// function mergeKLists(vector&lt;ListNode*&gt;&amp; lists)<br>- if lists.size() == 0<br>  - return NULL<br>- if end<br><br>- return mergeKListsHelper(lists, lists.size() - 1)<br><br>// function mergeKListsHelper(vector&lt;ListNode*&gt;&amp; lists, int last)<br>// Merge lists until one list is left<br>- loop while last != 0<br>  - initilaize i = 0, j = last<br><br>  - loop while i &lt; j<br>    // merge list i with list j<br>    // store the merged result in list i<br>    - lists[i] = mergeLists(lists[i], lists[j])<br><br>    - increment i = i++<br>    - decrement j = j--<br><br>    - if i &gt;= j<br>      - last = j<br>    - if end<br>  - while end<br>- while end<br><br>- return lists[0]<br><br>// function mergeLists(ListNode* l1, ListNode* l2)<br>- set ListNode* head = NULL<br><br>- if l1 == NULL<br>  - return l2<br>- else if l2 == NULL<br>  - return l1<br>- if end<br><br>- if l1-&gt;val &lt; l2-&gt;val<br>  - set head = l1<br>  - set l1 = l1-&gt;next<br>- else<br>  - set head = l2<br>  - set l2 = l2-&gt;next<br>- if end<br><br>- set ListNode* p = head<br><br>- loop while l1 &amp;&amp; l2<br>  - if l1-&gt;val &lt; l2-&gt;val<br>    - set p-&gt;next = l1<br>    - set l1 = l1-&gt;next<br>  - else<br>    - set p-&gt;next = l2<br>    - set l2 = l2-&gt;next<br>  - if end<br><br>  - set p = p-&gt;next<br>- while end<br><br>- if l1 != NULL<br>  - p-&gt;next = l1<br>- else<br>  - p-&gt;next = l2<br>- if end<br><br>- return head</pre><p>The time complexity of the above approach is <strong>O(n * log(k))</strong>, and the space complexity is <strong>O(1)</strong>.</p><p>Let’s check out our solutions in <strong>C++</strong>, <strong>Golang</strong>, and <strong>Javascript</strong>.</p><h4>C++ solution</h4><pre>class Solution {<br>public:<br>    ListNode* mergeKLists(vector&lt;ListNode*&gt;&amp; lists) {<br>        if(lists.size() == 0) {<br>            return NULL;<br>        }<br><br>        return mergeKListsHelper(lists, lists.size() - 1);<br>    }<br><br>    ListNode* mergeKListsHelper(vector&lt;ListNode*&gt;&amp; lists, int last) {<br>        // Merge lists until one list is left<br>        while(last != 0) {<br>            int i = 0, j = last;<br><br>            while(i &lt; j) {<br>                // merge list i with list j<br>                // store the merged result in list i<br>                lists[i] = mergeLists(lists[i], lists[j]);<br><br>                i++;<br>                j--;<br><br>                // update last when all pairs are merged<br>                if(i &gt;= j) {<br>                    last = j;<br>                }<br>            }<br>        }<br><br>        return lists[0];<br>    }<br><br>    ListNode* mergeLists(ListNode* l1, ListNode* l2) {<br>        ListNode* head = NULL;<br><br>        // if any one of the two lists is empty<br>        // return the other list.<br>        if(l1 == NULL) {<br>            return l2;<br>        } else if(l2 == NULL) {<br>            return l1;<br>        }<br><br>        // choose the head based on the smallest value of two lists.<br>        if(l1-&gt;val &lt; l2-&gt;val){<br>            head = l1;<br>            l1 = l1-&gt;next;<br>        } else {<br>            head = l2;<br>            l2 = l2-&gt;next;<br>        }<br><br>        ListNode *p;<br>        p = head;<br><br>        while(l1 &amp;&amp; l2){<br>            if(l1-&gt;val &lt; l2-&gt;val){<br>                p-&gt;next = l1;<br>                l1 = l1-&gt;next;<br>            } else {<br>                p-&gt;next = l2;<br>                l2 = l2-&gt;next;<br>            }<br><br>            p = p-&gt;next;<br>        }<br><br>        if(l1 != NULL){<br>            p-&gt;next = l1;<br>        } else {<br>            p-&gt;next = l2;<br>        }<br><br>        return head;<br>    }<br>};</pre><h4>Golang solution</h4><pre>func mergeKLists(lists []*ListNode) *ListNode {<br>    if len(lists) == 0 {<br>        return nil;<br>    }<br><br>    return mergeKListsHelper(lists, len(lists) - 1)<br>}<br><br>func mergeKListsHelper(lists []*ListNode, last int) *ListNode {<br>    // Merge lists until one list is left<br>    for last != 0 {<br>        i, j := 0, last<br><br>        for(i &lt; j) {<br>            // merge list i with list j<br>            // store the merged result in list i<br>            lists[i] = mergeLists(lists[i], lists[j])<br><br>            i++;<br>            j--;<br><br>            // update last when all pairs are merged<br>            if i &gt;= j {<br>                last = j<br>            }<br>        }<br>    }<br><br>    return lists[0]<br>}<br><br>func mergeLists(l1, l2 *ListNode) *ListNode {<br>    var head *ListNode<br>    head = nil<br><br>    // if any one of the two lists is empty<br>    // return the other list.<br>    if l1 == nil {<br>        return l2<br>    } else if l2 == nil {<br>        return l1<br>    }<br><br>    // choose the head based on the smallest value of the two lists.<br>    if(l1.Val &lt; l2.Val){<br>        head = l1;<br>        l1 = l1.Next;<br>    } else {<br>        head = l2;<br>        l2 = l2.Next;<br>    }<br><br>    p := head<br><br>    for l1 != nil &amp;&amp; l2 != nil {<br>        if l1.Val &lt; l2.Val {<br>            p.Next = l1<br>            l1 = l1.Next<br>        } else {<br>            p.Next = l2<br>            l2 = l2.Next<br>        }<br><br>        p = p.Next<br>    }<br><br>    if l1 != nil {<br>        p.Next = l1<br>    } else {<br>        p.Next = l2<br>    }<br><br>    return head<br>}</pre><h4>JavaScript solution</h4><pre>var mergeKLists = function(lists) {<br>    if(lists.length === 0) {<br>        return null;<br>    }<br><br>    return mergeKListsHelper(lists, lists.length - 1);<br>};<br><br>var mergeKListsHelper = function(lists, last) {<br>    // Merge lists until one list is left<br>    while(last != 0) {<br>        let i = 0, j = last;<br><br>        while(i &lt; j) {<br>            // merge list i with list j<br>            // store the merged result in list i<br>            lists[i] = mergeLists(lists[i], lists[j]);<br><br>            i++;<br>            j--;<br><br>            // update last when all pairs are merged<br>            if(i &gt;= j) {<br>                last = j;<br>            }<br>        }<br>    }<br><br>    return lists[0];<br>};<br><br>var mergeLists = function(l1, l2) {<br>    let head = null;<br><br>    // if any one of the two lists is empty<br>    // return the other list.<br>    if(l1 == null) {<br>        return l2;<br>    } else if(l2 == null) {<br>        return l1;<br>    }<br><br>    // choose the head based on the smallest value of the two lists.<br>    if(l1.val &lt; l2.val){<br>        head = l1;<br>        l1 = l1.next;<br>    } else {<br>        head = l2;<br>        l2 = l2.next;<br>    }<br><br>    let p = head;<br><br>    while(l1 &amp;&amp; l2){<br>        if(l1.val &lt; l2.val){<br>            p.next = l1;<br>            l1 = l1.next;<br>        } else {<br>            p.next = l2;<br>            l2 = l2.next;<br>        }<br><br>        p = p.next;<br>    }<br><br>    if(l1 != null){<br>        p.next = l1;<br>    } else {<br>        p.next = l2;<br>    }<br><br>    return head;<br>};</pre><p>Let’s dry-run our algorithm to see how the solution works.</p><pre>Input: lists = [[1, 4, 5], [1, 3, 4], [2, 6]]<br><br>// mergeKLists function<br>Step 1: if lists.size() == 0<br>          3 == 0<br>          false<br><br>Step 2: return mergeKListsHelper(lists, lists.size() - 1)<br>               mergeKListsHelper(lists, 2)<br><br>// mergeKListsHelper<br>Step 3: loop while last != 0<br>          2 != 0<br>          true<br><br>          i = 0<br>          j = last<br>            = 2<br><br>          loop while i &lt; j<br>            0 &lt; 2<br>            true<br><br>            lists[i] = mergeLists(lists[i], lists[j])<br>            lists[0] = mergeLists(lists[0], lists[2])<br>                     = mergeLists([1, 4, 5], [2, 6])<br><br>// mergeLists([1, 4, 5], [2, 6])<br>Step 4: This function will merge the list and return<br>        [1, 2, 4, 5, 6]<br><br>// mergeKListsHelper<br>Step 5: i++<br>        i = 1<br><br>        j--<br>        j = 1<br><br>        if i &gt;= j<br>           1 &gt;= 1<br>           true<br><br>           last = j<br>           last = 1<br><br>        loop while i &lt; j<br>          1 &lt; 1<br>          false<br><br>// mergeKListsHelper<br>Step 6: loop while last != 0<br>          1 != 0<br>          true<br><br>          i = 0<br>          j = last<br>            = 1<br><br>          loop while i &lt; j<br>            0 &lt; 1<br>            true<br><br>            lists[i] = mergeLists(lists[i], lists[j])<br>            lists[0] = mergeLists(lists[0], lists[1])<br>                     = mergeLists([1, 2, 4, 5, 6], [1, 3, 4])<br><br>// mergeLists([1, 2, 4, 5, 6], [1, 3, 4])<br>Step 7: This function will merge the list and return<br>        [1, 1, 2, 3, 4, 4, 5, 6]<br><br>// mergeKListsHelper<br>Step 8: i++<br>        i = 1<br><br>        j--<br>        j = 0<br><br>        if i &gt;= j<br>           1 &gt;= 0<br>           true<br><br>           last = j<br>           last = 0<br><br>        loop while i &lt; j<br>          1 &lt; 0<br>          false<br><br>Step 9: loop while last != 0<br>          0 != 0<br>          false<br><br>Step 10: return lists[0]<br>         [1, 1, 2, 3, 4, 4, 5, 6]</pre><p><em>Originally posted at </em><a href="https://alkeshghorpade.me/post/leetcode-merge-k-sorted-lists"><em>https://alkeshghorpade.me</em></a><em>.</em></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=a82f75edb4f0" width="1" height="1" alt="">]]></content:encoded>
        </item>
    </channel>
</rss>