Showing Posts From

Code

[Neetcode] Trapping Rain Water

[Neetcode] Trapping Rain Water

This is one of those problems where the formula is simple, but the trick is figuring out how much context each index needs. For any bar at index i, the water on top of it is: min(max wall on left, max wall on right) - height[i]If either side does not have a higher wall, the contribution becomes 0. Problem Given an array height, each value represents the height of a bar. We need to return how much water can be trapped after raining. Example: height = [0,2,0,3,1,0,1,3,2,1] answer = 9Approach 1 - Brute force For every index, scan the full left side and full right side to find the tallest wall on both sides. Then add the water contributed by the current index.This works because every index is handled independently, but it repeats a lot of work. For each bar we are scanning the array again. class Solution { public int trap(int[] height) { int n = height.length; int res = 0; for (int i = 0; i < n; i++) { int leftWall = i; int rightWall = i; for (int k = i; k >= 0; k--) { if (height[k] >= height[leftWall]) { leftWall = k; } } for (int k = i; k < n; k++) { if (height[k] > height[rightWall]) { rightWall = k; } } res += Math.min(height[leftWall], height[rightWall]) - height[i]; } return res; } }Time complexity: O(n^2) Space complexity: O(1) Approach 2 - Prefix and suffix walls The repeated work in brute force is finding the same left and right walls again and again. We can precompute them. leftWalls[i] stores the highest wall from 0 to i. rightWalls[i] stores the highest wall from i to n - 1.Once these two arrays are ready, the water at every index can be calculated in one pass. class Solution { public int trap(int[] height) { int n = height.length; int res = 0; int[] leftWalls = new int[n]; int[] rightWalls = new int[n]; leftWalls[0] = height[0]; rightWalls[n - 1] = height[n - 1]; for (int i = 1; i < n; i++) { leftWalls[i] = Math.max(leftWalls[i - 1], height[i]); } for (int i = n - 2; i >= 0; i--) { rightWalls[i] = Math.max(rightWalls[i + 1], height[i]); } for (int i = 0; i < n; i++) { res += Math.min(leftWalls[i], rightWalls[i]) - height[i]; } return res; } }Time complexity: O(n) Space complexity: O(n) Approach 3 - Two pointers We can avoid the extra arrays by keeping two pointers, one from the left and one from the right. The useful observation is that water is limited by the smaller wall. If leftMax < rightMax, then the left side can be settled because there is already a right wall tall enough to support it. Similarly, if rightMax < leftMax, the right side can be settled.class Solution { public int trap(int[] height) { int n = height.length; int res = 0; int l = 0; int r = n - 1; int leftMax = 0; int rightMax = 0; while (l < r) { leftMax = Math.max(leftMax, height[l]); rightMax = Math.max(rightMax, height[r]); if (leftMax > rightMax) { res += rightMax - height[r]; r--; } else { res += leftMax - height[l]; l++; } } return res; } }Time complexity: O(n) Space complexity: O(1) Takeaway The core idea is that each index only cares about the smaller wall between its best left wall and best right wall. Brute force finds those walls by scanning again and again. Prefix/suffix arrays remember them. Two pointers settle the side whose limit is already known.

[Neetcode] Two Integer Sum II

[Neetcode] Two Integer Sum II

Basically you have a sorted array of integers and you need to find the index i, j which will sum up to a target. Approach 1 - Bruteforce The simplest solution is loop through all the integers combinations and find the indices. This is basically looping twice each number -> O(n^2), not very good.We can make the above one more optimal by starting the second loop after the current index. This will reduce our iterations by half, making it n(n-1)/2. This is also O(n^2).We can add one more optimization by pruning as soon as second loop sums to a number greater than target. As the array is sorted, any number after the number which resulted in sum greater than target will also result in a sum greater than the target. Worst case this will also be O(n^2).But we got a clue here, the clue is traversing in reverse order if we get a sum less than target then we no longer need to search a number before the index. Basically, if sum of 1st and last is less than the target, then good guess would be check the 2nd number and last number. And if 1st and lat is greater than the target, then a good guess would be check 1st and 2nd last. And so on. Approach 2 - 2 pointers Take 2 pointers, l at the start of the array and r at the last of the array. If the sum of numbers at the pointers is greater than target then check r-1 and if it is less than the target then check l+1. This will give us a solution which is O(n) as none of the numbers are being passed more than once.

Vibe coded my blogging app

Vibe coded my blogging app

Just another late-nighter and the power of AI. I was looking for a VPS to host my blog, basically my admin page, so that I can access it anywhere and start writing my blogs wherever I can, mainly from my mobile. Then, an idea struck my head: why not get an app? Basically, I have the Git token, so I thought of getting an app that can access my GitHub and get this exact repo cloned on my system. And, like I always write blogs on my laptop, I can just use the same technologies to write blogs on my mobile. Then, I sat on my laptop, discussed things with Codex, and we came up with a plan to write an app that can connect to my GitHub, understand my blogging codebase, and create an app around that, matching my workflow. I can see my old posts, update, add, create whatever I want, and just write my blogs from mobile. The GitHub connector page This is where you just create a GitHub app and connect it to your app. Once connected, you will never need to do it again.The old blog posts View/edit your old blog posts and keep things updated.The writer page Write new articles/blogs just from the app and push it to GitHub. Once pushed the same CICD pipeline will make it go live. Easy Peasy.

Just started neetcode blind 150

Just started neetcode blind 150

Just started Neetcode blind 150. This time I'm using java as my tool. Navigating through same challenges and learning more. To be honest, coding on job and coding on coding platform are very different. On job, you use HashMaps and you are mostly done. And there are exceptions when you use DP or Trees. My case, I think I have used mostly all the general data structures and some advanced ones too. But anyways, back to coding and building hand memory again.

Make String a Subsequence Using Cyclic Increments

This is the LeetCode problem number 2825. Cyclic increment This is when you increase an entity by an amount and when you reach the end you circle back to start and continue the count. If a is increased cyclicly by 1, we will get b. If a is increased cyclicly by 2, we will get c. But if z is increased cyclicly by 1, we get a. By 2 we will get b. String increaseCyclic (String str, int index) { char ch = str.charAt(index); char newch = (char) ((ch - 'a' + 1) % 26 + 'a'); return str.substring(0, index) + newChar + str.substring(index + 1); }Subsequence String str1 is said to contain the subsequence of str2 if we can delete some characters from str1 to get str2. During this deletion we are not allowed to disturb the relative order of chars in the str1. A code to check if str1 contains subsequence str2. We can iterate over all the characters of str1 sequencely and check if all the letters are there as in str2. boolean isSubsequence(String str1, String str2) { int p1 = 0; int p2 = 0; while (p1 < str1.length() && p2 < str2.length()) { if (str1.charAt(p1) == str2.charAt(p2)) { p2++; } p1++; } return p2 == str2.length(); }Solution The problem asks us that we are allowed to cyclic increase any number of chars in str1. And check whether we are able to say str1 will contain a subsequence of str2. We can solve this problem by just merging both the problems. Instead of checking just the characters equality, we can add an additional check on character of str1 after increasig it cyclicly. public boolean canMakeSubsequence(String str1, String str2) { int p1 = 0; int p2 = 0; while (p1 < str1.length() && p2 < str2.length()) { char cyclicCh = (char) ((str1.charAt(p1) - 'a' + 1) % 26 + 'a'); if (str1.charAt(p1) == str2.charAt(p2) || cyclicCh == str2.charAt(p2)) { p2++; } p1++; } return p2 == str2.length(); }