Showing Posts From

Neetcode

[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.

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.