tag:blogger.com,1999:blog-25760489970958650512024-03-13T13:11:10.987+05:30Let's Code_* SDE Career Contemplations
* DSA Practice
* Problem Solving in Java
* Tech in General
* Open Source guidance
* Career guidanceChandni Vermahttp://www.blogger.com/profile/16416503906800854146noreply@blogger.comBlogger123125tag:blogger.com,1999:blog-2576048997095865051.post-4246568439737551802022-09-01T21:16:00.009+05:302022-09-01T21:19:52.635+05:30interviewBit Medium: Palindrome Partitioning II<p><b>Problem Name: </b>Palindrome Partitioning II</p><p><b>Problem Description</b>: <a href="https://www.interviewbit.com/problems/palindrome-partitioning-ii/">https://www.interviewbit.com/problems/palindrome-partitioning-ii/</a></p><p><b>Problem Approach used</b>: This problem can be solved with MCM approach. You can note this when you feel the urge to partition the input String into parts (which are palindromes themselves in this case).<b> </b></p><p><b>Time Complexity</b>: <b>O(n^2)</b> worst-case time complexity and <b>O(n^2) auxiliary space</b> for memoisation.</p><div><b>Solution:</b></div><div><br /></div><div><table style="color: #333333; font-family: Verdana, Helvetica, Arial, sans-serif;"><tbody><tr><td><pre style="line-height: 16.25px; margin-bottom: 0px; margin-top: 0px;"> 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56</pre></td><td><pre style="line-height: 16.25px; margin-bottom: 0px; margin-top: 0px;"><span style="color: #008800; font-weight: bold;">public</span> <span style="color: #008800; font-weight: bold;">class</span> <span style="color: #bb0066; font-weight: bold;">Solution</span> {
<span style="color: #008800; font-weight: bold;">public</span> <span style="color: #333399; font-weight: bold;">int</span> <span style="color: #0066bb; font-weight: bold;">minCut</span>(String A) {
<span style="color: #333399; font-weight: bold;">int</span> memo[][] = <span style="color: #008800; font-weight: bold;">new</span> <span style="color: #333399; font-weight: bold;">int</span>[<span style="color: #0000dd; font-weight: bold;">502</span>][<span style="color: #0000dd; font-weight: bold;">502</span>];
<span style="color: #008800; font-weight: bold;">for</span> (<span style="color: #333399; font-weight: bold;">int</span> i=<span style="color: #0000dd; font-weight: bold;">0</span>; i<<span style="color: #0000dd; font-weight: bold;">502</span>; i++) {
Arrays.<span style="color: #0000cc;">fill</span> (memo[i], -<span style="color: #0000dd; font-weight: bold;">1</span>);
}
<span style="color: #888888;">// i=0, j=n-1 // to ensure 2 partitions</span>
<span style="color: #008800; font-weight: bold;">return</span> <span style="color: #0066bb; font-weight: bold;">palinPartition</span>(A, <span style="color: #0000dd; font-weight: bold;">0</span>, A.<span style="color: #0000cc;">length</span>()-<span style="color: #0000dd; font-weight: bold;">1</span>, memo);
}
<span style="color: #333399; font-weight: bold;">int</span> <span style="color: #0066bb; font-weight: bold;">palinPartition</span>(String A, <span style="color: #333399; font-weight: bold;">int</span> i, <span style="color: #333399; font-weight: bold;">int</span> j, <span style="color: #333399; font-weight: bold;">int</span> [][] memo) {
<span style="color: #008800; font-weight: bold;">if</span> (i >= j) {
<span style="color: #008800; font-weight: bold;">return</span> <span style="color: #0000dd; font-weight: bold;">0</span>;
}
<span style="color: #008800; font-weight: bold;">if</span> (isPalindrome(A, i, j)) {
<span style="color: #008800; font-weight: bold;">return</span> <span style="color: #0000dd; font-weight: bold;">0</span>;
}
<span style="color: #008800; font-weight: bold;">if</span> (memo[i][j] != -<span style="color: #0000dd; font-weight: bold;">1</span>) {
<span style="color: #008800; font-weight: bold;">return</span> memo[i][j];
}
<span style="color: #333399; font-weight: bold;">int</span> mn = Integer.<span style="color: #0000cc;">MAX_VALUE</span>;
<span style="color: #888888;">// k= i -> j-1</span>
<span style="color: #008800; font-weight: bold;">for</span> (<span style="color: #333399; font-weight: bold;">int</span> k=i; k<j; k++) {
<span style="color: #333399; font-weight: bold;">int</span> c1 = palinPartition(A, i, k, memo);
<span style="color: #333399; font-weight: bold;">int</span> c2 = palinPartition(A, k+<span style="color: #0000dd; font-weight: bold;">1</span>, j, memo);
<span style="color: #333399; font-weight: bold;">int</span> temp = c1+c2+<span style="color: #0000dd; font-weight: bold;">1</span>;
mn = Math.<span style="color: #0000cc;">min</span> (mn, temp);
}
<span style="color: #008800; font-weight: bold;">return</span> memo[i][j] = mn;
}
<span style="color: #333399; font-weight: bold;">boolean</span> <span style="color: #0066bb; font-weight: bold;">isPalindrome</span>(String s, <span style="color: #333399; font-weight: bold;">int</span> i, <span style="color: #333399; font-weight: bold;">int</span> j) {
<span style="color: #008800; font-weight: bold;">if</span> (i >= j)
<span style="color: #008800; font-weight: bold;">return</span> <span style="color: #008800; font-weight: bold;">true</span>;
<span style="color: #008800; font-weight: bold;">while</span> (i<j) {
<span style="color: #008800; font-weight: bold;">if</span> (s.<span style="color: #0000cc;">charAt</span>(i) != s.<span style="color: #0000cc;">charAt</span>(j)) {
<span style="color: #008800; font-weight: bold;">return</span> <span style="color: #008800; font-weight: bold;">false</span>;
} <span style="color: #008800; font-weight: bold;">else</span> {
i++;
j--;
}
}
<span style="color: #008800; font-weight: bold;">return</span> <span style="color: #008800; font-weight: bold;">true</span>;
}
}</pre></td></tr></tbody></table></div><div><br /></div><div><br /></div><div><p>Until Next time, Keep coding and have fun!<br /><br /></p><p><br />Love! ❤️ <br />#Lets #Code<br /><br />Follow us on :<br /></p><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhfUYmRhkX_i4K0oX-yu0o2lSuknyicVjl4o4l2JjYvzxva1TTtNY_tOnKheAfM3pccf9EwloOQ2se0r75P_5yFWskZ47qK5Tu1s7FkmghH2Lux8u1ARz-WLPdSIQ5QNpdWTxh76BNiCNg/s20/TwitterTransparentBG-icon.png" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="17" data-original-width="20" height="17" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhfUYmRhkX_i4K0oX-yu0o2lSuknyicVjl4o4l2JjYvzxva1TTtNY_tOnKheAfM3pccf9EwloOQ2se0r75P_5yFWskZ47qK5Tu1s7FkmghH2Lux8u1ARz-WLPdSIQ5QNpdWTxh76BNiCNg/s0/TwitterTransparentBG-icon.png" width="20" /></a></div><p><a href="https://twitter.com/ThinkAlgorithms">https://twitter.com/ThinkAlgorithms</a></p><div><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhQrO6XtJFalqwzQpLck9X5UaC8fWeHBe2lFtjkrygS8By9k5K2EJlK5Gl3MbZyrg3NvHwKzxEdxeCyQ5RyHWDpa0WXyoCm-nCFXuSPgOCyREA1xGcraDJsN3EDFr12a7VaIZUhIqqcs4k/s21/FBimageTransparentBG-Icon.png" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="21" data-original-width="20" height="21" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhQrO6XtJFalqwzQpLck9X5UaC8fWeHBe2lFtjkrygS8By9k5K2EJlK5Gl3MbZyrg3NvHwKzxEdxeCyQ5RyHWDpa0WXyoCm-nCFXuSPgOCyREA1xGcraDJsN3EDFr12a7VaIZUhIqqcs4k/s0/FBimageTransparentBG-Icon.png" width="20" /></a></div><a href="https://www.facebook.com/theAlgorithmicCoder">https://www.facebook.com/theAlgorithmicCoder</a></div></div><div><br /></div><p><br /></p><p><br /></p><p><br /></p>Chandni Vermahttp://www.blogger.com/profile/16416503906800854146noreply@blogger.com0tag:blogger.com,1999:blog-2576048997095865051.post-28004804611772550422022-07-19T15:49:00.002+05:302022-07-19T15:51:06.110+05:30Leetcode Medium: Container with most water<p><b>Problem Name: </b>Container with most water</p><p><b>Problem Description</b>: <a href="https://leetcode.com/problems/container-with-most-water">https://leetcode.com/problems/container-with-most-water</a></p><p><b>Problem Approach used</b>: This problem can be solved with multiple approaches. The naive solution calculates the water content in all possible containers, compares and returns the maximum water that can be contained. It is <b>O(n^2) time solution with O(1) auxiliary space.</b></p><p>Other "smarter" solution takes <b>O(n) time with O(1) space. </b>It makes use of the <b>2-pointer technique. </b></p><p><b>Time Complexity</b>: <b>O(n)</b> worst-case time complexity and <b>O(1) auxiliary space</b> complexity.</p><p><b>Solution 1:</b></p><table style="color: #333333; font-family: Verdana, Helvetica, Arial, sans-serif;"><tbody><tr><td><pre style="line-height: 16.25px; margin-bottom: 0px; margin-top: 0px;"></pre></td><td><pre style="line-height: 16.25px; margin-bottom: 0px; margin-top: 0px;"><span style="color: #008800; font-weight: bold;">class</span> <span style="color: #bb0066; font-weight: bold;">Solution</span> {
<span style="color: #008800; font-weight: bold;">public</span> <span style="color: #333399; font-weight: bold;">int</span> <span style="color: #0066bb; font-weight: bold;">maxArea</span>(<span style="color: #333399; font-weight: bold;">int</span>[] height) {
<span style="color: #333399; font-weight: bold;">int</span> maxArea = Integer.<span style="color: #0000cc;">MIN_VALUE</span>;
<span style="color: #008800; font-weight: bold;">for</span> (<span style="color: #333399; font-weight: bold;">int</span> i=<span style="color: #0000dd; font-weight: bold;">0</span>; i<height.<span style="color: #0000cc;">length</span>; i++) {
<span style="color: #008800; font-weight: bold;">for</span> (<span style="color: #333399; font-weight: bold;">int</span> j=i+<span style="color: #0000dd; font-weight: bold;">1</span>; j<height.<span style="color: #0000cc;">length</span>; j++) {
<span style="color: #333399; font-weight: bold;">int</span> lesserHeight = Math.<span style="color: #0000cc;">min</span>(height[i], height[j]);
maxArea = Math.<span style="color: #0000cc;">max</span> (maxArea, lesserHeight*(j-i));
}
}
<span style="color: #008800; font-weight: bold;">return</span> maxArea;
}
}</pre></td></tr></tbody></table><p><b><br /></b></p><p><b>Solution 2:<br /><br /></b></p><table style="color: #333333; font-family: Verdana, Helvetica, Arial, sans-serif;"><tbody><tr><td><pre style="line-height: 16.25px; margin-bottom: 0px; margin-top: 0px;"></pre></td><td><pre style="line-height: 16.25px; margin-bottom: 0px; margin-top: 0px;"><span style="color: #008800; font-weight: bold;">class</span> <span style="color: #bb0066; font-weight: bold;">Solution</span> {
<span style="color: #008800; font-weight: bold;">public</span> <span style="color: #333399; font-weight: bold;">int</span> <span style="color: #0066bb; font-weight: bold;">maxArea</span>(<span style="color: #333399; font-weight: bold;">int</span>[] height) {
<span style="color: #888888;">// 2 pointer technique</span>
<span style="color: #333399; font-weight: bold;">int</span> smallerIndex=<span style="color: #0000dd; font-weight: bold;">0</span>, greaterIndex=height.<span style="color: #0000cc;">length</span>-<span style="color: #0000dd; font-weight: bold;">1</span>;
<span style="color: #333399; font-weight: bold;">int</span> maxAreaSoFar = <span style="color: #0000dd; font-weight: bold;">0</span>;
<span style="color: #008800; font-weight: bold;">while</span> (smallerIndex < greaterIndex) {
<span style="color: #008800; font-weight: bold;">if</span> (height[smallerIndex] >= height[greaterIndex]) {
maxAreaSoFar = Math.<span style="color: #0000cc;">max</span>(maxAreaSoFar,
height[greaterIndex] * (greaterIndex - smallerIndex));
greaterIndex-- ;
} <span style="color: #008800; font-weight: bold;">else</span> <span style="color: #008800; font-weight: bold;">if</span> (height[smallerIndex] < height[greaterIndex]) {
maxAreaSoFar = Math.<span style="color: #0000cc;">max</span>(maxAreaSoFar,
height[smallerIndex] * (greaterIndex - smallerIndex));
smallerIndex++;
} <span style="color: #008800; font-weight: bold;">else</span> {
;
}
}
<span style="color: #008800; font-weight: bold;">return</span> maxAreaSoFar;
}
}</pre></td></tr></tbody></table><p><br />Until Next time, Keep coding and have fun!<br /><br /></p><p><br />Love! ❤️ <br />#Lets #Code<br /><br />Follow us on :<br /></p><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhfUYmRhkX_i4K0oX-yu0o2lSuknyicVjl4o4l2JjYvzxva1TTtNY_tOnKheAfM3pccf9EwloOQ2se0r75P_5yFWskZ47qK5Tu1s7FkmghH2Lux8u1ARz-WLPdSIQ5QNpdWTxh76BNiCNg/s20/TwitterTransparentBG-icon.png" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="17" data-original-width="20" height="17" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhfUYmRhkX_i4K0oX-yu0o2lSuknyicVjl4o4l2JjYvzxva1TTtNY_tOnKheAfM3pccf9EwloOQ2se0r75P_5yFWskZ47qK5Tu1s7FkmghH2Lux8u1ARz-WLPdSIQ5QNpdWTxh76BNiCNg/s0/TwitterTransparentBG-icon.png" width="20" /></a></div><p><a href="https://twitter.com/ThinkAlgorithms">https://twitter.com/ThinkAlgorithms</a></p><div><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhQrO6XtJFalqwzQpLck9X5UaC8fWeHBe2lFtjkrygS8By9k5K2EJlK5Gl3MbZyrg3NvHwKzxEdxeCyQ5RyHWDpa0WXyoCm-nCFXuSPgOCyREA1xGcraDJsN3EDFr12a7VaIZUhIqqcs4k/s21/FBimageTransparentBG-Icon.png" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="21" data-original-width="20" height="21" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhQrO6XtJFalqwzQpLck9X5UaC8fWeHBe2lFtjkrygS8By9k5K2EJlK5Gl3MbZyrg3NvHwKzxEdxeCyQ5RyHWDpa0WXyoCm-nCFXuSPgOCyREA1xGcraDJsN3EDFr12a7VaIZUhIqqcs4k/s0/FBimageTransparentBG-Icon.png" width="20" /></a></div><a href="https://www.facebook.com/theAlgorithmicCoder">https://www.facebook.com/theAlgorithmicCoder</a></div>Chandni Vermahttp://www.blogger.com/profile/16416503906800854146noreply@blogger.com0tag:blogger.com,1999:blog-2576048997095865051.post-5396303896048008202022-07-18T19:20:00.002+05:302022-07-18T19:21:33.360+05:30Leetcode Hard: Trapping Rain Water<p> </p><p><b>Problem Name: </b>Trapping Rain Water</p><p><b>Problem Description</b>: <a href="https://leetcode.com/problems/product-of-array-except-self/">https://leetcode.com/problems/trapping-rain-water/</a></p><p><b>Problem Approach used</b>: Calculate the amount of water this index would store with the knowledge of highest left and highest right tower. Then subtract the hight of the current tower as that's just conctrete, water can't seep into.</p><p><b>Time Complexity</b>: <b>O(n)</b> worst-case <b>time and space</b> complexity.</p><p><b>Solution:</b></p><table style="color: #333333; font-family: Verdana, Helvetica, Arial, sans-serif;"><tbody><tr><td><pre style="line-height: 16.25px; margin-bottom: 0px; margin-top: 0px;"> 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28</pre></td><td><pre style="line-height: 16.25px; margin-bottom: 0px; margin-top: 0px;"><span style="color: #008800; font-weight: bold;">class</span> <span style="color: #bb0066; font-weight: bold;">Solution</span> {
<span style="color: #008800; font-weight: bold;">public</span> <span style="color: #333399; font-weight: bold;">int</span> <span style="color: #0066bb; font-weight: bold;">trap</span>(<span style="color: #333399; font-weight: bold;">int</span>[] height) {
<span style="color: #333399; font-weight: bold;">int</span> n = height.<span style="color: #0000cc;">length</span>;
<span style="color: #333399; font-weight: bold;">int</span>[] leftMax = <span style="color: #008800; font-weight: bold;">new</span> <span style="color: #333399; font-weight: bold;">int</span>[n];
<span style="color: #333399; font-weight: bold;">int</span>[] rightMax = <span style="color: #008800; font-weight: bold;">new</span> <span style="color: #333399; font-weight: bold;">int</span>[n];
<span style="color: #333399; font-weight: bold;">int</span> maxHt = <span style="color: #0000dd; font-weight: bold;">0</span>;
<span style="color: #008800; font-weight: bold;">for</span> (<span style="color: #333399; font-weight: bold;">int</span> i=<span style="color: #0000dd; font-weight: bold;">0</span>; i<n; i++) {
maxHt = Math.<span style="color: #0000cc;">max</span> (maxHt, height[i]);
leftMax[i] = maxHt;
}
maxHt = <span style="color: #0000dd; font-weight: bold;">0</span>;
<span style="color: #008800; font-weight: bold;">for</span> (<span style="color: #333399; font-weight: bold;">int</span> i=n-<span style="color: #0000dd; font-weight: bold;">1</span>; i>=<span style="color: #0000dd; font-weight: bold;">0</span>; i--) {
maxHt = Math.<span style="color: #0000cc;">max</span> (maxHt, height[i]);
rightMax[i] = maxHt;
}
<span style="color: #333399; font-weight: bold;">int</span> totalWater = <span style="color: #0000dd; font-weight: bold;">0</span>;
<span style="color: #333399; font-weight: bold;">int</span> water = <span style="color: #0000dd; font-weight: bold;">0</span>;
<span style="color: #008800; font-weight: bold;">for</span> (<span style="color: #333399; font-weight: bold;">int</span> i=<span style="color: #0000dd; font-weight: bold;">0</span>; i<n; i++) {
water = Math.<span style="color: #0000cc;">min</span>(leftMax[i], rightMax[i]) - height[i];
totalWater += water;
}
<span style="color: #008800; font-weight: bold;">return</span> totalWater;
}
}</pre></td></tr></tbody></table><p><br /></p><p>Keep coding and have fun!<br /><br /></p><p><br />Love! ❤️ <br />#Lets #Code<br /><br />Follow us on :<br /></p><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhfUYmRhkX_i4K0oX-yu0o2lSuknyicVjl4o4l2JjYvzxva1TTtNY_tOnKheAfM3pccf9EwloOQ2se0r75P_5yFWskZ47qK5Tu1s7FkmghH2Lux8u1ARz-WLPdSIQ5QNpdWTxh76BNiCNg/s20/TwitterTransparentBG-icon.png" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="17" data-original-width="20" height="17" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhfUYmRhkX_i4K0oX-yu0o2lSuknyicVjl4o4l2JjYvzxva1TTtNY_tOnKheAfM3pccf9EwloOQ2se0r75P_5yFWskZ47qK5Tu1s7FkmghH2Lux8u1ARz-WLPdSIQ5QNpdWTxh76BNiCNg/s0/TwitterTransparentBG-icon.png" width="20" /></a></div><p><a href="https://twitter.com/ThinkAlgorithms">https://twitter.com/ThinkAlgorithms</a></p><div><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhQrO6XtJFalqwzQpLck9X5UaC8fWeHBe2lFtjkrygS8By9k5K2EJlK5Gl3MbZyrg3NvHwKzxEdxeCyQ5RyHWDpa0WXyoCm-nCFXuSPgOCyREA1xGcraDJsN3EDFr12a7VaIZUhIqqcs4k/s21/FBimageTransparentBG-Icon.png" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="21" data-original-width="20" height="21" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhQrO6XtJFalqwzQpLck9X5UaC8fWeHBe2lFtjkrygS8By9k5K2EJlK5Gl3MbZyrg3NvHwKzxEdxeCyQ5RyHWDpa0WXyoCm-nCFXuSPgOCyREA1xGcraDJsN3EDFr12a7VaIZUhIqqcs4k/s0/FBimageTransparentBG-Icon.png" width="20" /></a></div><a href="https://www.facebook.com/theAlgorithmicCoder">https://www.facebook.com/theAlgorithmicCoder</a></div><p><br /></p><p><br /></p>Chandni Vermahttp://www.blogger.com/profile/16416503906800854146noreply@blogger.com0tag:blogger.com,1999:blog-2576048997095865051.post-71836198135799001552022-05-07T20:10:00.003+05:302022-07-18T19:05:16.012+05:30LeetCode Medium: Product of Array Except Self<p> <b>Problem Name: </b>Product of Array Except Self</p><p><b>Problem Description</b>: <a href="https://leetcode.com/problems/product-of-array-except-self/">https://leetcode.com/problems/product-of-array-except-self/</a></p><p><b>Problem Approach used</b>: It's an easy problem to solve, just keep in mind your Indeterminate Numbers lesson of High School to solve it.</p><p><b>Time Complexity</b>: <b>O(n)</b> worst-case time complexity and <b>O(1) auxiliary space</b> complexity.</p><p><b>Solution:</b></p><table style="color: #333333; font-family: Verdana, Helvetica, Arial, sans-serif;"><tbody><tr><td><pre style="line-height: 16.25px; margin-bottom: 0px; margin-top: 0px;"> 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30</pre></td><td><pre style="line-height: 16.25px; margin-bottom: 0px; margin-top: 0px;"><span style="color: #008800; font-weight: bold;">class</span> <span style="color: #bb0066; font-weight: bold;">Solution</span> {
<span style="color: #008800; font-weight: bold;">public</span> <span style="color: #333399; font-weight: bold;">int</span>[] <span style="color: #0066bb; font-weight: bold;">productExceptSelf</span>(<span style="color: #333399; font-weight: bold;">int</span>[] nums) {
<span style="color: #333399; font-weight: bold;">long</span> prodArr = <span style="color: #0000dd; font-weight: bold;">1</span>;
<span style="color: #333399; font-weight: bold;">long</span> non0ProdArr = <span style="color: #0000dd; font-weight: bold;">1</span>;
<span style="color: #333399; font-weight: bold;">int</span> countZeroes = <span style="color: #0000dd; font-weight: bold;">0</span>;
<span style="color: #008800; font-weight: bold;">for</span> (<span style="color: #333399; font-weight: bold;">int</span> i=<span style="color: #0000dd; font-weight: bold;">0</span>; i<nums.<span style="color: #0000cc;">length</span>; i++) {
<span style="color: #008800; font-weight: bold;">if</span> (nums[i] == <span style="color: #0000dd; font-weight: bold;">0</span>)
countZeroes++;
<span style="color: #008800; font-weight: bold;">if</span> (nums[i] != <span style="color: #0000dd; font-weight: bold;">0</span>)
non0ProdArr *= nums[i];
prodArr *= nums[i];
}
<span style="color: #333399; font-weight: bold;">int</span>[] answer = <span style="color: #008800; font-weight: bold;">new</span> <span style="color: #333399; font-weight: bold;">int</span>[nums.<span style="color: #0000cc;">length</span>];
<span style="color: #008800; font-weight: bold;">if</span> (countZeroes > <span style="color: #0000dd; font-weight: bold;">1</span>) {
Arrays.<span style="color: #0000cc;">fill</span>(answer, <span style="color: #0000dd; font-weight: bold;">0</span>);
<span style="color: #008800; font-weight: bold;">return</span> answer;
}
<span style="color: #008800; font-weight: bold;">for</span> (<span style="color: #333399; font-weight: bold;">int</span> i=<span style="color: #0000dd; font-weight: bold;">0</span>; i<nums.<span style="color: #0000cc;">length</span>; i++) {
<span style="color: #008800; font-weight: bold;">if</span> (nums[i] == <span style="color: #0000dd; font-weight: bold;">0</span> && countZeroes == <span style="color: #0000dd; font-weight: bold;">1</span>) {
countZeroes--;
answer[i] = (<span style="color: #333399; font-weight: bold;">int</span>)non0ProdArr;
} <span style="color: #008800; font-weight: bold;">else</span> {
answer[i] = (<span style="color: #333399; font-weight: bold;">int</span>)(prodArr / (<span style="color: #333399; font-weight: bold;">long</span>)nums[i]);
}
}
<span style="color: #008800; font-weight: bold;">return</span> answer;
}
}</pre></td></tr></tbody></table><p><b><br /></b></p><p>Until Next time, Keep coding and have fun!<br /><br /></p><p><br />Love! ❤️ <br />#Lets #Code<br /><br />Follow us on :<br /></p><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhfUYmRhkX_i4K0oX-yu0o2lSuknyicVjl4o4l2JjYvzxva1TTtNY_tOnKheAfM3pccf9EwloOQ2se0r75P_5yFWskZ47qK5Tu1s7FkmghH2Lux8u1ARz-WLPdSIQ5QNpdWTxh76BNiCNg/s20/TwitterTransparentBG-icon.png" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="17" data-original-width="20" height="17" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhfUYmRhkX_i4K0oX-yu0o2lSuknyicVjl4o4l2JjYvzxva1TTtNY_tOnKheAfM3pccf9EwloOQ2se0r75P_5yFWskZ47qK5Tu1s7FkmghH2Lux8u1ARz-WLPdSIQ5QNpdWTxh76BNiCNg/s0/TwitterTransparentBG-icon.png" width="20" /></a></div><p><a href="https://twitter.com/ThinkAlgorithms">https://twitter.com/ThinkAlgorithms</a></p><div><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhQrO6XtJFalqwzQpLck9X5UaC8fWeHBe2lFtjkrygS8By9k5K2EJlK5Gl3MbZyrg3NvHwKzxEdxeCyQ5RyHWDpa0WXyoCm-nCFXuSPgOCyREA1xGcraDJsN3EDFr12a7VaIZUhIqqcs4k/s21/FBimageTransparentBG-Icon.png" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="21" data-original-width="20" height="21" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhQrO6XtJFalqwzQpLck9X5UaC8fWeHBe2lFtjkrygS8By9k5K2EJlK5Gl3MbZyrg3NvHwKzxEdxeCyQ5RyHWDpa0WXyoCm-nCFXuSPgOCyREA1xGcraDJsN3EDFr12a7VaIZUhIqqcs4k/s0/FBimageTransparentBG-Icon.png" width="20" /></a></div><a href="https://www.facebook.com/theAlgorithmicCoder">https://www.facebook.com/theAlgorithmicCoder</a></div><div><br /></div>Chandni Vermahttp://www.blogger.com/profile/16416503906800854146noreply@blogger.com0tag:blogger.com,1999:blog-2576048997095865051.post-44551132817482497232022-04-05T16:58:00.001+05:302022-04-05T17:10:16.725+05:30Leetcode Medium: Set Matrix Zeroes<p> <b>Problem Name: </b>Set Matrix Zeroes</p><p><b>Problem Description</b>: <a href="https://leetcode.com/problems/course-schedule/">https://leetcode.com/problems/set-matrix-zeroes/</a></p><p><b>Problem Approach used</b>: Its a trick problem to solve it in constant space. We've used the same, using HashSets in the below solution.</p><p><b>Time Complexity</b>: <b>O(m*n)</b> worst-case time complexity and <b>O(1) auxiliary space</b> complexity.</p><p><b>Solution:</b></p><table style="color: #333333; font-family: Verdana, Helvetica, Arial, sans-serif;"><tbody><tr><td><pre style="line-height: 16.25px; margin-bottom: 0px; margin-top: 0px;"> 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48</pre></td><td><pre style="line-height: 16.25px; margin-bottom: 0px; margin-top: 0px;"><span style="color: #888888;">// In 1 line of thought, constant space solution is ideally not possible as all possible int values can be part of the matrix, but if we can assume some sentinel value out of these (like Integer.MIN_VALUE in our case) for marking original zeroes, a solution follows.</span>
<span style="color: #888888;">// * Also we can use a trick to solve ths problem: marking 1st(top and left) elements of the row and column respetively, to 0.</span>
<span style="color: #008800; font-weight: bold;">class</span> <span style="color: #bb0066; font-weight: bold;">Solution</span> {
Set<Integer> toZeroRows = <span style="color: #008800; font-weight: bold;">new</span> HashSet<>(), toZeroColumns = <span style="color: #008800; font-weight: bold;">new</span> HashSet<>();
<span style="color: #008800; font-weight: bold;">public</span> <span style="color: #333399; font-weight: bold;">void</span> <span style="color: #0066bb; font-weight: bold;">setZeroes</span>(<span style="color: #333399; font-weight: bold;">int</span>[][] matrix) {
<span style="color: #008800; font-weight: bold;">for</span> (<span style="color: #333399; font-weight: bold;">int</span> row=<span style="color: #0000dd; font-weight: bold;">0</span>; row<matrix.<span style="color: #0000cc;">length</span>; row++) {
<span style="color: #008800; font-weight: bold;">for</span> (<span style="color: #333399; font-weight: bold;">int</span> column=<span style="color: #0000dd; font-weight: bold;">0</span>; column<matrix[<span style="color: #0000dd; font-weight: bold;">0</span>].<span style="color: #0000cc;">length</span>; column++) {
<span style="color: #008800; font-weight: bold;">if</span> (matrix[row][column] == <span style="color: #0000dd; font-weight: bold;">0</span>) {
toZeroRows.<span style="color: #0000cc;">add</span>(row);
toZeroColumns.<span style="color: #0000cc;">add</span>(column);
}
}
}
<span style="color: #888888;">// Print initial matrix</span>
printMatrix(matrix);
<span style="color: #008800; font-weight: bold;">for</span> (<span style="color: #333399; font-weight: bold;">int</span> row=<span style="color: #0000dd; font-weight: bold;">0</span>; row<matrix.<span style="color: #0000cc;">length</span>; row++) {
<span style="color: #008800; font-weight: bold;">if</span> (toZeroRows.<span style="color: #0000cc;">contains</span>(row)) {
<span style="color: #008800; font-weight: bold;">for</span>(<span style="color: #333399; font-weight: bold;">int</span> columnIndex=<span style="color: #0000dd; font-weight: bold;">0</span>; columnIndex<matrix[<span style="color: #0000dd; font-weight: bold;">0</span>].<span style="color: #0000cc;">length</span>; columnIndex++) {
matrix[row][columnIndex] = <span style="color: #0000dd; font-weight: bold;">0</span>;
}
}
}
printMatrix(matrix);
<span style="color: #008800; font-weight: bold;">for</span> (<span style="color: #333399; font-weight: bold;">int</span> column=<span style="color: #0000dd; font-weight: bold;">0</span>; column<matrix[<span style="color: #0000dd; font-weight: bold;">0</span>].<span style="color: #0000cc;">length</span>; column++) {
<span style="color: #008800; font-weight: bold;">if</span> (toZeroColumns.<span style="color: #0000cc;">contains</span>(column))
<span style="color: #008800; font-weight: bold;">for</span>(<span style="color: #333399; font-weight: bold;">int</span> rowIndex=<span style="color: #0000dd; font-weight: bold;">0</span>; rowIndex<matrix.<span style="color: #0000cc;">length</span>; rowIndex++) {
matrix[rowIndex][column] = <span style="color: #0000dd; font-weight: bold;">0</span>;
}
}
printMatrix(matrix);
}
<span style="color: #008800; font-weight: bold;">public</span> <span style="color: #333399; font-weight: bold;">void</span> <span style="color: #0066bb; font-weight: bold;">printMatrix</span>(<span style="color: #333399; font-weight: bold;">int</span> [][] matrix) {
<span style="color: #008800; font-weight: bold;">for</span> (<span style="color: #333399; font-weight: bold;">int</span> row = <span style="color: #0000dd; font-weight: bold;">0</span>; row<matrix.<span style="color: #0000cc;">length</span>; row++) {
<span style="color: #008800; font-weight: bold;">for</span> (<span style="color: #333399; font-weight: bold;">int</span> column = <span style="color: #0000dd; font-weight: bold;">0</span>; column<matrix[<span style="color: #0000dd; font-weight: bold;">0</span>].<span style="color: #0000cc;">length</span>; column++) {
System.<span style="color: #0000cc;">out</span>.<span style="color: #0000cc;">print</span>(<span style="background-color: #fff0f0;">" "</span> + matrix[row][column]);
}
System.<span style="color: #0000cc;">out</span>.<span style="color: #0000cc;">println</span>();
}
}
}</pre></td></tr></tbody></table><p><br /></p><p>Happy Coding!</p><p><br />Love! ❤️ <br />#Lets #Code<br /><br />Follow us on :<br /></p><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhfUYmRhkX_i4K0oX-yu0o2lSuknyicVjl4o4l2JjYvzxva1TTtNY_tOnKheAfM3pccf9EwloOQ2se0r75P_5yFWskZ47qK5Tu1s7FkmghH2Lux8u1ARz-WLPdSIQ5QNpdWTxh76BNiCNg/s20/TwitterTransparentBG-icon.png" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="17" data-original-width="20" height="17" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhfUYmRhkX_i4K0oX-yu0o2lSuknyicVjl4o4l2JjYvzxva1TTtNY_tOnKheAfM3pccf9EwloOQ2se0r75P_5yFWskZ47qK5Tu1s7FkmghH2Lux8u1ARz-WLPdSIQ5QNpdWTxh76BNiCNg/s0/TwitterTransparentBG-icon.png" width="20" /></a></div><p><a href="https://twitter.com/ThinkAlgorithms">https://twitter.com/ThinkAlgorithms</a></p><div><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhQrO6XtJFalqwzQpLck9X5UaC8fWeHBe2lFtjkrygS8By9k5K2EJlK5Gl3MbZyrg3NvHwKzxEdxeCyQ5RyHWDpa0WXyoCm-nCFXuSPgOCyREA1xGcraDJsN3EDFr12a7VaIZUhIqqcs4k/s21/FBimageTransparentBG-Icon.png" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="21" data-original-width="20" height="21" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhQrO6XtJFalqwzQpLck9X5UaC8fWeHBe2lFtjkrygS8By9k5K2EJlK5Gl3MbZyrg3NvHwKzxEdxeCyQ5RyHWDpa0WXyoCm-nCFXuSPgOCyREA1xGcraDJsN3EDFr12a7VaIZUhIqqcs4k/s0/FBimageTransparentBG-Icon.png" width="20" /></a></div><a href="https://www.facebook.com/theAlgorithmicCoder">https://www.facebook.com/theAlgorithmicCoder</a><br /><div class="separator" style="clear: both; text-align: center;"><br /></div> </div>Chandni Vermahttp://www.blogger.com/profile/16416503906800854146noreply@blogger.com0tag:blogger.com,1999:blog-2576048997095865051.post-68226945246361447162022-04-05T16:57:00.003+05:302022-04-05T17:07:18.907+05:30Leetcode Problem: Climbing Stairs<p> <b>Problem of Today: Climbing Stairs</b></p><p><b>Problem description</b>: https://leetcode.com/problems/climbing-stairs/</p><p><b>Solution Approach</b>: Memoization</p><p><b>Solution: </b></p><table style="color: #333333; font-family: Verdana, Helvetica, Arial, sans-serif;"><tbody><tr><td><pre style="line-height: 16.25px; margin-bottom: 0px; margin-top: 0px;"> 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18</pre></td><td><pre style="line-height: 16.25px; margin-bottom: 0px; margin-top: 0px;"><span style="color: #008800; font-weight: bold;">class</span> <span style="color: #bb0066; font-weight: bold;">Solution</span> {
<span style="color: #008800; font-weight: bold;">private</span> <span style="color: #333399; font-weight: bold;">int</span> memo[];
<span style="color: #888888;">// Bottom-up</span>
<span style="color: #008800; font-weight: bold;">public</span> <span style="color: #333399; font-weight: bold;">int</span> <span style="color: #0066bb; font-weight: bold;">climbStairs</span>(<span style="color: #333399; font-weight: bold;">int</span> n) {
memo = <span style="color: #008800; font-weight: bold;">new</span> <span style="color: #333399; font-weight: bold;">int</span>[n+<span style="color: #0000dd; font-weight: bold;">1</span>];
<span style="color: #008800; font-weight: bold;">for</span> (<span style="color: #333399; font-weight: bold;">int</span> i=<span style="color: #0000dd; font-weight: bold;">0</span>; i<=n; i++) {
memo[n] = -<span style="color: #0000dd; font-weight: bold;">1</span>;
}
memo[<span style="color: #0000dd; font-weight: bold;">0</span>] = <span style="color: #0000dd; font-weight: bold;">1</span>;
memo[<span style="color: #0000dd; font-weight: bold;">1</span>] = <span style="color: #0000dd; font-weight: bold;">1</span>;
<span style="color: #008800; font-weight: bold;">for</span> (<span style="color: #333399; font-weight: bold;">int</span> i=<span style="color: #0000dd; font-weight: bold;">2</span>; i<=n; i++) {
memo[i] = memo[i-<span style="color: #0000dd; font-weight: bold;">1</span>] + memo[i-<span style="color: #0000dd; font-weight: bold;">2</span>];
}
<span style="color: #008800; font-weight: bold;">return</span> memo[n];
}
}</pre></td></tr></tbody></table><p><br /></p><p>Happy Coding!</p><p><br />Love! ❤️ <br />#Lets #Code<br /><br />Follow us on :<br /></p><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhfUYmRhkX_i4K0oX-yu0o2lSuknyicVjl4o4l2JjYvzxva1TTtNY_tOnKheAfM3pccf9EwloOQ2se0r75P_5yFWskZ47qK5Tu1s7FkmghH2Lux8u1ARz-WLPdSIQ5QNpdWTxh76BNiCNg/s20/TwitterTransparentBG-icon.png" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="17" data-original-width="20" height="17" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhfUYmRhkX_i4K0oX-yu0o2lSuknyicVjl4o4l2JjYvzxva1TTtNY_tOnKheAfM3pccf9EwloOQ2se0r75P_5yFWskZ47qK5Tu1s7FkmghH2Lux8u1ARz-WLPdSIQ5QNpdWTxh76BNiCNg/s0/TwitterTransparentBG-icon.png" width="20" /></a></div><p><a href="https://twitter.com/ThinkAlgorithms">https://twitter.com/ThinkAlgorithms</a></p><div><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhQrO6XtJFalqwzQpLck9X5UaC8fWeHBe2lFtjkrygS8By9k5K2EJlK5Gl3MbZyrg3NvHwKzxEdxeCyQ5RyHWDpa0WXyoCm-nCFXuSPgOCyREA1xGcraDJsN3EDFr12a7VaIZUhIqqcs4k/s21/FBimageTransparentBG-Icon.png" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="21" data-original-width="20" height="21" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhQrO6XtJFalqwzQpLck9X5UaC8fWeHBe2lFtjkrygS8By9k5K2EJlK5Gl3MbZyrg3NvHwKzxEdxeCyQ5RyHWDpa0WXyoCm-nCFXuSPgOCyREA1xGcraDJsN3EDFr12a7VaIZUhIqqcs4k/s0/FBimageTransparentBG-Icon.png" width="20" /></a></div><a href="https://www.facebook.com/theAlgorithmicCoder">https://www.facebook.com/theAlgorithmicCoder</a><br /><div class="separator" style="clear: both; text-align: center;"><br /></div> </div><p><br /></p>Chandni Vermahttp://www.blogger.com/profile/16416503906800854146noreply@blogger.com0tag:blogger.com,1999:blog-2576048997095865051.post-9858782482943182852021-12-06T01:52:00.003+05:302021-12-06T02:04:42.169+05:30LeetCode Medium: Generate Parentheses<p>Dear followers,</p><p><br /></p><p>Tonight, I came across a nice problem for post-dinner exercise, about generating all possible valid parentheses sequences given the number of brackets to use in total.</p><p>PROBLEM LINK: https://leetcode.com/problems/generate-parentheses/</p><p>PROBLEM SOLVING APPROACH: Recursion (using Choice Diagram and Decision tree)</p><p>TIME-COMPLEXITY: O(2^n) in the worst case but the input n is given to be max 8, so very much doable :)</p><p><br /></p><p>Here's a sample Java solution for your reference:</p><p><br /></p>
<pre>class Solution {
public List<String> generateParenthesis(int n) {
ArrayList<String> generatedParentheses = new ArrayList<>();
genParenthesesRecur(n, n, "", generatedParentheses);
return generatedParentheses;
}
private void genParenthesesRecur (int remOpenBrackets, int remClosingBrackets, String outputFromCaller, List<String> generatedParentheses) {
// Base Cases
if (remOpenBrackets < 0 || remClosingBrackets < 0)
return;
if (remClosingBrackets < remOpenBrackets) {
return;
}
if (remOpenBrackets == 0 && remClosingBrackets == 0) {
generatedParentheses.add(outputFromCaller);
}
// Recursive Case
String opUsingAnOpeningBracket = outputFromCaller + "(";
genParenthesesRecur(remOpenBrackets-1, remClosingBrackets, opUsingAnOpeningBracket, generatedParentheses);
if (remClosingBrackets > remOpenBrackets) {
String opUsingAClosingBracket = outputFromCaller + ")";
genParenthesesRecur(remOpenBrackets, remClosingBrackets-1, opUsingAClosingBracket, generatedParentheses);
}
}
}
</pre>
<p>Thanks for Reading!</p><p>Happy Programming!!</p><p><br /></p><p style="caret-color: rgb(255, 255, 255); font-family: Lato, sans-serif; font-size: 16px;">Love! ❤️ <br />#Lets #Code<br /><br />Follow us on :<br /></p><div class="separator" style="caret-color: rgb(255, 255, 255); clear: both; color: white; font-family: Lato, sans-serif; font-size: 16px; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhfUYmRhkX_i4K0oX-yu0o2lSuknyicVjl4o4l2JjYvzxva1TTtNY_tOnKheAfM3pccf9EwloOQ2se0r75P_5yFWskZ47qK5Tu1s7FkmghH2Lux8u1ARz-WLPdSIQ5QNpdWTxh76BNiCNg/s20/TwitterTransparentBG-icon.png" style="clear: left; color: #77e4ff; float: left; margin-bottom: 1em; margin-right: 1em; text-decoration: none;"><img border="0" data-original-height="17" data-original-width="20" height="17" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhfUYmRhkX_i4K0oX-yu0o2lSuknyicVjl4o4l2JjYvzxva1TTtNY_tOnKheAfM3pccf9EwloOQ2se0r75P_5yFWskZ47qK5Tu1s7FkmghH2Lux8u1ARz-WLPdSIQ5QNpdWTxh76BNiCNg/s0/TwitterTransparentBG-icon.png" style="border: 0px; height: auto; max-width: 100%;" width="20" /></a></div><p style="caret-color: rgb(255, 255, 255); color: white; font-family: Lato, sans-serif; font-size: 16px;"><a href="https://twitter.com/ThinkAlgorithms" style="color: #77e4ff; text-decoration: none;">https://twitter.com/ThinkAlgorithms</a></p><div style="caret-color: rgb(255, 255, 255); color: white; font-family: Lato, sans-serif; font-size: 16px;"><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhQrO6XtJFalqwzQpLck9X5UaC8fWeHBe2lFtjkrygS8By9k5K2EJlK5Gl3MbZyrg3NvHwKzxEdxeCyQ5RyHWDpa0WXyoCm-nCFXuSPgOCyREA1xGcraDJsN3EDFr12a7VaIZUhIqqcs4k/s21/FBimageTransparentBG-Icon.png" style="clear: left; color: #77e4ff; float: left; margin-bottom: 1em; margin-right: 1em; text-decoration: none;"><img border="0" data-original-height="21" data-original-width="20" height="21" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhQrO6XtJFalqwzQpLck9X5UaC8fWeHBe2lFtjkrygS8By9k5K2EJlK5Gl3MbZyrg3NvHwKzxEdxeCyQ5RyHWDpa0WXyoCm-nCFXuSPgOCyREA1xGcraDJsN3EDFr12a7VaIZUhIqqcs4k/s0/FBimageTransparentBG-Icon.png" style="border: 0px; height: auto; max-width: 100%;" width="20" /></a></div><a href="https://www.facebook.com/theAlgorithmicCoder" style="color: #77e4ff; text-decoration: none;">https://www.facebook.com/theAlgorithmicCoder</a></div><p><br /></p>Chandni Vermahttp://www.blogger.com/profile/16416503906800854146noreply@blogger.com0tag:blogger.com,1999:blog-2576048997095865051.post-66800454452524145532021-12-05T23:08:00.004+05:302021-12-06T02:04:30.165+05:30Leetcode Easy: Longest Common Prefix<p>Tea-time snacking!</p><p><br /></p><p>PROBLEM: https://leetcode.com/problems/longest-common-prefix/</p><p>TIME-COMPLEXITY: O(n*m) where n is the number of strings in input and m is the length of longest common prefix.</p><p><br /></p><p>Sample Java Solution for tea-time snacking:</p><p><br /></p>
<pre>class Solution {
public String longestCommonPrefix(String[] strs) {
if (strs.length == 1)
return strs[0];
int minLen = Integer.MAX_VALUE;
for (int i=0; i<strs.length; i++) {
minLen = Math.min(minLen, strs[i].length());
}
int lastPastIdx = minLen;
outer:
for (int i=0; i<minLen; i++) {
char ch = strs[0].charAt(i);
for (int str=0; str<strs.length; str++) {
if (strs[str].charAt(i) != ch) {
lastPastIdx = i;
break outer;
}
}
}
return strs[0].substring(0, lastPastIdx);
}
}
</pre>
<p>Enjoy and Happy Coding!!</p><p><br /></p><p style="caret-color: rgb(255, 255, 255); font-family: Lato, sans-serif; font-size: 16px;">Love! ❤️ <br />#Lets #Code<br /><br />Follow us on :<br /></p><div class="separator" style="caret-color: rgb(255, 255, 255); clear: both; color: white; font-family: Lato, sans-serif; font-size: 16px; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhfUYmRhkX_i4K0oX-yu0o2lSuknyicVjl4o4l2JjYvzxva1TTtNY_tOnKheAfM3pccf9EwloOQ2se0r75P_5yFWskZ47qK5Tu1s7FkmghH2Lux8u1ARz-WLPdSIQ5QNpdWTxh76BNiCNg/s20/TwitterTransparentBG-icon.png" style="clear: left; color: #77e4ff; float: left; margin-bottom: 1em; margin-right: 1em; text-decoration: none;"><img border="0" data-original-height="17" data-original-width="20" height="17" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhfUYmRhkX_i4K0oX-yu0o2lSuknyicVjl4o4l2JjYvzxva1TTtNY_tOnKheAfM3pccf9EwloOQ2se0r75P_5yFWskZ47qK5Tu1s7FkmghH2Lux8u1ARz-WLPdSIQ5QNpdWTxh76BNiCNg/s0/TwitterTransparentBG-icon.png" style="border: 0px; height: auto; max-width: 100%;" width="20" /></a></div><p style="caret-color: rgb(255, 255, 255); color: white; font-family: Lato, sans-serif; font-size: 16px;"><a href="https://twitter.com/ThinkAlgorithms" style="color: #77e4ff; text-decoration: none;">https://twitter.com/ThinkAlgorithms</a></p><div style="caret-color: rgb(255, 255, 255); color: white; font-family: Lato, sans-serif; font-size: 16px;"><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhQrO6XtJFalqwzQpLck9X5UaC8fWeHBe2lFtjkrygS8By9k5K2EJlK5Gl3MbZyrg3NvHwKzxEdxeCyQ5RyHWDpa0WXyoCm-nCFXuSPgOCyREA1xGcraDJsN3EDFr12a7VaIZUhIqqcs4k/s21/FBimageTransparentBG-Icon.png" style="clear: left; color: #77e4ff; float: left; margin-bottom: 1em; margin-right: 1em; text-decoration: none;"><img border="0" data-original-height="21" data-original-width="20" height="21" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhQrO6XtJFalqwzQpLck9X5UaC8fWeHBe2lFtjkrygS8By9k5K2EJlK5Gl3MbZyrg3NvHwKzxEdxeCyQ5RyHWDpa0WXyoCm-nCFXuSPgOCyREA1xGcraDJsN3EDFr12a7VaIZUhIqqcs4k/s0/FBimageTransparentBG-Icon.png" style="border: 0px; height: auto; max-width: 100%;" width="20" /></a></div><a href="https://www.facebook.com/theAlgorithmicCoder" style="color: #77e4ff; text-decoration: none;">https://www.facebook.com/theAlgorithmicCoder</a></div>Chandni Vermahttp://www.blogger.com/profile/16416503906800854146noreply@blogger.com0tag:blogger.com,1999:blog-2576048997095865051.post-12592098945056926292021-12-04T15:58:00.002+05:302021-12-04T15:58:13.523+05:30LeetCode Medium Trick Problem: Longest Consecutive Sequence<p><br /></p><p><br /></p><p>Came across this problem on Leetcode, which requires one to focus on optimization.</p><p><br /></p><p>PROBLEM LINK: https://leetcode.com/problems/longest-consecutive-sequence</p><p>TIME COMPLEXITY: O(n) at worst case where n is the number of elements in the input array (precisely the constant factor for n is 2)</p><p>APPROACH: The most naive approach to solve this problem would have been to sort the input array using comparison sort in O(n lg n) worst case time complexity and then in single pass find the length of the consecutive sequences in the same, resulting in overall worst case time complexity on O(n lg n).</p><p>But, if we notice carefully, we can make use of a trick to solve the problem in O(n) worst case time complexity. The trick makes a space trade off of O(n) and makes use of a HashSet to store the values to quickly check if any number exists in the input array. Then, it checks for all values in input, if it is the start of a consecutive sequence by checking presence of 1 lesser value than that on the number line, in the number Set. If any start-of-consecutive-range is found in the array elements, the length of the range is found by consecutively checking all the numbers in the increasing order on the number line consecutively.</p><p>In each such iteration of the numbers in input array, the length of the max-range is updated and the largest value is returned at the end of all iterations.</p><p><br /></p><p>Here's a sample code for the same:</p><p><br /></p>
<pre>class Solution {
public int longestConsecutive(int[] nums) {
Set<integer> numberSet = new HashSet<integer> ();
// Add numbers to Set while updating length of the longest consecutive elements sequence
int maxLLCES = 0, currLLCES = 0;
for (int i=0; i<nums.length; i++) {
numberSet.add (nums[i]);
}
for (int i=0; i<nums.length; i++) {
if (!numberSet.contains(nums[i]-1)) {
// nums[i] is not a start of a consecutive sequence
currLLCES = 1;
int checkNum = nums[i]+1;
while(numberSet.contains(checkNum)) {
currLLCES++;
checkNum++;
}
maxLLCES = Math.max(maxLLCES, currLLCES);
// System.out.println("Updated maxLLCES:" + maxLLCES);
}
}
return maxLLCES;
}
}</integer></integer></pre>
<p><br /></p><p><br /></p><p>Do share your thoughts and feel free to talk about the alternatives/optimisations you feel can be done in the comment section!</p><p><br />Love! ❤️ <br />#Lets #Code<br /><br />Follow us on :<br /></p><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhfUYmRhkX_i4K0oX-yu0o2lSuknyicVjl4o4l2JjYvzxva1TTtNY_tOnKheAfM3pccf9EwloOQ2se0r75P_5yFWskZ47qK5Tu1s7FkmghH2Lux8u1ARz-WLPdSIQ5QNpdWTxh76BNiCNg/s20/TwitterTransparentBG-icon.png" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="17" data-original-width="20" height="17" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhfUYmRhkX_i4K0oX-yu0o2lSuknyicVjl4o4l2JjYvzxva1TTtNY_tOnKheAfM3pccf9EwloOQ2se0r75P_5yFWskZ47qK5Tu1s7FkmghH2Lux8u1ARz-WLPdSIQ5QNpdWTxh76BNiCNg/s0/TwitterTransparentBG-icon.png" width="20" /></a></div><p><a href="https://twitter.com/ThinkAlgorithms">https://twitter.com/ThinkAlgorithms</a></p><div><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhQrO6XtJFalqwzQpLck9X5UaC8fWeHBe2lFtjkrygS8By9k5K2EJlK5Gl3MbZyrg3NvHwKzxEdxeCyQ5RyHWDpa0WXyoCm-nCFXuSPgOCyREA1xGcraDJsN3EDFr12a7VaIZUhIqqcs4k/s21/FBimageTransparentBG-Icon.png" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="21" data-original-width="20" height="21" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhQrO6XtJFalqwzQpLck9X5UaC8fWeHBe2lFtjkrygS8By9k5K2EJlK5Gl3MbZyrg3NvHwKzxEdxeCyQ5RyHWDpa0WXyoCm-nCFXuSPgOCyREA1xGcraDJsN3EDFr12a7VaIZUhIqqcs4k/s0/FBimageTransparentBG-Icon.png" width="20" /></a></div><a href="https://www.facebook.com/theAlgorithmicCoder">https://www.facebook.com/theAlgorithmicCoder</a><br /><div class="separator" style="clear: both; text-align: center;"><br /></div> <br /></div><p><br /></p><p><br /></p>
Chandni Vermahttp://www.blogger.com/profile/16416503906800854146noreply@blogger.com0tag:blogger.com,1999:blog-2576048997095865051.post-2667757793613250502021-12-03T14:39:00.007+05:302021-12-04T15:25:59.829+05:30Recursion Series: Deleting the middle element from a stack<p>This post marks the start point of the much awaited recursion series on Let'sCode_ =) </p><p>We start it with a GeeksForGeeks problem : <a href="https://www.geeksforgeeks.org/delete-middle-element-stack/">https://www.geeksforgeeks.org/delete-middle-element-stack/</a></p><p><br /></p><p>Position of Middle element of all elements from top of stack (1 based):</p><blockquote style="border: none; margin: 0px 0px 0px 40px; padding: 0px;"><p style="text-align: left;">stack.size()/2 + 1</p></blockquote><p><br /></p><p>Now, to build an effective solution we can use:</p><p><b>Methodology</b>: <b>Recursion</b></p><p><b>Time Complexity</b>:<b> O(n)</b> where n is the number of elements in the stack</p><p><b>Space Complexity</b>: <b>O(n)</b> considering the accumulation of constant space in each level of the recursive stack. <b>O(1)</b> if we dis-consider the stack space accumulation.</p><p><br /></p><p>Here is one such solution:</p><p>
</p><pre><integer><integer><integer><-- --todeletepos="" base="" case="" deletemidrecur="" int="" nteger="" printstack="" private="" return="" stack.pop="" stack.push="" stack="" static="" tack="" top="" void="">/*package whatever //do not write package name here */
import java.io.*;
import java.util.*;
class GFG {
public static void main (String[] args) {
System.out.println("GfG!");
Stack<Integer> stack = new Stack<>();
stack.push(6);
stack.push(5);
stack.push(4);
stack.push(3);
stack.push(2);
stack.push(1);
deleteMid(stack);
}
private static void deleteMid(Stack<Integer> stack) {
if (stack == null)
return;
if (stack.isEmpty())
return;
int mid = stack.size()/2+1;
deleteMidRecur(stack, mid);
printStack(stack);
}
private static void deleteMidRecur (Stack<Integer> stack, int toDeletePos) {
if (toDeletePos == 1) {
// delete this element <-- base case
stack.pop();
return;
}
int top = stack.pop();
deleteMidRecur(stack, --toDeletePos);
stack.push(top);
}
private static void printStack (Stack<Integer> stack) {
while (!stack.isEmpty()) {
System.out.println(stack.pop());
}
}
}
</--></integer></integer></integer></pre>
<p></p><p>IMO, such are the most efficient solutions to this problem. So share your thoughts and let me know your point of views.</p><p><br /></p><p>Happy Coding!</p><p><br />Love! ❤️ <br />#Lets #Code<br /><br />Follow us on :<br /></p><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhfUYmRhkX_i4K0oX-yu0o2lSuknyicVjl4o4l2JjYvzxva1TTtNY_tOnKheAfM3pccf9EwloOQ2se0r75P_5yFWskZ47qK5Tu1s7FkmghH2Lux8u1ARz-WLPdSIQ5QNpdWTxh76BNiCNg/s20/TwitterTransparentBG-icon.png" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="17" data-original-width="20" height="17" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhfUYmRhkX_i4K0oX-yu0o2lSuknyicVjl4o4l2JjYvzxva1TTtNY_tOnKheAfM3pccf9EwloOQ2se0r75P_5yFWskZ47qK5Tu1s7FkmghH2Lux8u1ARz-WLPdSIQ5QNpdWTxh76BNiCNg/s0/TwitterTransparentBG-icon.png" width="20" /></a></div><p>https://twitter.com/ThinkAlgorithms</p><div><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhQrO6XtJFalqwzQpLck9X5UaC8fWeHBe2lFtjkrygS8By9k5K2EJlK5Gl3MbZyrg3NvHwKzxEdxeCyQ5RyHWDpa0WXyoCm-nCFXuSPgOCyREA1xGcraDJsN3EDFr12a7VaIZUhIqqcs4k/s21/FBimageTransparentBG-Icon.png" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="21" data-original-width="20" height="21" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhQrO6XtJFalqwzQpLck9X5UaC8fWeHBe2lFtjkrygS8By9k5K2EJlK5Gl3MbZyrg3NvHwKzxEdxeCyQ5RyHWDpa0WXyoCm-nCFXuSPgOCyREA1xGcraDJsN3EDFr12a7VaIZUhIqqcs4k/s0/FBimageTransparentBG-Icon.png" width="20" /></a></div> https://www.facebook.com/theAlgorithmicCoder</div>
Chandni Vermahttp://www.blogger.com/profile/16416503906800854146noreply@blogger.com0tag:blogger.com,1999:blog-2576048997095865051.post-17906167125681638232021-10-13T00:55:00.017+05:302021-10-13T01:39:23.001+05:30Beware of Multiple internet versions<p>Some time ago, I submitted an email to malwarebytes with data depicting the presence of multiple websites for an original tricking people into targetted scams.<br /><br />In light of yesterday's (12 October, 2021's) news where malwareBytes admits and warns users of the same, I'd like to point out that not only for sites like the MalwareBytes.com site where one can be tricked into a duplicate site with malformed hyperlinks, even the Search Giant, Google's site has many duplicate websites, including 1 which I found my own internet pointing to on nslookup.</p><p><br /></p><p>Here are the relevant screenshots worth the surprise:</p><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjLP0hwaTc7xxx1-iCP7gskSmQozhm8b-vFBmTODNzJt6biaqCu-MlAtc3hfhhovt2NPIAPovbuXZUq4V3bYjVuSzk2WmlqxfAqpl_62VdBnylrTccQwe9iX5vNMwWCwwqqBZQlU3fwTRI/s1440/Screenshot+2021-10-13+at+12.35.53+AM.png" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="900" data-original-width="1440" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjLP0hwaTc7xxx1-iCP7gskSmQozhm8b-vFBmTODNzJt6biaqCu-MlAtc3hfhhovt2NPIAPovbuXZUq4V3bYjVuSzk2WmlqxfAqpl_62VdBnylrTccQwe9iX5vNMwWCwwqqBZQlU3fwTRI/s16000/Screenshot+2021-10-13+at+12.35.53+AM.png" /></a></div><div><br /></div><div><br /></div>Below you can see that my www.google.com entry points to the IP address whose reverse DNS lookup is the site-name which I have copied and hit with my web browser as seen in the above screenshot.<div><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhxEa3X_OJR7Kdh2JF5HCT8sh7ERj6MhIe4kZKuBwV5IpMZHVp7QcrdKZaSf8C7JaA6xBO0zRN8lftHvDNkpOWOgmUqKFM2cvCYZy-7VhMwRRoHQo37fg8AXXMM7dOwkDkJzFwGE8mAiG0/s1440/Screenshot+2021-10-13+at+12.36.10+AM.png" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="900" data-original-width="1440" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhxEa3X_OJR7Kdh2JF5HCT8sh7ERj6MhIe4kZKuBwV5IpMZHVp7QcrdKZaSf8C7JaA6xBO0zRN8lftHvDNkpOWOgmUqKFM2cvCYZy-7VhMwRRoHQo37fg8AXXMM7dOwkDkJzFwGE8mAiG0/s16000/Screenshot+2021-10-13+at+12.36.10+AM.png" /></a></div><div><br /></div><div>For your reference my /etc/resolv.conf, which is used for local entries for DNS lookup remained auto-generated, and looked like this (notice trail):</div><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhwBAQIbW4MD11ngQgcNU3idNcGHpg-98bCixYEyGYvtRQfqjQC6mUsJgBOEclgBVcOjOiDwukGG9ocWaJhyphenhyphenpn91V0xCUzqHWFQlI5Ua1fY1zeRInsxxlGhukXBLPl0PIj-tPUmQDfz5nU/s1440/Screenshot+2021-10-13+at+1.30.01+AM.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="900" data-original-width="1440" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhwBAQIbW4MD11ngQgcNU3idNcGHpg-98bCixYEyGYvtRQfqjQC6mUsJgBOEclgBVcOjOiDwukGG9ocWaJhyphenhyphenpn91V0xCUzqHWFQlI5Ua1fY1zeRInsxxlGhukXBLPl0PIj-tPUmQDfz5nU/s16000/Screenshot+2021-10-13+at+1.30.01+AM.png" /></a></div><br /><div><br /></div><div>All-in-all:</div><div><br /></div><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg8uD-ojPtgV0ohRxex3T3Bxfovzf3phYCpMGt_m8lKsGOeh6_FuNdybED1q9whGvvSfdBN5JFA2YgyBep5pz8SQUgKAnU7WnOhG1_e6PCrsdsj3C-OD2IOc_Aa0vCzEboAkL8t-7EZqAg/s1168/Screenshot+2021-10-13+at+1.37.09+AM.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="782" data-original-width="1168" height="428" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg8uD-ojPtgV0ohRxex3T3Bxfovzf3phYCpMGt_m8lKsGOeh6_FuNdybED1q9whGvvSfdBN5JFA2YgyBep5pz8SQUgKAnU7WnOhG1_e6PCrsdsj3C-OD2IOc_Aa0vCzEboAkL8t-7EZqAg/w640-h428/Screenshot+2021-10-13+at+1.37.09+AM.png" width="640" /></a></div><br /><div class="separator" style="clear: both; text-align: center;"><br /></div><br /><div><br /></div><br /><p><br />Also, with today's announcement of the Honourable Prime Minister of India, where he warns everyone of cyber misinterpretation, such facts come to the rescue of the citizens of the world and provoke them to be more cautious by making them wary and aware!</p><p>Any such websites should be immediately reported and taken down from the internet's DNSes and a regular blacklisting of these should be automated and checked every very frequently on all the World Wide Web's DNSes in my honest opinion. Honestly said, the internet is not safe any more and it's even more evident with such data!</p><p><br /></p><p>In light of the same, and for the lack thereof, to create more awareness and an actionable log of referable observations, Let's Code_ will be launching a dedicated platform where people will be able to report cybersecurity incidents.</p><p><br /></p><p>Keep aware and stay safe!</p><p>Best of Love and Luck,<br /><br />Yours Truly,<br />Chandni Verma<br />Chief Editor,<br />Let's Code_<br /></p><p class="p1" style="font-family: "Helvetica Neue"; font-size: 13px; font-stretch: normal; font-variant-east-asian: normal; font-variant-numeric: normal; line-height: normal; margin: 0px;">#Lets #Code<br /><br />Follow us on :</p><p class="p1" style="font-family: "Helvetica Neue"; font-size: 13px; font-stretch: normal; font-variant-east-asian: normal; font-variant-numeric: normal; line-height: normal; margin: 0px;"><br /></p><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEi7oWhXpTsTi8WmLvjFyiLqeGaRvIrP_w5Nj-sPPVLJ8rSmkJu6XNXcxiVjrBEhAEUdQS3M8nxnC-mswgIs-sACW3uGt7YU8MB0BGSqNseC-I4grH2CA2uml5bM5P2AvYhfNilf6sOPgOM/s20/TwitterTransparentBG-icon.png" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="17" data-original-width="20" height="17" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEi7oWhXpTsTi8WmLvjFyiLqeGaRvIrP_w5Nj-sPPVLJ8rSmkJu6XNXcxiVjrBEhAEUdQS3M8nxnC-mswgIs-sACW3uGt7YU8MB0BGSqNseC-I4grH2CA2uml5bM5P2AvYhfNilf6sOPgOM/s0/TwitterTransparentBG-icon.png" width="20" /></a></div><p><a href="https://twitter.com/ThinkAlgorithms">https://twitter.com/ThinkAlgorithms</a></p><div><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhD4TK-RcRmIm1jQD5qxJW3biRA4qdH-sR5sjYPMEnOyaJrcwZfAmrWjFr7TOuDHn3mH27ayETStwKPCrONdNeia9Iv8uZt9ISJoEad2rm37-qHU2Ges47mrHoqXwEQ2m0oyU4bZ_rchrk/s21/FBimageTransparentBG-Icon.png" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="21" data-original-width="20" height="21" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhD4TK-RcRmIm1jQD5qxJW3biRA4qdH-sR5sjYPMEnOyaJrcwZfAmrWjFr7TOuDHn3mH27ayETStwKPCrONdNeia9Iv8uZt9ISJoEad2rm37-qHU2Ges47mrHoqXwEQ2m0oyU4bZ_rchrk/s0/FBimageTransparentBG-Icon.png" width="20" /></a></div><a href="https://www.facebook.com/theAlgorithmicCoder">https://www.facebook.com/theAlgorithmicCoder</a></div></div>Chandni Vermahttp://www.blogger.com/profile/16416503906800854146noreply@blogger.com0tag:blogger.com,1999:blog-2576048997095865051.post-70565196063663740682021-08-29T10:07:00.002+05:302021-08-29T10:15:51.421+05:30LeetCode Medium: Course Schedule<p> The next problem in the current coding spree was:<br /><br /></p><p><b>Problem Name: </b>Course Schedule</p><p><b>Problem Description</b>: <a href="https://leetcode.com/problems/course-schedule/">https://leetcode.com/problems/course-schedule/</a></p><p><b>Problem Approach used</b>: Detecting cycles on the directed graph pf dependencies using DFS to solve in O(V+E) where V is the number of courses in the input and E is the number of edges between them.</p><p><b>Time Complexity</b>: <b>O(lg n)</b> worst-case time and <b>O(1) auxiliary space</b> complexity</p><p><br /></p><p>Java Solution:</p><p><br /></p><pre style="color: #FFFFFF; line-height: 16.25px; margin-bottom: 0px; margin-top: 0px;"><span style="color: #888888;">//Cycle detection</span>
<span style="color: #888888;">// package com.projects.cv.course_schedule;</span>
<span style="color: #008800; font-weight: bold;">import</span> <span style="color: #0e84b5; font-weight: bold;">java.util.ArrayList</span>;
<span style="color: #008800; font-weight: bold;">import</span> <span style="color: #0e84b5; font-weight: bold;">java.util.HashMap</span>;
<span style="color: #008800; font-weight: bold;">import</span> <span style="color: #0e84b5; font-weight: bold;">java.util.List</span>;
<span style="color: #008800; font-weight: bold;">import</span> <span style="color: #0e84b5; font-weight: bold;">java.util.Map</span>;
<span style="color: #008800; font-weight: bold;">class</span> <span style="color: #bb0066; font-weight: bold;">Solution</span> {
<span style="color: #888888;">// private static Logger logger = Logger.getLogger("MyLogger");</span>
<span style="color: #333399; font-weight: bold;">int</span> nodes;
<span style="color: #008800; font-weight: bold;">public</span> <span style="color: #333399; font-weight: bold;">boolean</span> <span style="color: #0066bb; font-weight: bold;">canFinish</span>(<span style="color: #333399; font-weight: bold;">int</span> numCourses, <span style="color: #333399; font-weight: bold;">int</span>[][] prerequisites) {
<span style="color: #008800; font-weight: bold;">if</span> (prerequisites == <span style="color: #008800; font-weight: bold;">null</span>)
<span style="color: #008800; font-weight: bold;">return</span> <span style="color: #008800; font-weight: bold;">false</span>;
<span style="color: #333399; font-weight: bold;">int</span> pL = prerequisites.<span style="color: #0000cc;">length</span>;
nodes = numCourses;
<span style="color: #888888;">// Build directed graph</span>
Map<Integer, List<Integer>> g = <span style="color: #008800; font-weight: bold;">new</span> HashMap<>();
<span style="color: #008800; font-weight: bold;">for</span> (<span style="color: #333399; font-weight: bold;">int</span> i=<span style="color: #0000dd; font-weight: bold;">0</span>; i<pL; i++) {
<span style="color: #008800; font-weight: bold;">if</span> (!g.<span style="color: #0000cc;">containsKey</span>(prerequisites[i][<span style="color: #0000dd; font-weight: bold;">0</span>]))
g.<span style="color: #0000cc;">put</span>(prerequisites[i][<span style="color: #0000dd; font-weight: bold;">0</span>], <span style="color: #008800; font-weight: bold;">new</span> ArrayList<>());
g.<span style="color: #0000cc;">get</span>(prerequisites[i][<span style="color: #0000dd; font-weight: bold;">0</span>]).<span style="color: #0000cc;">add</span>(prerequisites[i][<span style="color: #0000dd; font-weight: bold;">1</span>]);
}
System.<span style="color: #0000cc;">out</span>.<span style="color: #0000cc;">println</span>(g);
<span style="color: #888888;">//Create visited to prevent re-visiting</span>
<span style="color: #333399; font-weight: bold;">int</span> visited[] = <span style="color: #008800; font-weight: bold;">new</span> <span style="color: #333399; font-weight: bold;">int</span>[numCourses];
<span style="color: #008800; font-weight: bold;">for</span> (<span style="color: #333399; font-weight: bold;">int</span> i=<span style="color: #0000dd; font-weight: bold;">0</span>; i<numCourses; i++) {
<span style="color: #008800; font-weight: bold;">if</span> (visited[i] == <span style="color: #0000dd; font-weight: bold;">0</span>) {
<span style="color: #008800; font-weight: bold;">if</span> (hasCycleDfs(g, visited, i, -<span style="color: #0000dd; font-weight: bold;">1</span>))
<span style="color: #008800; font-weight: bold;">return</span> <span style="color: #008800; font-weight: bold;">false</span>;
}
}
<span style="color: #008800; font-weight: bold;">return</span> <span style="color: #008800; font-weight: bold;">true</span>;
}
<span style="color: #008800; font-weight: bold;">private</span> <span style="color: #333399; font-weight: bold;">boolean</span> <span style="color: #0066bb; font-weight: bold;">hasCycleDfs</span>( Map<Integer, List<Integer>> g, <span style="color: #333399; font-weight: bold;">int</span>[] visited, <span style="color: #333399; font-weight: bold;">int</span> n, <span style="color: #333399; font-weight: bold;">int</span> parent) {
<span style="color: #008800; font-weight: bold;">if</span> (visited[n] == -<span style="color: #0000dd; font-weight: bold;">1</span>) {
<span style="color: #888888;">//current exploration path</span>
System.<span style="color: #0000cc;">out</span>.<span style="color: #0000cc;">println</span>(<span style="background-color: #fff0f0;">"cycle found at u("</span> + parent + <span style="background-color: #fff0f0;">")->v("</span> + n + <span style="background-color: #fff0f0;">")"</span>);
<span style="color: #008800; font-weight: bold;">return</span> <span style="color: #008800; font-weight: bold;">true</span>;
}
<span style="color: #008800; font-weight: bold;">if</span> (visited[n] == <span style="color: #0000dd; font-weight: bold;">1</span>) {
<span style="color: #008800; font-weight: bold;">return</span> <span style="color: #008800; font-weight: bold;">false</span>;
}
visited[n] = -<span style="color: #0000dd; font-weight: bold;">1</span>;
<span style="color: #008800; font-weight: bold;">if</span> (g.<span style="color: #0000cc;">get</span>(n) == <span style="color: #008800; font-weight: bold;">null</span>) { <span style="color: #888888;">// tackle bad callers</span>
visited[n] = <span style="color: #0000dd; font-weight: bold;">1</span>;
<span style="color: #008800; font-weight: bold;">return</span> <span style="color: #008800; font-weight: bold;">false</span>;
}
<span style="color: #008800; font-weight: bold;">for</span> (<span style="color: #333399; font-weight: bold;">int</span> neighBr : g.<span style="color: #0000cc;">get</span>(n)) {
<span style="color: #008800; font-weight: bold;">if</span> (hasCycleDfs(g, visited, neighBr, n))
<span style="color: #008800; font-weight: bold;">return</span> <span style="color: #008800; font-weight: bold;">true</span>;
}
visited[n] = <span style="color: #0000dd; font-weight: bold;">1</span>;
<span style="color: #008800; font-weight: bold;">return</span> <span style="color: #008800; font-weight: bold;">false</span>;
}
<span style="color: #888888;">// public static void main(String[] args) {</span>
<span style="color: #888888;">// Solution s = new Solution();</span>
<span style="color: #888888;">// int[][] deps = {{1, 0}};</span>
<span style="color: #888888;">// s.canFinish(2, deps);</span>
<span style="color: #888888;">// }</span>
}</pre><p><br /></p><p class="p1" style="font-family: "Helvetica Neue"; font-size: 13px; font-stretch: normal; font-variant-east-asian: normal; font-variant-numeric: normal; line-height: normal; margin: 0px;"><br />Love! ❤️ <br />#Lets #Code<br /><br />Follow us on :<br /></p><p class="p2" style="font-family: "Helvetica Neue"; font-size: 13px; font-stretch: normal; font-variant-east-asian: normal; font-variant-numeric: normal; line-height: normal; margin: 0px; min-height: 15px;"><br /></p><p class="p1" style="font-family: "Helvetica Neue"; font-size: 13px; font-stretch: normal; font-variant-east-asian: normal; font-variant-numeric: normal; line-height: normal; margin: 0px;"><br /></p><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEi7oWhXpTsTi8WmLvjFyiLqeGaRvIrP_w5Nj-sPPVLJ8rSmkJu6XNXcxiVjrBEhAEUdQS3M8nxnC-mswgIs-sACW3uGt7YU8MB0BGSqNseC-I4grH2CA2uml5bM5P2AvYhfNilf6sOPgOM/s20/TwitterTransparentBG-icon.png" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="17" data-original-width="20" height="17" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEi7oWhXpTsTi8WmLvjFyiLqeGaRvIrP_w5Nj-sPPVLJ8rSmkJu6XNXcxiVjrBEhAEUdQS3M8nxnC-mswgIs-sACW3uGt7YU8MB0BGSqNseC-I4grH2CA2uml5bM5P2AvYhfNilf6sOPgOM/s0/TwitterTransparentBG-icon.png" width="20" /></a></div>https://twitter.com/ThinkAlgorithms<br /><div style="text-align: left;"><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhD4TK-RcRmIm1jQD5qxJW3biRA4qdH-sR5sjYPMEnOyaJrcwZfAmrWjFr7TOuDHn3mH27ayETStwKPCrONdNeia9Iv8uZt9ISJoEad2rm37-qHU2Ges47mrHoqXwEQ2m0oyU4bZ_rchrk/s21/FBimageTransparentBG-Icon.png" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="21" data-original-width="20" height="21" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhD4TK-RcRmIm1jQD5qxJW3biRA4qdH-sR5sjYPMEnOyaJrcwZfAmrWjFr7TOuDHn3mH27ayETStwKPCrONdNeia9Iv8uZt9ISJoEad2rm37-qHU2Ges47mrHoqXwEQ2m0oyU4bZ_rchrk/s0/FBimageTransparentBG-Icon.png" width="20" /></a></div>https://www.facebook.com/theAlgorithmicCoder</div><div><p></p><p class="p1" style="font-family: "Helvetica Neue"; font-size: 13px; font-stretch: normal; font-variant-east-asian: normal; font-variant-numeric: normal; line-height: normal; margin: 0px;"> </p><p><br /></p><p><br /></p><p><br /></p></div>Chandni Vermahttp://www.blogger.com/profile/16416503906800854146noreply@blogger.com0tag:blogger.com,1999:blog-2576048997095865051.post-72763254105059597582021-08-29T07:35:00.006+05:302021-12-03T14:41:38.403+05:30GeeksforGeeks Medium: Find the Number of Islands<p>Yesterday I solved a few hands-on coding problems using Java programming language.</p><p><br /></p><p>I came across this easy problem(called Medium there) over GfG, to turn on the inertia:</p><p><b><br /></b></p><p><b>Problem</b>: Find the Number of Islands</p><p><b>Problem Description</b>: <a href="https://practice.geeksforgeeks.org/problems/find-the-number-of-islands " target="_blank">https://practice.geeksforgeeks.org/problems/find-the-number-of-islands </a></p><p><b>Problem Approach</b>: DFS</p><p><b>Time Complexity</b>: O(V) where v = number of cells in the input grid<br /><br /></p><p>One Java Solution:</p><p><br /></p>
<pre style="color: #FFFFFF; line-height: 16.25px; margin-bottom: 0px; margin-top: 0px;"><span style="color: #888888;">// { Driver Code Starts</span>
<span style="color: #008800; font-weight: bold;">import</span> <span style="color: #0e84b5; font-weight: bold;">java.util.*</span>;
<span style="color: #008800; font-weight: bold;">import</span> <span style="color: #0e84b5; font-weight: bold;">java.lang.*</span>;
<span style="color: #008800; font-weight: bold;">import</span> <span style="color: #0e84b5; font-weight: bold;">java.io.*</span>;
<span style="color: #008800; font-weight: bold;">class</span> <span style="color: #bb0066; font-weight: bold;">GFG</span>
{
<span style="color: #008800; font-weight: bold;">public</span> <span style="color: #008800; font-weight: bold;">static</span> <span style="color: #333399; font-weight: bold;">void</span> <span style="color: #0066bb; font-weight: bold;">main</span>(String[] args) <span style="color: #008800; font-weight: bold;">throws</span> IOException
{
BufferedReader br = <span style="color: #008800; font-weight: bold;">new</span> BufferedReader(<span style="color: #008800; font-weight: bold;">new</span> InputStreamReader(System.<span style="color: #0000cc;">in</span>));
<span style="color: #333399; font-weight: bold;">int</span> T = Integer.<span style="color: #0000cc;">parseInt</span>(br.<span style="color: #0000cc;">readLine</span>().<span style="color: #0000cc;">trim</span>());
<span style="color: #008800; font-weight: bold;">while</span>(T--><span style="color: #0000dd; font-weight: bold;">0</span>)
{
String[] s = br.<span style="color: #0000cc;">readLine</span>().<span style="color: #0000cc;">trim</span>().<span style="color: #0000cc;">split</span>(<span style="background-color: #fff0f0;">" "</span>);
<span style="color: #333399; font-weight: bold;">int</span> n = Integer.<span style="color: #0000cc;">parseInt</span>(s[<span style="color: #0000dd; font-weight: bold;">0</span>]);
<span style="color: #333399; font-weight: bold;">int</span> m = Integer.<span style="color: #0000cc;">parseInt</span>(s[<span style="color: #0000dd; font-weight: bold;">1</span>]);
<span style="color: #333399; font-weight: bold;">char</span>[][] grid = <span style="color: #008800; font-weight: bold;">new</span> <span style="color: #333399; font-weight: bold;">char</span>[n][m];
<span style="color: #008800; font-weight: bold;">for</span>(<span style="color: #333399; font-weight: bold;">int</span> i = <span style="color: #0000dd; font-weight: bold;">0</span>; i < n; i++){
String[] S = br.<span style="color: #0000cc;">readLine</span>().<span style="color: #0000cc;">trim</span>().<span style="color: #0000cc;">split</span>(<span style="background-color: #fff0f0;">" "</span>);
<span style="color: #008800; font-weight: bold;">for</span>(<span style="color: #333399; font-weight: bold;">int</span> j = <span style="color: #0000dd; font-weight: bold;">0</span>; j < m; j++){
grid[i][j] = S[j].<span style="color: #0000cc;">charAt</span>(<span style="color: #0000dd; font-weight: bold;">0</span>);
}
}
Solution obj = <span style="color: #008800; font-weight: bold;">new</span> Solution();
<span style="color: #333399; font-weight: bold;">int</span> ans = obj.<span style="color: #0000cc;">numIslands</span>(grid);
System.<span style="color: #0000cc;">out</span>.<span style="color: #0000cc;">println</span>(ans);
}
}
}<span style="color: #888888;">// } Driver Code Ends</span>
<span style="color: #008800; font-weight: bold;">class</span> <span style="color: #bb0066; font-weight: bold;">Solution</span>
{
<span style="color: #333399; font-weight: bold;">int</span> r, c;
<span style="color: #333399; font-weight: bold;">byte</span>[] xOffset = {<span style="color: #0000dd; font-weight: bold;">1</span>, <span style="color: #0000dd; font-weight: bold;">1</span>, <span style="color: #0000dd; font-weight: bold;">1</span>, <span style="color: #0000dd; font-weight: bold;">0</span>, -<span style="color: #0000dd; font-weight: bold;">1</span>, -<span style="color: #0000dd; font-weight: bold;">1</span>, -<span style="color: #0000dd; font-weight: bold;">1</span>, <span style="color: #0000dd; font-weight: bold;">0</span>};
<span style="color: #333399; font-weight: bold;">byte</span>[] yOffset = {<span style="color: #0000dd; font-weight: bold;">1</span>, <span style="color: #0000dd; font-weight: bold;">0</span>, -<span style="color: #0000dd; font-weight: bold;">1</span>, -<span style="color: #0000dd; font-weight: bold;">1</span>, -<span style="color: #0000dd; font-weight: bold;">1</span>, <span style="color: #0000dd; font-weight: bold;">0</span>, <span style="color: #0000dd; font-weight: bold;">1</span>, <span style="color: #0000dd; font-weight: bold;">1</span>};
<span style="color: #888888;">//Function to find the number of islands.</span>
<span style="color: #008800; font-weight: bold;">public</span> <span style="color: #333399; font-weight: bold;">int</span> <span style="color: #0066bb; font-weight: bold;">numIslands</span>(<span style="color: #333399; font-weight: bold;">char</span>[][] grid)
{
<span style="color: #888888;">// Code here</span>
r = grid.<span style="color: #0000cc;">length</span>;
c = grid[<span style="color: #0000dd; font-weight: bold;">0</span>].<span style="color: #0000cc;">length</span>;
<span style="color: #333399; font-weight: bold;">boolean</span>[][] visited = <span style="color: #008800; font-weight: bold;">new</span> <span style="color: #333399; font-weight: bold;">boolean</span>[r][c];
<span style="color: #333399; font-weight: bold;">int</span> cnt = <span style="color: #0000dd; font-weight: bold;">0</span>;
<span style="color: #008800; font-weight: bold;">for</span> (<span style="color: #333399; font-weight: bold;">int</span> i=<span style="color: #0000dd; font-weight: bold;">0</span>; i<r; i++) {
<span style="color: #008800; font-weight: bold;">for</span>(<span style="color: #333399; font-weight: bold;">int</span> j=<span style="color: #0000dd; font-weight: bold;">0</span>; j<c; j++) {
<span style="color: #008800; font-weight: bold;">if</span> (grid[i][j]==<span style="color: #0044dd;">'1'</span> && !visited[i][j]) {
dfs(grid, visited, i, j);
cnt++;
}
}
}
<span style="color: #008800; font-weight: bold;">return</span> cnt;
}
<span style="color: #008800; font-weight: bold;">private</span> <span style="color: #333399; font-weight: bold;">void</span> <span style="color: #0066bb; font-weight: bold;">dfs</span> (<span style="color: #333399; font-weight: bold;">char</span>[][] grid, <span style="color: #333399; font-weight: bold;">boolean</span>[][] visited, <span style="color: #333399; font-weight: bold;">int</span> x, <span style="color: #333399; font-weight: bold;">int</span> y) {
<span style="color: #888888;">//input validation</span>
<span style="color: #008800; font-weight: bold;">if</span> (!valid (grid, x, y) || visited[x][y]==<span style="color: #008800; font-weight: bold;">true</span>) {
<span style="color: #008800; font-weight: bold;">return</span>;
}
visited[x][y] = <span style="color: #008800; font-weight: bold;">true</span>;
<span style="color: #008800; font-weight: bold;">for</span> (<span style="color: #333399; font-weight: bold;">int</span> i=<span style="color: #0000dd; font-weight: bold;">0</span>; i<<span style="color: #0000dd; font-weight: bold;">8</span>; i++) {
<span style="color: #333399; font-weight: bold;">int</span> newX = x + xOffset[i];
<span style="color: #333399; font-weight: bold;">int</span> newY = y + yOffset[i];
<span style="color: #008800; font-weight: bold;">if</span>(valid(grid, newX, newY) && !visited[newX][newY]) {
dfs(grid, visited, newX, newY);
}
}
}
<span style="color: #333399; font-weight: bold;">boolean</span> <span style="color: #0066bb; font-weight: bold;">valid</span> (<span style="color: #333399; font-weight: bold;">char</span>[][]grid, <span style="color: #333399; font-weight: bold;">int</span> x, <span style="color: #333399; font-weight: bold;">int</span> y) {
<span style="color: #008800; font-weight: bold;">if</span> (x<<span style="color: #0000dd; font-weight: bold;">0</span> || x>=r || y<<span style="color: #0000dd; font-weight: bold;">0</span> || y>=c || grid[x][y] == <span style="color: #0044dd;">'0'</span>){
<span style="color: #008800; font-weight: bold;">return</span> <span style="color: #008800; font-weight: bold;">false</span>;
}
<span style="color: #008800; font-weight: bold;">return</span> <span style="color: #008800; font-weight: bold;">true</span>;
}
}</pre><p><br /></p><p><br /></p><p>Do share your thoughts and feel free to talk about the alternatives/optimisations you feel can be done in the comment section!</p><p><br />Love! ❤️ <br />#Lets #Code<br /><br />Follow us on :<br /></p><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhfUYmRhkX_i4K0oX-yu0o2lSuknyicVjl4o4l2JjYvzxva1TTtNY_tOnKheAfM3pccf9EwloOQ2se0r75P_5yFWskZ47qK5Tu1s7FkmghH2Lux8u1ARz-WLPdSIQ5QNpdWTxh76BNiCNg/s20/TwitterTransparentBG-icon.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="17" data-original-width="20" height="17" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhfUYmRhkX_i4K0oX-yu0o2lSuknyicVjl4o4l2JjYvzxva1TTtNY_tOnKheAfM3pccf9EwloOQ2se0r75P_5yFWskZ47qK5Tu1s7FkmghH2Lux8u1ARz-WLPdSIQ5QNpdWTxh76BNiCNg/s0/TwitterTransparentBG-icon.png" width="20" /></a></div>https://twitter.com/ThinkAlgorithms<div><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhQrO6XtJFalqwzQpLck9X5UaC8fWeHBe2lFtjkrygS8By9k5K2EJlK5Gl3MbZyrg3NvHwKzxEdxeCyQ5RyHWDpa0WXyoCm-nCFXuSPgOCyREA1xGcraDJsN3EDFr12a7VaIZUhIqqcs4k/s21/FBimageTransparentBG-Icon.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="21" data-original-width="20" height="21" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhQrO6XtJFalqwzQpLck9X5UaC8fWeHBe2lFtjkrygS8By9k5K2EJlK5Gl3MbZyrg3NvHwKzxEdxeCyQ5RyHWDpa0WXyoCm-nCFXuSPgOCyREA1xGcraDJsN3EDFr12a7VaIZUhIqqcs4k/s0/FBimageTransparentBG-Icon.png" width="20" /></a></div> https://www.facebook.com/theAlgorithmicCoder<br /><div class="separator" style="clear: both; text-align: center;"><br /></div> <br /><br /> <p></p><p><br /></p><p><br /></p></div>Chandni Vermahttp://www.blogger.com/profile/16416503906800854146noreply@blogger.com0tag:blogger.com,1999:blog-2576048997095865051.post-38748040001667678702021-08-29T06:24:00.002+05:302021-08-29T06:29:03.339+05:30Restarting Shorter and More Intense Problem-Solving SprintsHello Fellas,<div><br /></div><div><br /></div><div>After a long break, I have re-started #Problem #Solving #Tutorials using DS/Algorithms over (this) <a href="https://chandniverma.blogspot.com/" target="_blank">Let's Code Blog</a>, but this time, it's gonna be consisting more intense but shorter #Coding #Sprints over weekends and somewhat lesser live-videos!! :D</div><div><br /></div><div>Join me and get the weekend puzzle-solver activated in you!</div><div><br /></div><div><br /></div><div>✌️</div><div>#LetsCode</div>Chandni Vermahttp://www.blogger.com/profile/16416503906800854146noreply@blogger.com0tag:blogger.com,1999:blog-2576048997095865051.post-71862357812867652592021-02-14T01:33:00.006+05:302021-02-14T01:36:13.580+05:30HackerRank: Reverse a doubly linked list<p><b>Problem Description</b>: https://www.hackerrank.com/challenges/reverse-a-doubly-linked-list/problem</p><p><b>Runtime complexity</b> of my below code: <b>O(n)</b> where n is the size of the linked list.</p><p><b>Solution approach</b>: Recursive</p><p><b>My Java Solution</b>:<br /></p>
<!--HTML generated using hilite.me--><div style="background: rgb(255, 255, 255); border-color: gray; border-image: initial; border-style: solid; border-width: 0.1em 0.1em 0.1em 0.8em; border: solid gray; overflow: auto; padding: 0.2em 0.6em; width: auto;"><table><tbody><tr><td><pre style="line-height: 125%; margin: 0px;"> 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135</pre></td><td><pre style="line-height: 125%; margin: 0px;"><span style="color: #008800; font-weight: bold;">import</span> <span style="color: #0e84b5; font-weight: bold;">java.io.*</span><span style="color: #333333;">;</span>
<span style="color: #008800; font-weight: bold;">import</span> <span style="color: #0e84b5; font-weight: bold;">java.math.*</span><span style="color: #333333;">;</span>
<span style="color: #008800; font-weight: bold;">import</span> <span style="color: #0e84b5; font-weight: bold;">java.security.*</span><span style="color: #333333;">;</span>
<span style="color: #008800; font-weight: bold;">import</span> <span style="color: #0e84b5; font-weight: bold;">java.text.*</span><span style="color: #333333;">;</span>
<span style="color: #008800; font-weight: bold;">import</span> <span style="color: #0e84b5; font-weight: bold;">java.util.*</span><span style="color: #333333;">;</span>
<span style="color: #008800; font-weight: bold;">import</span> <span style="color: #0e84b5; font-weight: bold;">java.util.concurrent.*</span><span style="color: #333333;">;</span>
<span style="color: #008800; font-weight: bold;">import</span> <span style="color: #0e84b5; font-weight: bold;">java.util.regex.*</span><span style="color: #333333;">;</span>
<span style="color: #008800; font-weight: bold;">public</span> <span style="color: #008800; font-weight: bold;">class</span> <span style="color: #bb0066; font-weight: bold;">Solution</span> <span style="color: #333333;">{</span>
<span style="color: #008800; font-weight: bold;">static</span> <span style="color: #008800; font-weight: bold;">class</span> <span style="color: #bb0066; font-weight: bold;">DoublyLinkedListNode</span> <span style="color: #333333;">{</span>
<span style="color: #008800; font-weight: bold;">public</span> <span style="color: #333399; font-weight: bold;">int</span> data<span style="color: #333333;">;</span>
<span style="color: #008800; font-weight: bold;">public</span> DoublyLinkedListNode next<span style="color: #333333;">;</span>
<span style="color: #008800; font-weight: bold;">public</span> DoublyLinkedListNode prev<span style="color: #333333;">;</span>
<span style="color: #008800; font-weight: bold;">public</span> <span style="color: #0066bb; font-weight: bold;">DoublyLinkedListNode</span><span style="color: #333333;">(</span><span style="color: #333399; font-weight: bold;">int</span> nodeData<span style="color: #333333;">)</span> <span style="color: #333333;">{</span>
<span style="color: #008800; font-weight: bold;">this</span><span style="color: #333333;">.</span><span style="color: #0000cc;">data</span> <span style="color: #333333;">=</span> nodeData<span style="color: #333333;">;</span>
<span style="color: #008800; font-weight: bold;">this</span><span style="color: #333333;">.</span><span style="color: #0000cc;">next</span> <span style="color: #333333;">=</span> <span style="color: #008800; font-weight: bold;">null</span><span style="color: #333333;">;</span>
<span style="color: #008800; font-weight: bold;">this</span><span style="color: #333333;">.</span><span style="color: #0000cc;">prev</span> <span style="color: #333333;">=</span> <span style="color: #008800; font-weight: bold;">null</span><span style="color: #333333;">;</span>
<span style="color: #333333;">}</span>
<span style="color: #333333;">}</span>
<span style="color: #008800; font-weight: bold;">static</span> <span style="color: #008800; font-weight: bold;">class</span> <span style="color: #bb0066; font-weight: bold;">DoublyLinkedList</span> <span style="color: #333333;">{</span>
<span style="color: #008800; font-weight: bold;">public</span> DoublyLinkedListNode head<span style="color: #333333;">;</span>
<span style="color: #008800; font-weight: bold;">public</span> DoublyLinkedListNode tail<span style="color: #333333;">;</span>
<span style="color: #008800; font-weight: bold;">public</span> <span style="color: #0066bb; font-weight: bold;">DoublyLinkedList</span><span style="color: #333333;">()</span> <span style="color: #333333;">{</span>
<span style="color: #008800; font-weight: bold;">this</span><span style="color: #333333;">.</span><span style="color: #0000cc;">head</span> <span style="color: #333333;">=</span> <span style="color: #008800; font-weight: bold;">null</span><span style="color: #333333;">;</span>
<span style="color: #008800; font-weight: bold;">this</span><span style="color: #333333;">.</span><span style="color: #0000cc;">tail</span> <span style="color: #333333;">=</span> <span style="color: #008800; font-weight: bold;">null</span><span style="color: #333333;">;</span>
<span style="color: #333333;">}</span>
<span style="color: #008800; font-weight: bold;">public</span> <span style="color: #333399; font-weight: bold;">void</span> <span style="color: #0066bb; font-weight: bold;">insertNode</span><span style="color: #333333;">(</span><span style="color: #333399; font-weight: bold;">int</span> nodeData<span style="color: #333333;">)</span> <span style="color: #333333;">{</span>
DoublyLinkedListNode node <span style="color: #333333;">=</span> <span style="color: #008800; font-weight: bold;">new</span> DoublyLinkedListNode<span style="color: #333333;">(</span>nodeData<span style="color: #333333;">);</span>
<span style="color: #008800; font-weight: bold;">if</span> <span style="color: #333333;">(</span><span style="color: #008800; font-weight: bold;">this</span><span style="color: #333333;">.</span><span style="color: #0000cc;">head</span> <span style="color: #333333;">==</span> <span style="color: #008800; font-weight: bold;">null</span><span style="color: #333333;">)</span> <span style="color: #333333;">{</span>
<span style="color: #008800; font-weight: bold;">this</span><span style="color: #333333;">.</span><span style="color: #0000cc;">head</span> <span style="color: #333333;">=</span> node<span style="color: #333333;">;</span>
<span style="color: #333333;">}</span> <span style="color: #008800; font-weight: bold;">else</span> <span style="color: #333333;">{</span>
<span style="color: #008800; font-weight: bold;">this</span><span style="color: #333333;">.</span><span style="color: #0000cc;">tail</span><span style="color: #333333;">.</span><span style="color: #0000cc;">next</span> <span style="color: #333333;">=</span> node<span style="color: #333333;">;</span>
node<span style="color: #333333;">.</span><span style="color: #0000cc;">prev</span> <span style="color: #333333;">=</span> <span style="color: #008800; font-weight: bold;">this</span><span style="color: #333333;">.</span><span style="color: #0000cc;">tail</span><span style="color: #333333;">;</span>
<span style="color: #333333;">}</span>
<span style="color: #008800; font-weight: bold;">this</span><span style="color: #333333;">.</span><span style="color: #0000cc;">tail</span> <span style="color: #333333;">=</span> node<span style="color: #333333;">;</span>
<span style="color: #333333;">}</span>
<span style="color: #333333;">}</span>
<span style="color: #008800; font-weight: bold;">public</span> <span style="color: #008800; font-weight: bold;">static</span> <span style="color: #333399; font-weight: bold;">void</span> <span style="color: #0066bb; font-weight: bold;">printDoublyLinkedList</span><span style="color: #333333;">(</span>DoublyLinkedListNode node<span style="color: #333333;">,</span> String sep<span style="color: #333333;">,</span> BufferedWriter bufferedWriter<span style="color: #333333;">)</span> <span style="color: #008800; font-weight: bold;">throws</span> IOException <span style="color: #333333;">{</span>
<span style="color: #008800; font-weight: bold;">while</span> <span style="color: #333333;">(</span>node <span style="color: #333333;">!=</span> <span style="color: #008800; font-weight: bold;">null</span><span style="color: #333333;">)</span> <span style="color: #333333;">{</span>
bufferedWriter<span style="color: #333333;">.</span><span style="color: #0000cc;">write</span><span style="color: #333333;">(</span>String<span style="color: #333333;">.</span><span style="color: #0000cc;">valueOf</span><span style="color: #333333;">(</span>node<span style="color: #333333;">.</span><span style="color: #0000cc;">data</span><span style="color: #333333;">));</span>
node <span style="color: #333333;">=</span> node<span style="color: #333333;">.</span><span style="color: #0000cc;">next</span><span style="color: #333333;">;</span>
<span style="color: #008800; font-weight: bold;">if</span> <span style="color: #333333;">(</span>node <span style="color: #333333;">!=</span> <span style="color: #008800; font-weight: bold;">null</span><span style="color: #333333;">)</span> <span style="color: #333333;">{</span>
bufferedWriter<span style="color: #333333;">.</span><span style="color: #0000cc;">write</span><span style="color: #333333;">(</span>sep<span style="color: #333333;">);</span>
<span style="color: #333333;">}</span>
<span style="color: #333333;">}</span>
<span style="color: #333333;">}</span>
<span style="color: #888888;">// Complete the reverse function below.</span>
<span style="color: #888888;">/*</span>
<span style="color: #888888;"> * For your reference:</span>
<span style="color: #888888;"> *</span>
<span style="color: #888888;"> * DoublyLinkedListNode {</span>
<span style="color: #888888;"> * int data;</span>
<span style="color: #888888;"> * DoublyLinkedListNode next;</span>
<span style="color: #888888;"> * DoublyLinkedListNode prev;</span>
<span style="color: #888888;"> * }</span>
<span style="color: #888888;"> *</span>
<span style="color: #888888;"> */</span>
<span style="color: #008800; font-weight: bold;">static</span> DoublyLinkedListNode <span style="color: #0066bb; font-weight: bold;">reverse</span><span style="color: #333333;">(</span>DoublyLinkedListNode head<span style="color: #333333;">)</span> <span style="color: #333333;">{</span>
<span style="color: #008800; font-weight: bold;">return</span> <span style="color: #0066bb; font-weight: bold;">reverseRecur</span><span style="color: #333333;">(</span>head<span style="color: #333333;">,</span> head<span style="color: #333333;">.</span><span style="color: #0000cc;">next</span><span style="color: #333333;">);</span>
<span style="color: #333333;">}</span>
<span style="color: #008800; font-weight: bold;">private</span> <span style="color: #008800; font-weight: bold;">static</span> DoublyLinkedListNode <span style="color: #0066bb; font-weight: bold;">reverseRecur</span><span style="color: #333333;">(</span>DoublyLinkedListNode current<span style="color: #333333;">,</span> DoublyLinkedListNode nextNode<span style="color: #333333;">)</span> <span style="color: #333333;">{</span> <span style="color: #888888;">// 2, 3 3, 4 4, \0</span>
<span style="color: #008800; font-weight: bold;">if</span> <span style="color: #333333;">(</span>current <span style="color: #333333;">==</span> <span style="color: #008800; font-weight: bold;">null</span><span style="color: #333333;">)</span>
<span style="color: #008800; font-weight: bold;">return</span> current<span style="color: #333333;">;</span>
<span style="color: #008800; font-weight: bold;">if</span> <span style="color: #333333;">(</span>nextNode <span style="color: #333333;">==</span> <span style="color: #008800; font-weight: bold;">null</span> <span style="color: #333333;">&&</span> current<span style="color: #333333;">.</span><span style="color: #0000cc;">prev</span> <span style="color: #333333;">==</span> <span style="color: #008800; font-weight: bold;">null</span><span style="color: #333333;">)</span> <span style="color: #333333;">{</span>
<span style="color: #008800; font-weight: bold;">return</span> current<span style="color: #333333;">;</span>
<span style="color: #333333;">}</span>
<span style="color: #888888;">//Node nextNode = current.next; 2</span>
DoublyLinkedListNode prevNode <span style="color: #333333;">=</span> current<span style="color: #333333;">.</span><span style="color: #0000cc;">prev</span><span style="color: #333333;">;</span> <span style="color: #888888;">// \0 1 2 3</span>
<span style="color: #008800; font-weight: bold;">if</span> <span style="color: #333333;">(</span>nextNode <span style="color: #333333;">==</span> <span style="color: #008800; font-weight: bold;">null</span><span style="color: #333333;">)</span> <span style="color: #333333;">{</span>
current<span style="color: #333333;">.</span><span style="color: #0000cc;">prev</span> <span style="color: #333333;">=</span> <span style="color: #008800; font-weight: bold;">null</span><span style="color: #333333;">;</span>
<span style="color: #008800; font-weight: bold;">return</span> current<span style="color: #333333;">;</span> <span style="color: #888888;">// 4</span>
<span style="color: #333333;">}</span>
<span style="color: #888888;">//Assume reversed till current.</span>
DoublyLinkedListNode nextToNext <span style="color: #333333;">=</span> nextNode<span style="color: #333333;">.</span><span style="color: #0000cc;">next</span><span style="color: #333333;">;</span> <span style="color: #888888;">// 4 \0</span>
<span style="color: #888888;">// 1 <-> 2 <-> 3 <-> 4 -> 4<->3<->2<->1</span>
nextNode<span style="color: #333333;">.</span><span style="color: #0000cc;">next</span> <span style="color: #333333;">=</span> current<span style="color: #333333;">;</span> <span style="color: #888888;">//4 <-> 3 <-> 2 <-> 1 -> \0</span>
current<span style="color: #333333;">.</span><span style="color: #0000cc;">prev</span> <span style="color: #333333;">=</span> nextNode<span style="color: #333333;">;</span>
current<span style="color: #333333;">.</span><span style="color: #0000cc;">next</span> <span style="color: #333333;">=</span> prevNode<span style="color: #333333;">;</span>
<span style="color: #008800; font-weight: bold;">return</span> <span style="color: #0066bb; font-weight: bold;">reverseRecur</span><span style="color: #333333;">(</span>nextNode<span style="color: #333333;">,</span> nextToNext<span style="color: #333333;">);</span> <span style="color: #888888;">// 3, 4 4, \0</span>
<span style="color: #333333;">}</span>
<span style="color: #008800; font-weight: bold;">private</span> <span style="color: #008800; font-weight: bold;">static</span> <span style="color: #008800; font-weight: bold;">final</span> Scanner scanner <span style="color: #333333;">=</span> <span style="color: #008800; font-weight: bold;">new</span> Scanner<span style="color: #333333;">(</span>System<span style="color: #333333;">.</span><span style="color: #0000cc;">in</span><span style="color: #333333;">);</span>
<span style="color: #008800; font-weight: bold;">public</span> <span style="color: #008800; font-weight: bold;">static</span> <span style="color: #333399; font-weight: bold;">void</span> <span style="color: #0066bb; font-weight: bold;">main</span><span style="color: #333333;">(</span>String<span style="color: #333333;">[]</span> args<span style="color: #333333;">)</span> <span style="color: #008800; font-weight: bold;">throws</span> IOException <span style="color: #333333;">{</span>
BufferedWriter bufferedWriter <span style="color: #333333;">=</span> <span style="color: #008800; font-weight: bold;">new</span> BufferedWriter<span style="color: #333333;">(</span><span style="color: #008800; font-weight: bold;">new</span> FileWriter<span style="color: #333333;">(</span>System<span style="color: #333333;">.</span><span style="color: #0000cc;">getenv</span><span style="color: #333333;">(</span><span style="background-color: #fff0f0;">"OUTPUT_PATH"</span><span style="color: #333333;">)));</span>
<span style="color: #333399; font-weight: bold;">int</span> t <span style="color: #333333;">=</span> scanner<span style="color: #333333;">.</span><span style="color: #0000cc;">nextInt</span><span style="color: #333333;">();</span>
scanner<span style="color: #333333;">.</span><span style="color: #0000cc;">skip</span><span style="color: #333333;">(</span><span style="background-color: #fff0f0;">"(\r\n|[\n\r\u2028\u2029\u0085])?"</span><span style="color: #333333;">);</span>
<span style="color: #008800; font-weight: bold;">for</span> <span style="color: #333333;">(</span><span style="color: #333399; font-weight: bold;">int</span> tItr <span style="color: #333333;">=</span> <span style="color: #0000dd; font-weight: bold;">0</span><span style="color: #333333;">;</span> tItr <span style="color: #333333;"><</span> t<span style="color: #333333;">;</span> tItr<span style="color: #333333;">++)</span> <span style="color: #333333;">{</span>
DoublyLinkedList llist <span style="color: #333333;">=</span> <span style="color: #008800; font-weight: bold;">new</span> DoublyLinkedList<span style="color: #333333;">();</span>
<span style="color: #333399; font-weight: bold;">int</span> llistCount <span style="color: #333333;">=</span> scanner<span style="color: #333333;">.</span><span style="color: #0000cc;">nextInt</span><span style="color: #333333;">();</span>
scanner<span style="color: #333333;">.</span><span style="color: #0000cc;">skip</span><span style="color: #333333;">(</span><span style="background-color: #fff0f0;">"(\r\n|[\n\r\u2028\u2029\u0085])?"</span><span style="color: #333333;">);</span>
<span style="color: #008800; font-weight: bold;">for</span> <span style="color: #333333;">(</span><span style="color: #333399; font-weight: bold;">int</span> i <span style="color: #333333;">=</span> <span style="color: #0000dd; font-weight: bold;">0</span><span style="color: #333333;">;</span> i <span style="color: #333333;"><</span> llistCount<span style="color: #333333;">;</span> i<span style="color: #333333;">++)</span> <span style="color: #333333;">{</span>
<span style="color: #333399; font-weight: bold;">int</span> llistItem <span style="color: #333333;">=</span> scanner<span style="color: #333333;">.</span><span style="color: #0000cc;">nextInt</span><span style="color: #333333;">();</span>
scanner<span style="color: #333333;">.</span><span style="color: #0000cc;">skip</span><span style="color: #333333;">(</span><span style="background-color: #fff0f0;">"(\r\n|[\n\r\u2028\u2029\u0085])?"</span><span style="color: #333333;">);</span>
llist<span style="color: #333333;">.</span><span style="color: #0000cc;">insertNode</span><span style="color: #333333;">(</span>llistItem<span style="color: #333333;">);</span>
<span style="color: #333333;">}</span>
DoublyLinkedListNode llist1 <span style="color: #333333;">=</span> reverse<span style="color: #333333;">(</span>llist<span style="color: #333333;">.</span><span style="color: #0000cc;">head</span><span style="color: #333333;">);</span>
printDoublyLinkedList<span style="color: #333333;">(</span>llist1<span style="color: #333333;">,</span> <span style="background-color: #fff0f0;">" "</span><span style="color: #333333;">,</span> bufferedWriter<span style="color: #333333;">);</span>
bufferedWriter<span style="color: #333333;">.</span><span style="color: #0000cc;">newLine</span><span style="color: #333333;">();</span>
<span style="color: #333333;">}</span>
bufferedWriter<span style="color: #333333;">.</span><span style="color: #0000cc;">close</span><span style="color: #333333;">();</span>
scanner<span style="color: #333333;">.</span><span style="color: #0000cc;">close</span><span style="color: #333333;">();</span>
<span style="color: #333333;">}</span>
<span style="color: #333333;">}</span>
</pre></td></tr></tbody></table></div>
<p><br /></p><p><br /></p>
<p>Do share your thoughts below!</p><p>Until next time, Happy Coding!</p><p><br /></p>
<div style="text-align: center;"><a data-patreon-widget-type="become-patron-button" href="https://www.patreon.com/bePatron?u=41494657">Become a Patron!</a><script async="" src="https://c6.patreon.com/becomePatronButton.bundle.js"></script></div>Chandni Vermahttp://www.blogger.com/profile/16416503906800854146noreply@blogger.com0tag:blogger.com,1999:blog-2576048997095865051.post-88030053740083861522021-01-23T20:17:00.003+05:302021-02-01T18:59:03.783+05:30LeetCode Medium: Open the Lock<p> Another BFS solvable problem of LeetCode!</p><p><br /></p><p><b>Problem Description</b>: <a href="https://leetcode.com/problems/open-the-lock/">https://leetcode.com/problems/open-the-lock/</a></p><p><b>Problem Approach</b>: BFS</p><p><b>Time Complexity</b>: O(1) as the custom size of state-nodes in this problem is a constant.</p><p><br /></p><p><b>Solution</b>:</p><p><br /></p>
<!--HTML generated using hilite.me--><div style="background: rgb(255, 255, 255); border-color: gray; border-image: initial; border-style: solid; border-width: 0.1em 0.1em 0.1em 0.8em; border: solid gray; overflow: auto; padding: 0.2em 0.6em; width: auto;"><table><tbody><tr><td><pre style="line-height: 125%; margin: 0px;"> 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74</pre></td><td><pre style="line-height: 125%; margin: 0px;"><span style="color: #888888;">//public class OpenTheLock {</span>
<span style="color: #888888;">//}</span>
<span style="color: #008800; font-weight: bold;">import</span> <span style="color: #0e84b5; font-weight: bold;">java.util.*</span><span style="color: #333333;">;</span>
<span style="color: #008800; font-weight: bold;">class</span> <span style="color: #bb0066; font-weight: bold;">State</span> <span style="color: #333333;">{</span>
String code<span style="color: #333333;">;</span>
<span style="color: #333399; font-weight: bold;">int</span> dist<span style="color: #333333;">;</span>
State<span style="color: #333333;">(</span>String code<span style="color: #333333;">,</span> <span style="color: #333399; font-weight: bold;">int</span> dist<span style="color: #333333;">)</span> <span style="color: #333333;">{</span>
<span style="color: #008800; font-weight: bold;">this</span><span style="color: #333333;">.</span><span style="color: #0000cc;">code</span> <span style="color: #333333;">=</span> code<span style="color: #333333;">;</span>
<span style="color: #008800; font-weight: bold;">this</span><span style="color: #333333;">.</span><span style="color: #0000cc;">dist</span> <span style="color: #333333;">=</span> dist<span style="color: #333333;">;</span>
<span style="color: #333333;">}</span>
<span style="color: #333333;">}</span>
<span style="color: #008800; font-weight: bold;">class</span> <span style="color: #bb0066; font-weight: bold;">Solution</span> <span style="color: #333333;">{</span>
<span style="color: #008800; font-weight: bold;">public</span> <span style="color: #333399; font-weight: bold;">int</span> <span style="color: #0066bb; font-weight: bold;">openLock</span><span style="color: #333333;">(</span>String<span style="color: #333333;">[]</span> deadends<span style="color: #333333;">,</span> String target<span style="color: #333333;">)</span> <span style="color: #333333;">{</span>
Set<span style="color: #333333;"><</span>String<span style="color: #333333;">></span> visited <span style="color: #333333;">=</span> <span style="color: #008800; font-weight: bold;">new</span> HashSet<span style="color: #333333;"><>();</span>
Set<span style="color: #333333;"><</span>String<span style="color: #333333;">></span> deadendsSet <span style="color: #333333;">=</span> <span style="color: #008800; font-weight: bold;">new</span> HashSet<span style="color: #333333;"><>();</span>
<span style="color: #008800; font-weight: bold;">for</span> <span style="color: #333333;">(</span>String d <span style="color: #333333;">:</span> deadends<span style="color: #333333;">)</span> <span style="color: #333333;">{</span>
deadendsSet<span style="color: #333333;">.</span><span style="color: #0000cc;">add</span><span style="color: #333333;">(</span>d<span style="color: #333333;">);</span>
<span style="color: #333333;">}</span>
<span style="color: #008800; font-weight: bold;">if</span> <span style="color: #333333;">(</span><span style="background-color: #fff0f0;">"0000"</span><span style="color: #333333;">.</span><span style="color: #0000cc;">equals</span><span style="color: #333333;">(</span>target<span style="color: #333333;">))</span>
<span style="color: #008800; font-weight: bold;">return</span> <span style="color: #0000dd; font-weight: bold;">0</span><span style="color: #333333;">;</span>
<span style="color: #008800; font-weight: bold;">if</span> <span style="color: #333333;">(</span>deadendsSet<span style="color: #333333;">.</span><span style="color: #0000cc;">contains</span><span style="color: #333333;">(</span><span style="background-color: #fff0f0;">"0000"</span><span style="color: #333333;">))</span>
<span style="color: #008800; font-weight: bold;">return</span> <span style="color: #333333;">-</span><span style="color: #0000dd; font-weight: bold;">1</span><span style="color: #333333;">;</span>
Queue<span style="color: #333333;"><</span>State<span style="color: #333333;">></span> q <span style="color: #333333;">=</span> <span style="color: #008800; font-weight: bold;">new</span> LinkedList<span style="color: #333333;"><>();</span>
q<span style="color: #333333;">.</span><span style="color: #0000cc;">add</span><span style="color: #333333;">(</span><span style="color: #008800; font-weight: bold;">new</span> State<span style="color: #333333;">(</span><span style="background-color: #fff0f0;">"0000"</span><span style="color: #333333;">,</span> <span style="color: #0000dd; font-weight: bold;">0</span><span style="color: #333333;">));</span>
visited<span style="color: #333333;">.</span><span style="color: #0000cc;">add</span><span style="color: #333333;">(</span><span style="background-color: #fff0f0;">"0000"</span><span style="color: #333333;">);</span>
<span style="color: #008800; font-weight: bold;">while</span> <span style="color: #333333;">(!</span>q<span style="color: #333333;">.</span><span style="color: #0000cc;">isEmpty</span><span style="color: #333333;">())</span> <span style="color: #333333;">{</span>
State out <span style="color: #333333;">=</span> q<span style="color: #333333;">.</span><span style="color: #0000cc;">remove</span><span style="color: #333333;">();</span>
List<span style="color: #333333;"><</span>String<span style="color: #333333;">></span> neighbours <span style="color: #333333;">=</span> getNeighbours<span style="color: #333333;">(</span>out<span style="color: #333333;">.</span><span style="color: #0000cc;">code</span><span style="color: #333333;">);</span>
<span style="color: #008800; font-weight: bold;">for</span> <span style="color: #333333;">(</span>String n <span style="color: #333333;">:</span> neighbours<span style="color: #333333;">)</span> <span style="color: #333333;">{</span>
<span style="color: #008800; font-weight: bold;">if</span> <span style="color: #333333;">(!</span>visited<span style="color: #333333;">.</span><span style="color: #0000cc;">contains</span><span style="color: #333333;">(</span>n<span style="color: #333333;">)</span> <span style="color: #333333;">&&</span> <span style="color: #333333;">!</span>deadendsSet<span style="color: #333333;">.</span><span style="color: #0000cc;">contains</span><span style="color: #333333;">(</span>n<span style="color: #333333;">))</span> <span style="color: #333333;">{</span>
<span style="color: #008800; font-weight: bold;">if</span> <span style="color: #333333;">(</span>n<span style="color: #333333;">.</span><span style="color: #0000cc;">equals</span><span style="color: #333333;">(</span>target<span style="color: #333333;">))</span>
<span style="color: #008800; font-weight: bold;">return</span> out<span style="color: #333333;">.</span><span style="color: #0000cc;">dist</span><span style="color: #333333;">+</span><span style="color: #0000dd; font-weight: bold;">1</span><span style="color: #333333;">;</span>
State neighState <span style="color: #333333;">=</span> <span style="color: #008800; font-weight: bold;">new</span> State<span style="color: #333333;">(</span>n<span style="color: #333333;">,</span> out<span style="color: #333333;">.</span><span style="color: #0000cc;">dist</span><span style="color: #333333;">+</span><span style="color: #0000dd; font-weight: bold;">1</span><span style="color: #333333;">);</span>
visited<span style="color: #333333;">.</span><span style="color: #0000cc;">add</span><span style="color: #333333;">(</span>n<span style="color: #333333;">);</span>
q<span style="color: #333333;">.</span><span style="color: #0000cc;">add</span><span style="color: #333333;">(</span>neighState<span style="color: #333333;">);</span>
<span style="color: #333333;">}</span>
<span style="color: #333333;">}</span>
<span style="color: #333333;">}</span>
<span style="color: #008800; font-weight: bold;">return</span> <span style="color: #333333;">-</span><span style="color: #0000dd; font-weight: bold;">1</span><span style="color: #333333;">;</span>
<span style="color: #333333;">}</span>
<span style="color: #008800; font-weight: bold;">private</span> List<span style="color: #333333;"><</span>String<span style="color: #333333;">></span> <span style="color: #0066bb; font-weight: bold;">getNeighbours</span><span style="color: #333333;">(</span>String baseState<span style="color: #333333;">)</span> <span style="color: #333333;">{</span>
List<span style="color: #333333;"><</span>String<span style="color: #333333;">></span> res <span style="color: #333333;">=</span> <span style="color: #008800; font-weight: bold;">new</span> ArrayList<span style="color: #333333;"><>();</span>
<span style="color: #333399; font-weight: bold;">char</span><span style="color: #333333;">[]</span> codeChar <span style="color: #333333;">=</span> baseState<span style="color: #333333;">.</span><span style="color: #0000cc;">toCharArray</span><span style="color: #333333;">();</span>
<span style="color: #008800; font-weight: bold;">for</span> <span style="color: #333333;">(</span><span style="color: #333399; font-weight: bold;">int</span> i<span style="color: #333333;">=</span><span style="color: #0000dd; font-weight: bold;">0</span><span style="color: #333333;">;</span> i<span style="color: #333333;"><</span>codeChar<span style="color: #333333;">.</span><span style="color: #0000cc;">length</span><span style="color: #333333;">;</span> i<span style="color: #333333;">++)</span> <span style="color: #333333;">{</span>
String neighState <span style="color: #333333;">=</span> <span style="color: #008800; font-weight: bold;">new</span> String<span style="color: #333333;">();</span>
String c <span style="color: #333333;">=</span> <span style="color: #333333;">((</span>codeChar<span style="color: #333333;">[</span>i<span style="color: #333333;">]-</span><span style="color: #0044dd;">'0'</span><span style="color: #333333;">)+</span><span style="color: #0000dd; font-weight: bold;">1</span><span style="color: #333333;">)%</span><span style="color: #0000dd; font-weight: bold;">10</span> <span style="color: #333333;">+</span> <span style="background-color: #fff0f0;">""</span><span style="color: #333333;">;</span>
<span style="color: #008800; font-weight: bold;">for</span> <span style="color: #333333;">(</span><span style="color: #333399; font-weight: bold;">int</span> idx<span style="color: #333333;">=</span><span style="color: #0000dd; font-weight: bold;">0</span><span style="color: #333333;">;</span> idx<span style="color: #333333;"><</span>codeChar<span style="color: #333333;">.</span><span style="color: #0000cc;">length</span><span style="color: #333333;">;</span> idx<span style="color: #333333;">++)</span>
<span style="color: #008800; font-weight: bold;">if</span> <span style="color: #333333;">(</span>idx <span style="color: #333333;">==</span> i<span style="color: #333333;">)</span>
neighState<span style="color: #333333;">+=</span>c<span style="color: #333333;">;</span>
<span style="color: #008800; font-weight: bold;">else</span>
neighState<span style="color: #333333;">+=</span>codeChar<span style="color: #333333;">[</span>idx<span style="color: #333333;">];</span>
res<span style="color: #333333;">.</span><span style="color: #0000cc;">add</span><span style="color: #333333;">(</span>neighState<span style="color: #333333;">);</span>
neighState <span style="color: #333333;">=</span> <span style="color: #008800; font-weight: bold;">new</span> String<span style="color: #333333;">();</span>
c <span style="color: #333333;">=</span> <span style="color: #333333;">((</span>codeChar<span style="color: #333333;">[</span>i<span style="color: #333333;">]-</span><span style="color: #0044dd;">'0'</span><span style="color: #333333;">)+</span><span style="color: #0000dd; font-weight: bold;">10</span><span style="color: #333333;">-</span><span style="color: #0000dd; font-weight: bold;">1</span><span style="color: #333333;">)%</span><span style="color: #0000dd; font-weight: bold;">10</span> <span style="color: #333333;">+</span> <span style="background-color: #fff0f0;">""</span><span style="color: #333333;">;</span>
<span style="color: #008800; font-weight: bold;">for</span> <span style="color: #333333;">(</span><span style="color: #333399; font-weight: bold;">int</span> idx<span style="color: #333333;">=</span><span style="color: #0000dd; font-weight: bold;">0</span><span style="color: #333333;">;</span> idx<span style="color: #333333;"><</span>codeChar<span style="color: #333333;">.</span><span style="color: #0000cc;">length</span><span style="color: #333333;">;</span> idx<span style="color: #333333;">++)</span>
<span style="color: #008800; font-weight: bold;">if</span> <span style="color: #333333;">(</span>idx <span style="color: #333333;">==</span> i<span style="color: #333333;">)</span>
neighState<span style="color: #333333;">+=</span>c<span style="color: #333333;">;</span>
<span style="color: #008800; font-weight: bold;">else</span>
neighState<span style="color: #333333;">+=</span>codeChar<span style="color: #333333;">[</span>idx<span style="color: #333333;">];</span>
res<span style="color: #333333;">.</span><span style="color: #0000cc;">add</span><span style="color: #333333;">(</span>neighState<span style="color: #333333;">);</span>
<span style="color: #333333;">}</span>
<span style="color: #008800; font-weight: bold;">return</span> res<span style="color: #333333;">;</span>
<span style="color: #333333;">}</span>
<span style="color: #333333;">}</span>
</pre></td></tr></tbody></table></div>
<p><br /></p><p>Have fun, until next time!</p>
<div style="text-align: center;"><a data-patreon-widget-type="become-patron-button" href="https://www.patreon.com/bePatron?u=41494657">Become a Patron!</a><script async="" src="https://c6.patreon.com/becomePatronButton.bundle.js"></script></div>Chandni Vermahttp://www.blogger.com/profile/16416503906800854146noreply@blogger.com0tag:blogger.com,1999:blog-2576048997095865051.post-51758606147460540532021-01-23T16:07:00.014+05:302021-01-27T16:21:05.143+05:30LeetCode Medium: Snakes and Ladders<p>Here's a problem based on the classical snakes and ladders children's game</p><p><b><br /></b></p><p><b>Problem Description</b>: <a href="https://leetcode.com/problems/snakes-and-ladders">https://leetcode.com/problems/snakes-and-ladders</a></p><p><b>Solution Approach</b>: BFS</p><p><b>Time Complexity</b>: O(V) where V is the number of cells in the board-game and E = 6V.</p><p><br /></p><p><b>Solution</b>:</p>
<!-- HTML generated using hilite.me --><div style="background: #ffffff; overflow:auto;width:auto;border:solid gray;border-width:.1em .1em .1em .8em;padding:.2em .6em;"><table><tr><td><pre style="margin: 0; line-height: 125%"> 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68</pre></td><td><pre style="margin: 0; line-height: 125%"><span style="color: #008800; font-weight: bold">class</span> <span style="color: #BB0066; font-weight: bold">Solution</span> <span style="color: #333333">{</span>
<span style="color: #008800; font-weight: bold">public</span> <span style="color: #333399; font-weight: bold">int</span> <span style="color: #0066BB; font-weight: bold">snakesAndLadders</span><span style="color: #333333">(</span><span style="color: #333399; font-weight: bold">int</span><span style="color: #333333">[][]</span> board<span style="color: #333333">)</span> <span style="color: #333333">{</span>
<span style="color: #333399; font-weight: bold">int</span> rows <span style="color: #333333">=</span> board<span style="color: #333333">.</span><span style="color: #0000CC">length</span><span style="color: #333333">;</span>
<span style="color: #333399; font-weight: bold">int</span> cols <span style="color: #333333">=</span> board<span style="color: #333333">[</span><span style="color: #0000DD; font-weight: bold">0</span><span style="color: #333333">].</span><span style="color: #0000CC">length</span><span style="color: #333333">;</span>
<span style="color: #333399; font-weight: bold">int</span> maxSq <span style="color: #333333">=</span> rows<span style="color: #333333">*</span>cols<span style="color: #333333">;</span>
<span style="color: #333399; font-weight: bold">boolean</span> visited<span style="color: #333333">[]</span> <span style="color: #333333">=</span> <span style="color: #008800; font-weight: bold">new</span> <span style="color: #333399; font-weight: bold">boolean</span><span style="color: #333333">[</span>maxSq<span style="color: #333333">];</span>
<span style="color: #333399; font-weight: bold">int</span><span style="color: #333333">[]</span> pred <span style="color: #333333">=</span> <span style="color: #008800; font-weight: bold">new</span> <span style="color: #333399; font-weight: bold">int</span><span style="color: #333333">[</span>maxSq<span style="color: #333333">+</span><span style="color: #0000DD; font-weight: bold">1</span><span style="color: #333333">];</span> <span style="color: #888888">// Allows to print the path as well. Alternatively, a dist[] incrementing at each time can be used too.</span>
Queue<span style="color: #333333"><</span>Integer<span style="color: #333333">></span> squaresQ <span style="color: #333333">=</span> <span style="color: #008800; font-weight: bold">new</span> LinkedList<span style="color: #333333"><>();</span>
squaresQ<span style="color: #333333">.</span><span style="color: #0000CC">add</span><span style="color: #333333">(</span><span style="color: #0000DD; font-weight: bold">1</span><span style="color: #333333">);</span>
visited<span style="color: #333333">[</span><span style="color: #0000DD; font-weight: bold">1</span><span style="color: #333333">]</span> <span style="color: #333333">=</span> <span style="color: #008800; font-weight: bold">true</span><span style="color: #333333">;</span>
pred<span style="color: #333333">[</span><span style="color: #0000DD; font-weight: bold">1</span><span style="color: #333333">]</span> <span style="color: #333333">=</span> <span style="color: #0000DD; font-weight: bold">0</span><span style="color: #333333">;</span>
<span style="color: #997700; font-weight: bold">outer:</span>
<span style="color: #008800; font-weight: bold">while</span><span style="color: #333333">(!</span>squaresQ<span style="color: #333333">.</span><span style="color: #0000CC">isEmpty</span><span style="color: #333333">())</span> <span style="color: #333333">{</span>
<span style="color: #333399; font-weight: bold">int</span> sqOut <span style="color: #333333">=</span> squaresQ<span style="color: #333333">.</span><span style="color: #0000CC">remove</span><span style="color: #333333">();</span>
<span style="color: #008800; font-weight: bold">for</span> <span style="color: #333333">(</span><span style="color: #333399; font-weight: bold">int</span> i<span style="color: #333333">=</span><span style="color: #0000DD; font-weight: bold">1</span><span style="color: #333333">;</span> i<span style="color: #333333"><=</span><span style="color: #0000DD; font-weight: bold">6</span><span style="color: #333333">;</span> i<span style="color: #333333">++)</span> <span style="color: #333333">{</span>
<span style="color: #333399; font-weight: bold">int</span> neighbourSq <span style="color: #333333">=</span> sqOut <span style="color: #333333">+</span> i<span style="color: #333333">;</span>
<span style="color: #008800; font-weight: bold">if</span> <span style="color: #333333">(</span>neighbourSq <span style="color: #333333">></span> maxSq<span style="color: #333333">)</span>
<span style="color: #008800; font-weight: bold">break</span><span style="color: #333333">;</span>
<span style="color: #333399; font-weight: bold">int</span> effRow <span style="color: #333333">=</span> getEffRow<span style="color: #333333">(</span>neighbourSq<span style="color: #333333">,</span> rows<span style="color: #333333">,</span> cols<span style="color: #333333">);</span>
<span style="color: #333399; font-weight: bold">int</span> effCol <span style="color: #333333">=</span> getEffCol<span style="color: #333333">(</span>neighbourSq<span style="color: #333333">,</span> rows<span style="color: #333333">,</span> cols<span style="color: #333333">);</span>
<span style="color: #008800; font-weight: bold">if</span> <span style="color: #333333">(</span>board<span style="color: #333333">[</span>effRow<span style="color: #333333">][</span>effCol<span style="color: #333333">]</span> <span style="color: #333333">!=</span> <span style="color: #333333">-</span><span style="color: #0000DD; font-weight: bold">1</span><span style="color: #333333">)</span> <span style="color: #333333">{</span>
neighbourSq <span style="color: #333333">=</span> board<span style="color: #333333">[</span>effRow<span style="color: #333333">][</span>effCol<span style="color: #333333">];</span>
effRow <span style="color: #333333">=</span> getEffRow<span style="color: #333333">(</span>neighbourSq<span style="color: #333333">,</span> rows<span style="color: #333333">,</span> cols<span style="color: #333333">);</span>
effCol <span style="color: #333333">=</span> getEffCol<span style="color: #333333">(</span>neighbourSq<span style="color: #333333">,</span> rows<span style="color: #333333">,</span> cols<span style="color: #333333">);</span>
<span style="color: #333333">}</span>
<span style="color: #008800; font-weight: bold">if</span> <span style="color: #333333">(</span>neighbourSq <span style="color: #333333">==</span> maxSq<span style="color: #333333">)</span> <span style="color: #333333">{</span>
pred<span style="color: #333333">[</span>neighbourSq<span style="color: #333333">]</span> <span style="color: #333333">=</span> sqOut<span style="color: #333333">;</span>
<span style="color: #008800; font-weight: bold">break</span> outer<span style="color: #333333">;</span>
<span style="color: #333333">}</span>
<span style="color: #008800; font-weight: bold">if</span> <span style="color: #333333">(!</span>visited<span style="color: #333333">[</span>neighbourSq<span style="color: #333333">])</span> <span style="color: #333333">{</span>
visited<span style="color: #333333">[</span>neighbourSq<span style="color: #333333">]</span> <span style="color: #333333">=</span> <span style="color: #008800; font-weight: bold">true</span><span style="color: #333333">;</span>
pred<span style="color: #333333">[</span>neighbourSq<span style="color: #333333">]</span> <span style="color: #333333">=</span> sqOut<span style="color: #333333">;</span> <span style="color: #888888">// Alternatively, can do: dist[neighbourSq] = dist[sqOut]++;</span>
squaresQ<span style="color: #333333">.</span><span style="color: #0000CC">add</span><span style="color: #333333">(</span>neighbourSq<span style="color: #333333">);</span>
<span style="color: #333333">}</span>
<span style="color: #333333">}</span>
<span style="color: #333333">}</span>
<span style="color: #333399; font-weight: bold">int</span> cnt <span style="color: #333333">=</span> <span style="color: #0000DD; font-weight: bold">0</span><span style="color: #333333">;</span>
<span style="color: #333399; font-weight: bold">int</span> predSq <span style="color: #333333">=</span> maxSq<span style="color: #333333">;</span>
<span style="color: #008800; font-weight: bold">if</span> <span style="color: #333333">(</span>pred<span style="color: #333333">[</span>predSq<span style="color: #333333">]</span> <span style="color: #333333">==</span> <span style="color: #0000DD; font-weight: bold">0</span><span style="color: #333333">)</span>
<span style="color: #008800; font-weight: bold">return</span> <span style="color: #333333">-</span><span style="color: #0000DD; font-weight: bold">1</span><span style="color: #333333">;</span>
<span style="color: #008800; font-weight: bold">while</span><span style="color: #333333">(</span>predSq <span style="color: #333333">!=</span> <span style="color: #0000DD; font-weight: bold">1</span><span style="color: #333333">)</span> <span style="color: #333333">{</span>
cnt<span style="color: #333333">++;</span>
predSq <span style="color: #333333">=</span> pred<span style="color: #333333">[</span>predSq<span style="color: #333333">];</span>
<span style="color: #333333">}</span>
<span style="color: #008800; font-weight: bold">return</span> cnt<span style="color: #333333">;</span>
<span style="color: #333333">}</span>
<span style="color: #008800; font-weight: bold">private</span> <span style="color: #333399; font-weight: bold">int</span> <span style="color: #0066BB; font-weight: bold">getEffRow</span><span style="color: #333333">(</span><span style="color: #333399; font-weight: bold">int</span> sq<span style="color: #333333">,</span> <span style="color: #333399; font-weight: bold">int</span> rows<span style="color: #333333">,</span> <span style="color: #333399; font-weight: bold">int</span> cols<span style="color: #333333">)</span> <span style="color: #333333">{</span>
<span style="color: #008800; font-weight: bold">return</span> <span style="color: #333333">(</span>rows <span style="color: #333333">-</span> <span style="color: #0000DD; font-weight: bold">1</span> <span style="color: #333333">-</span> <span style="color: #333333">(</span>sq<span style="color: #333333">-</span><span style="color: #0000DD; font-weight: bold">1</span><span style="color: #333333">)/</span>cols<span style="color: #333333">);</span>
<span style="color: #333333">}</span>
<span style="color: #008800; font-weight: bold">private</span> <span style="color: #333399; font-weight: bold">int</span> <span style="color: #0066BB; font-weight: bold">getEffCol</span><span style="color: #333333">(</span><span style="color: #333399; font-weight: bold">int</span> sq<span style="color: #333333">,</span> <span style="color: #333399; font-weight: bold">int</span> rows<span style="color: #333333">,</span> <span style="color: #333399; font-weight: bold">int</span> cols<span style="color: #333333">)</span> <span style="color: #333333">{</span>
<span style="color: #333399; font-weight: bold">int</span> effCol <span style="color: #333333">=</span> <span style="color: #333333">(</span>sq <span style="color: #333333">-</span><span style="color: #0000DD; font-weight: bold">1</span><span style="color: #333333">)</span> <span style="color: #333333">%</span> cols<span style="color: #333333">;</span> <span style="color: #888888">// 0 based</span>
<span style="color: #008800; font-weight: bold">if</span> <span style="color: #333333">(((</span>sq <span style="color: #333333">-</span> <span style="color: #0000DD; font-weight: bold">1</span><span style="color: #333333">)/</span>cols <span style="color: #333333">+</span> <span style="color: #0000DD; font-weight: bold">1</span><span style="color: #333333">)</span> <span style="color: #333333">%</span> <span style="color: #0000DD; font-weight: bold">2</span> <span style="color: #333333">==</span> <span style="color: #0000DD; font-weight: bold">0</span><span style="color: #333333">)</span> <span style="color: #888888">// even row from bottom:1 based</span>
effCol <span style="color: #333333">=</span> cols <span style="color: #333333">-</span> <span style="color: #0000DD; font-weight: bold">1</span> <span style="color: #333333">-</span> effCol<span style="color: #333333">;</span>
<span style="color: #008800; font-weight: bold">return</span> effCol<span style="color: #333333">;</span>
<span style="color: #333333">}</span>
<span style="color: #333333">}</span>
</pre></td></tr></table></div>
<p><br /></p><p>Until next time,</p>
<script src="http://gist-it.appspot.com/https://github.com/glassrose/LeetCode-ModernJava/blob/master/src/main/java/SnakesAndLadders.java"></script>
<p>Happy Coding!</p>
<div style="text-align: center;"><a data-patreon-widget-type="become-patron-button" href="https://www.patreon.com/bePatron?u=41494657">Become a Patron!</a><script async="" src="https://c6.patreon.com/becomePatronButton.bundle.js"></script></div>Chandni Vermahttp://www.blogger.com/profile/16416503906800854146noreply@blogger.com0tag:blogger.com,1999:blog-2576048997095865051.post-34576242722211428552021-01-18T19:44:00.010+05:302021-01-18T19:55:49.161+05:30LeetCode Medium: Pancake Sorting<p><b>Problem of the day</b>: Pancake Sorting</p><p><b>Problem description</b>: https://leetcode.com/problems/pancake-sorting/</p><p><b>Solution Approach</b>:</p><p>At every iteration for n-1 iterations move the max element in unsorted prefix array to the end of it by following the following steps:</p><p></p><ol style="text-align: left;"><li>Find max element index in unsorted prefix part.</li><li>flip array at that index.</li><li>flip array at index marking the end of unsorted array.</li><li>reduce the pointer marking end of unsorted array by 1 thereby decreasing the unsorted part of the array.</li></ol><p></p><p><b>Solution</b>:</p><p><br />
</p>
<pre>
class Solution {
public List<Integer> pancakeSort(int[] arr) {
if (arr.length<=1) {
return new ArrayList<>();
}
List<Integer> maxIndicesSelectedForFlip;
int endOfUnsortedArray = arr.length-1;
for (int idx=1; idx <= endOfUnsortedArray; idx++) {
//find maxElement, maxElementIndex
int maxElement = Integer.MIN_VALUE, maxElementIndex = -1;
for (int i=0; i < endOfUnsortedArray; i++) {
if (arr[i]>maxElement) {
maxElement = arr[i];
maxElementIndex = i;
}
}
//Flip 0->maxElementIndex
flip(arr, maxElementIndex);
maxIndicesSelectedForFlip.add(maxElementIndex+1);
//Flip 0->endOfUnsortedArray
flip(arr, endOfUnsortedArray);
maxIndicesSelectedForFlip.add(endOfUnsortedArray+1);
}
return maxIndicesSelectedForFlip;
}
private void flip(int[] arr, int maxIndex) {
for (int i=0; i<=maxIndex/2; i++) {
int tmp = arr[i];
arr[i] = arr[maxIndex-i];
arr[maxIndex-i] = tmp;
}
}
}
</pre>
<p><b>Time Complexity</b>: O(n^2)</p><p><b>Space Complexity</b>: In-place sorting: O(1) </p><p><br /></p><p>Happy Coding! ;)</p>Chandni Vermahttp://www.blogger.com/profile/16416503906800854146noreply@blogger.com0tag:blogger.com,1999:blog-2576048997095865051.post-19093377286679596942021-01-09T12:49:00.005+05:302021-01-09T12:51:16.735+05:30LeetCode Medium: Design Circular Queue<p>Every now and then I come across a LeetCode problem that has test cases which contradict the problem statement. One such problem is <b>#622: Design Circular Queue</b>, a medium level problem on LeetCode.</p><p><br /></p><p><b>Problem Description</b>: <a href="https://leetcode.com/problems/design-circular-queue/">https://leetcode.com/problems/design-circular-queue/</a></p><p><b>Time Complexity</b>: O(1) across all methods - enqueue, dequeue, front, rear, isEmpty, isFull.</p><p><b>Design</b>:</p><p><br />
</p>
<pre>class MyCircularQueue {
int[] arr;
int front;
int rear;
int size;
public MyCircularQueue(int k) {
arr = new int[k];
front = rear = -1;
size = k;
}
public boolean enQueue(int value) {
if (isFull()) {
// queue is full
return false;
}
if (isEmpty()) {
front = rear = 0;
arr[front] = value;
} else {
rear = (rear+1)%size;
arr[rear] = value;
}
return true;
}
public boolean deQueue() {
if (isEmpty())
return false;
if (front == rear) {
front = rear = -1;
} else {
rear = (rear-1)%size;
}
return true;
}
public int Front() {
if (isEmpty())
return -1;
return arr[front];
}
public int Rear() {
if (isEmpty())
return -1;
return arr[rear];
}
public boolean isEmpty() {
if (front == rear && front == -1) {
// queue is empty
return true;
}
return false;
}
public boolean isFull() {
if (front == (rear+1)%size)
return true;
return false;
}
}
/**
* Your MyCircularQueue object will be instantiated and called as such:
* MyCircularQueue obj = new MyCircularQueue(k);
* boolean param_1 = obj.enQueue(value);
* boolean param_2 = obj.deQueue();
* int param_3 = obj.Front();
* int param_4 = obj.Rear();
* boolean param_5 = obj.isEmpty();
* boolean param_6 = obj.isFull();
*/
</pre>
<div>Failing test case:</div><div><br /></div><div><div class="css-n2wnd7-RowContainer e5i1odf0" style="-webkit-box-align: center; align-items: center; background-color: white; box-sizing: border-box; color: #455a64; display: flex; font-family: -apple-system, system-ui, "Segoe UI", "PingFang SC", "Hiragino Sans GB", "Microsoft YaHei", "Helvetica Neue", Helvetica, Arial, sans-serif, "Apple Color Emoji", "Segoe UI Emoji", "Segoe UI Symbol"; font-size: 14px; margin-bottom: 10px;"><div class="css-j7wj5p-Field e5i1odf1" style="box-sizing: border-box; flex: 0 0 90px;" width="90">Input</div><div class="css-i03q4h-ValueContainer e5i1odf3" style="background: rgb(250, 250, 250); border-radius: 3px; border: 1px solid rgb(238, 238, 238); box-sizing: border-box; display: flex; flex: 1 1 0%; overflow-x: auto;"><div class="css-1ubm0bb-Value e5i1odf2" style="box-sizing: border-box; cursor: pointer; font-family: Monaco, Menlo, "Ubuntu Mono", Consolas, source-code-pro, monospace; font-size: 12px; line-height: 18px; max-height: 47px; min-height: 32px; padding: 6px 10px; white-space: pre-wrap;">["MyCircularQueue","enQueue","enQueue","enQueue","enQueue","deQueue","deQueue","isEmpty","isEmpty","Rear","Rear","deQueue"]<br style="box-sizing: border-box;" />[[8],[3],[9],[5],[0],[],[],[],[],[],[],[]]<br style="box-sizing: border-box;" /></div></div></div><div class="css-n2wnd7-RowContainer e5i1odf0" style="-webkit-box-align: center; align-items: center; background-color: white; box-sizing: border-box; color: #455a64; display: flex; font-family: -apple-system, system-ui, "Segoe UI", "PingFang SC", "Hiragino Sans GB", "Microsoft YaHei", "Helvetica Neue", Helvetica, Arial, sans-serif, "Apple Color Emoji", "Segoe UI Emoji", "Segoe UI Symbol"; font-size: 14px; margin-bottom: 10px;"><div class="css-j7wj5p-Field e5i1odf1" style="box-sizing: border-box; flex: 0 0 90px;" width="90">Output</div><div class="css-i03q4h-ValueContainer e5i1odf3" style="background: rgb(250, 250, 250); border-radius: 3px; border: 1px solid rgb(238, 238, 238); box-sizing: border-box; display: flex; flex: 1 1 0%; overflow-x: auto;"><div class="css-1ubm0bb-Value e5i1odf2" style="box-sizing: border-box; cursor: pointer; font-family: Monaco, Menlo, "Ubuntu Mono", Consolas, source-code-pro, monospace; font-size: 12px; line-height: 18px; max-height: 47px; min-height: 32px; padding: 6px 10px; white-space: pre-wrap;">[null,true,true,true,true,true,true,false,false,9,9,true]<br style="box-sizing: border-box;" /></div></div></div><div class="css-n2wnd7-RowContainer e5i1odf0" style="-webkit-box-align: center; align-items: center; background-color: white; box-sizing: border-box; color: #455a64; display: flex; font-family: -apple-system, system-ui, "Segoe UI", "PingFang SC", "Hiragino Sans GB", "Microsoft YaHei", "Helvetica Neue", Helvetica, Arial, sans-serif, "Apple Color Emoji", "Segoe UI Emoji", "Segoe UI Symbol"; font-size: 14px; margin-bottom: 0px;"><div class="css-j7wj5p-Field e5i1odf1" style="box-sizing: border-box; flex: 0 0 90px;" width="90">Expected</div><div class="css-i03q4h-ValueContainer e5i1odf3" style="background: rgb(250, 250, 250); border-radius: 3px; border: 1px solid rgb(238, 238, 238); box-sizing: border-box; display: flex; flex: 1 1 0%; overflow-x: auto;"><div class="css-1ubm0bb-Value e5i1odf2" style="box-sizing: border-box; cursor: pointer; font-family: Monaco, Menlo, "Ubuntu Mono", Consolas, source-code-pro, monospace; font-size: 12px; line-height: 18px; max-height: 47px; min-height: 32px; padding: 6px 10px; white-space: pre-wrap;">[null,true,true,true,true,true,true,false,false,0,0,true]</div></div></div></div><div><br /></div><div>Dear @LeetCode please remove these erroneous test cases from the problem's test suite.</div><div><br /></div><div><br /></div><div>Happy Coding meanwhile!</div><div><br /></div>
Chandni Vermahttp://www.blogger.com/profile/16416503906800854146noreply@blogger.com0tag:blogger.com,1999:blog-2576048997095865051.post-77264998629465725382021-01-03T14:28:00.002+05:302021-01-03T14:28:36.156+05:30LeetCode Medium: Rotate Array<div>Hello all,</div><div><br /></div>Problem of the day: Rotate Array (rotate towards right, k times)<div>Link to Problem description: https://leetcode.com/problems/rotate-array/</div><div>Solution approach: multiple ways</div><div><br /></div><div><br /></div><div>Solution approach 1:</div><div>Brute force moving all elements by 1 position, k times. Time Complexity O(n*k). Not great! In-place, so space complexity O(1).</div><div><br /></div><div>Solution Approach 2:</div><div>Making a temporary copy(tmp) of k rightmost elements. Move all preceding elements towards right maintaining order, by k positions i.e. towards the rightmost end. Copy all tmp elements towards k spaces created at the leftmost end.<br />
<pre> class Solution {
public void rotate(int[] nums, int k) {
int n = nums.length;
if (n < 2)
return;
k = k % n;
int[] tmp = Arrays.copyOfRange(nums, n-k, n);
for (int i=n-k; i>=1; i--)
nums[i+k-1] = nums[i-1];
for (int i=tmp.length-1; i>=0; i--)
nums[i] = tmp[i];
}
}</pre></div><div><br /></div><div>Time Complexity: O(n)</div><div>Space Complexity: O(k)</div><div><br /></div><div><br /></div><div>Solution 3:</div><div>Using in-place reverse array custom method.</div><div><br /></div><div><pre>class Solution {
public void rotate(int[] nums, int k) {
int n = nums.length;
if (n < 2)
return;
k = k % n;
reverse(nums, 0, n-1-k);
reverse(nums, n-k, n-1);
reverse(nums, 0, n-1);
}
public void reverse(int[] arr, int st, int end) {
int mid = (end-st+1)%2==0 ? (end+st)/2+1 : (end+st)/2;
for (int i=st; i<mid; i++) { // < : don't reverse mid with itself on odd nElems
arr[i] = arr[i] + arr[end-(i-st)];
arr[end-(i-st)] = arr[i] - arr[end-(i-st)];
arr[i] = arr[i] - arr[end-(i-st)];
}
}
}</pre><pre><span style="font-family: Times; white-space: normal;">Time Complexity: O(n)</span></pre><pre><span style="font-family: Times; white-space: normal;">Space: In-place; O(1).</span></pre></div><div><br />Happy Coding!<br /><div style="text-align: center;"><a data-patreon-widget-type="become-patron-button" href="https://www.patreon.com/bePatron?u=41494657">Become a Patron!</a><script async="" src="https://c6.patreon.com/becomePatronButton.bundle.js"></script></div>
</div><div><br /></div><div><br /></div><div><br /></div><div><br /></div>Chandni Vermahttp://www.blogger.com/profile/16416503906800854146noreply@blogger.com0tag:blogger.com,1999:blog-2576048997095865051.post-81506931362064505082020-12-30T21:18:00.002+05:302020-12-30T21:18:11.632+05:30LeetCode Easy(medium-ish): Subtree of Another TreeHello Peeps,<div><br /></div><div>We're getting back in touch with problem solving after a long-long time. I was _really really_ busy with family functions in this break.
<div><br /></div><div>Yesterday, I solved this LeetCode problem <b>Subtree of Another Tree</b> categorised as easy on LeetCode. I would say medium would have been a more appropriate categorisation of this recursively solvable problem.</div></div><div><br /></div><div><br /></div><div><b>Problem link</b>: https://leetcode.com/problems/subtree-of-another-tree/</div><div><b>Solution Approach</b>: Recursion</div><div><b>Time Complexity</b>: O(n) where n is the number of nodes in the tree s.</div><div><b>Space Complexity</b>: O(h) where h is the height of the tree s.</div><div><br /></div><div><br /></div><div><b>Solution</b>:</div><div><br /></div>
<pre>/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public boolean isSubtree(TreeNode s, TreeNode t) {
//Main logic
boolean matchFound = false;
//Base condition
if (s == null && t == null)
return true;
if ((s!=null && t==null) || (s==null && t!=null))
return false;
if (s.val == t.val)
matchFound = matches (s, t);
if (!matchFound) {
matchFound = isSubtree(s.left, t);
}
if (!matchFound) {
matchFound = isSubtree(s.right, t);
}
return matchFound;
}
private boolean matches (TreeNode s, TreeNode t) {
if (s==null && t==null)
return true;
if ((s!=null && t==null) || (s==null && t!=null))
return false;
if (s.val != t.val)
return false;
return matches(s.left, t.left) && matches(s.right, t.right);
}
}
</pre>
<div>That's all for now!</div><div><br /></div><div>Happy Coding!!</div>Chandni Vermahttp://www.blogger.com/profile/16416503906800854146noreply@blogger.com0tag:blogger.com,1999:blog-2576048997095865051.post-966261777370054322020-09-22T17:18:00.009+05:302020-09-22T17:36:39.323+05:30LeetCode Medium: Maximum Number of Vowels in a Substring of Given Length<div>Hello All,</div>
<div> </div>
<div>Today’s coding problem is a Medium level LeetCode problem. <strong>Problem #1456: Maximum Number of Vowels in a Substring of Given Length</strong></div>
<div><strong>Link to Problem</strong>: https://leetcode.com/problems/maximum-number-of-vowels-in-a-substring-of-given-length/</div>
<div><strong>Problem Approach</strong>: Sliding Window</div>
<div><strong>Time Complexity</strong>: O(n) where n is the number of characters in the input string.</div><div><b>Space Complexity</b>: O(1) extra space</div>
<div> </div>
<div> </div>
<div>Accepted Java solution using Sliding Window:</div>
<div> </div>
<div>
<pre>class Solution {
public int maxVowels(String s, int k) {
if (s==null || s.length()<k) {
return 0;
}
int maxVowelCnt = 0;
int currentVowelCnt = 0;
for (int i=0; i<=s.length()-k; i++) {
if (i==0) { //1st window only
for (int j=i; j<i+k; j++) {
if (isVowel(s.charAt(j)))
currentVowelCnt++;
}
} else { //remaining windows
if(isVowel(s.charAt(i+k-1)))
currentVowelCnt++;
if(isVowel(s.charAt(i-1)))
currentVowelCnt--;
}
maxVowelCnt = Math.max(maxVowelCnt, currentVowelCnt);
}
return maxVowelCnt;
}
private boolean isVowel(char c) {
return c=='a' || c=='e' || c=='i' || c=='o' || c=='u' ;
}
}
</pre>
</div>
<div> </div>
<div><strong>Video Explanation</strong>:</div>
<div> </div>
<div><iframe allowfullscreen="allowfullscreen" class="embed-responsive-item" frameborder="0" height="385" src="https://www.youtube.com/embed/3D29psQzBjI" width="640"> </iframe></div>
<div> </div>
<div> </div>
<div>Share your thoughts!</div>
<div>Happy Coding!</div>
<div> </div>
<div> </div>
<div style="text-align: center;"><a data-patreon-widget-type="become-patron-button" href="https://www.patreon.com/bePatron?u=41494657">Become a Patron!</a><script async="" src="https://c6.patreon.com/becomePatronButton.bundle.js"></script></div>
<div> </div>
Chandni Vermahttp://www.blogger.com/profile/16416503906800854146noreply@blogger.com0tag:blogger.com,1999:blog-2576048997095865051.post-91670302998804250542020-09-07T03:18:00.007+05:302020-09-08T05:30:26.446+05:30LeetCode Hard: Find Median from Data Stream<div><b>LeetCode Problem #295: Find Median from Data Stream</b><br /><b>Link to Problem Description</b>: <a href="https://leetcode.com/problems/find-median-from-data-stream/">https://leetcode.com/problems/find-median-from-data-stream/ </a><br /><b>Category</b>: Applications of Binary Heaps (or Priority Queues) <br /><b>Solution Approach</b>: Divide elements into 2 mutually-balanced Priority Queues - one having elements smaller than the middle element(s), one having larger. <br /><b>Time Complexity of Approach</b>:</div>
<ul>
<li>O(lg n) for insertion where n = number of elements seen so far.</li>
<li>O(n) for finding the median of elements seen so far. Space Complexity: O(n) </li>
</ul>
<div> </div>
<div>This LeetCode Hard Problem is a pretty neat application of Binary Heaps, which are readily usable as PriorityQueues in Java.</div>
<div>I have discussed the possible approaches to dolve the problem in the adjoining youtube video link and in this blog post I present 2 solutions for the Twin-heap based solution:</div>
<div> </div>
<div><b><u>Approach #1</u></b>: Using PriorityQueue Collection Class of Java Collections Framework</div>
<div> </div>
<div> </div>
<pre>class MedianFinder {
PriorityQueue lesser;
PriorityQueue greater;
public MedianFinder() {
lesser = new PriorityQueue<>(10, (o1, o2)->o2-o1);
greater = new PriorityQueue<>();
}
public void addNum(int num) { // O(lg n)
if (lesser.size() == 0 || num < lesser.peek()) {
lesser.add(num);
} else {
greater.add(num);
}
//Balance the heaps
if (Math.abs(lesser.size() - greater.size()) <= 1)
return;
if (lesser.size() < greater.size())
lesser.add(greater.poll());
else
greater.add(lesser.poll());
}
public double findMedian() { // O(1)
if (lesser.size() == greater.size())
return ((double)lesser.peek() + greater.peek())/2;
if (lesser.size() > greater.size())
return lesser.peek();
return greater.peek();
}
}
/**
* Your MedianFinder object will be instantiated and called as such:
* MedianFinder obj = new MedianFinder();
* obj.addNum(num);
* double param_2 = obj.findMedian();
*/
</pre>
<div> </div>
<div> </div>
<div><b><u>Approach 2</u></b>: Without using pre-build classes of Java - To test if you can code a Binary Heap data structure from scratch!</div>
<div> </div>
<div> </div>
<pre>class MyPriorityQueue> {
private ArrayList q;
private Comparator comp;
public MyPriorityQueue(int initialCapacity, Comparator cmp) {
q = new ArrayList(initialCapacity);
comp = cmp;
}
public MyPriorityQueue() {
q = new ArrayList(10);
comp = (o1, o2)->o1.compareTo(o2);
}
private int parent(int idx) {
int pos = idx+1;
return pos/2 - 1;
}
private int left(int idx) {
int pos = idx+1;
return (pos*2) -1;
}
private int right(int idx) {
int pos = idx+1;
return (pos*2+1) -1;
}
public void add (E e) {
q.add(e);
//bubble-up if necessary
int currentIdx = q.size()-1;
int parentIdx = parent(currentIdx);
while (parentIdx >= 0 && comp.compare(e, q.get(parentIdx)) < 0) {
q.set(currentIdx, q.get(parentIdx));
q.set(parentIdx, e);
currentIdx = parentIdx;
parentIdx = parent(currentIdx);
}
}
public int size() {
return q.size();
}
public E peek() {
if (q.isEmpty())
return null;
return q.get(0);
}
public void remove() {
if (q.isEmpty())
return;
q.set(0, q.get(q.size()-1));
q.remove(q.size()-1);
minHeapify(0);
}
private void minHeapify(int i) {
if (i >= q.size())
return;
int leastValIdx = i;
if (left(i) < q.size() && comp.compare(q.get(leastValIdx), q.get(left(i))) > 0)
leastValIdx = left(i);
if (right(i) < q.size() && comp.compare(q.get(leastValIdx), q.get(right(i))) > 0)
leastValIdx = right(i);
if (leastValIdx != i) {
E tmp = q.get(leastValIdx);
q.set(leastValIdx, q.get(i));
q.set(i, tmp);
minHeapify(leastValIdx);
}
}
}
class MedianFinder {
/** initialize your data structure here. */
MyPriorityQueue lesserElementsMaxHeap;
MyPriorityQueue greaterElementsMinHeap;
public MedianFinder() {
lesserElementsMaxHeap = new MyPriorityQueue<>(10, (o1, o2)->o2-o1);
greaterElementsMinHeap = new MyPriorityQueue<>(); //minHeap by default
}
public void addNum(int num) {
Integer lesserMax = lesserElementsMaxHeap.peek();
if (lesserMax == null || lesserMax>num)
lesserElementsMaxHeap.add(num);
else
greaterElementsMinHeap.add(num);
//ensure balanced heaps
if (Math.abs(lesserElementsMaxHeap.size() - greaterElementsMinHeap.size()) <= 1)
return;
if (lesserElementsMaxHeap.size() > greaterElementsMinHeap.size()) {
lesserMax = lesserElementsMaxHeap.peek();
greaterElementsMinHeap.add(lesserMax);
lesserElementsMaxHeap.remove();
} else {
Integer greaterMin = greaterElementsMinHeap.peek();
lesserElementsMaxHeap.add(greaterMin);
greaterElementsMinHeap.remove();
}
}
public double findMedian() {
if (lesserElementsMaxHeap.size() == greaterElementsMinHeap.size())
return ((double)lesserElementsMaxHeap.peek() + greaterElementsMinHeap.peek())/2;
if (lesserElementsMaxHeap.size() > greaterElementsMinHeap.size())
return lesserElementsMaxHeap.peek();
else
return greaterElementsMinHeap.peek();
}
}
/**
* Your MedianFinder object will be instantiated and called as such:
* MedianFinder obj = new MedianFinder();
* obj.addNum(num);
* double param_2 = obj.findMedian();
*/
</pre>
<div> </div>
<div> </div>
<div> Video explanation for the approach:</div>
<div> </div>
<div><iframe allowfullscreen="allowfullscreen" height="314" src="//www.youtube.com/embed/MtKr5wOdsvQ" width="560"></iframe></div>
<div> </div>
<div>Share your thoughts in comments!</div>
<div> </div>
<div><3</div><div><br /></div><div><br /></div>
<div style="text-align: center;"><a data-patreon-widget-type="become-patron-button" href="https://www.patreon.com/bePatron?u=41494657">Become a Patron!</a><script async="" src="https://c6.patreon.com/becomePatronButton.bundle.js"></script></div>
<div> </div>Chandni Vermahttp://www.blogger.com/profile/16416503906800854146noreply@blogger.com0tag:blogger.com,1999:blog-2576048997095865051.post-34214893804645132002020-09-01T22:50:00.000+05:302020-09-01T22:50:32.477+05:30LeetCode Medium: Fruit Into Baskets<p>Y'day I solved LeetCode medium level problem: <strong>#904: Fruit Into Baskets</strong> ()</p>
<p>A quick heuristics-based solution with O(n) time-complexity in Java, which has been accepted by the LeetCode judge, is :</p>
<div>
<pre>
class Solution {
public int totalFruit(int[] tree) {
Integer[] uniqueTreeTypesIdx = new Integer[2];
uniqueTreeTypesIdx[0] = 0;
int start = 0;
int lastConsecutiveStretchStart = 0;
int maxStretchLength = 1;
int i = 1; //index counter
for (i=1; i<tree.length; i++) {
if (tree[i] != tree[uniqueTreeTypesIdx[0]]) {
if (uniqueTreeTypesIdx[1] == null) {
uniqueTreeTypesIdx[1] = i;
lastConsecutiveStretchStart = i;
} else if (tree[i] != tree[uniqueTreeTypesIdx[1]]) {
maxStretchLength = Math.max (maxStretchLength, i-1-start+1);
start = lastConsecutiveStretchStart;
uniqueTreeTypesIdx[0] = lastConsecutiveStretchStart;
uniqueTreeTypesIdx[1] = i;
lastConsecutiveStretchStart = i;
} else { //tree[i] != tree[uniqueTreeTypesIdx[0]] && tree[i] == tree[uniqueTreeTypesIdx[1]]
if (tree[i] == tree[lastConsecutiveStretchStart])
;
else
lastConsecutiveStretchStart = i;
}
} else {
if (tree[i] == tree[lastConsecutiveStretchStart])
;
else
lastConsecutiveStretchStart = i;
}
}
maxStretchLength = Math.max (maxStretchLength, i-1-start+1);
return maxStretchLength;
}
}
</pre>
<br /><br />I would like to re-visit it in near-times, to devise a more elegant and intuitive solution approach, but this is it for now!<br /><br />Stay tuned for the next one!<br /><br /><br /></div>
<div align="center">
<a href="https://www.patreon.com/bePatron?u=41494657" data-patreon-widget-type="become-patron-button">Become a Patron!</a><script async src="https://c6.patreon.com/becomePatronButton.bundle.js"></script>
</div>Chandni Vermahttp://www.blogger.com/profile/16416503906800854146noreply@blogger.com0tag:blogger.com,1999:blog-2576048997095865051.post-24388020309973856722020-08-31T03:37:00.004+05:302020-08-31T03:44:07.766+05:30Announcement! Become our Patron!<div> </div>
<div>Our very own Let’s Code_ community initiative is now having a Patreon Landing page! Just another way for you to say thanks!</div>
<div> </div>
<div>Go: </div>
<div> </div>
<div>
<a data-patreon-widget-type="become-patron-button" href="https://www.patreon.com/bePatron?u=41494657">Become our Patron!</a><script async="" src="https://c6.patreon.com/becomePatronButton.bundle.js"></script>
</div>Chandni Vermahttp://www.blogger.com/profile/16416503906800854146noreply@blogger.com0