Trapping Rain Water

Problem:

Given n non-negative integers representing an elevation map(block) where the width of each bar is 1, compute how much water it can trap after raining.

Example:

Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]

Output: 6

Explanation: The above elevation map (black section) is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.

Approach:

This Problem is almost similar to this problem, so we can assume that we can solve this problem using the two-pointers method. But before move on to the two-pointers method, let's try to solve this problem using the forward and backward array methods. 

Previously we have solved another forward and backward array method, named "Maximum Subarray Sum with One Deletion". 

Now, let's try to visualize the problem.

We have to calculate the maximum traping water area, that would be,
    area = Height * Width

=>area = min(left_block_height, right_block_height) - current_height * 1

Width 1, that is given.

Now, why is this happening!

We have to consider every single position.

Suppose we are at position 'x' , if x-1 block is equal to or smaller than 'x' block, then we can't trap water at 'x' position. The same case at x+1 right block hold. Now, suppose the left block is the bigger and the right block, then we can't make an area like (bigger_block - current_block), because from right block water will be overflowed.

Now, How can we calculate the left max and the right max! simple, we will consider two arrays, named Forward array, and another one is a backward array.

Suppose, in 'x' position value of Forward array give a max height consider from 0th index to current index, Backward array will be same but from right.

Complexity, Time Complexity O(n), and Space Complexity O(n), because Forward and backward arrays taking extra memory.

See the code for a better understanding,

See, we illustrate already, if n < 3 then its not possible to trap any water into this, otherwise we have to calculate.

Sorted block also not possible, but we don't need to consider this one.

Then, we are taking only positive height.

Container With Most Water

Problem:

Given n non-negative integers a1, a2, ..., an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i are at (i, ai) and (i, 0). Find two lines, which, together with the x-axis forms a container, such that the container contains the most water.

Notice, that you may not slant the container.

Example,

Input: height = [1,8,6,2,5,4,8,3,7]

Output: 49

Explanation: The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49. 

Approach:

The first thing is that how can we calculate the area, which would be height*width. First, let's try to visualize,

We need to calculate the maximum area,One thing is clear that,

    area = height*width

=>area = min(height[left], height[right]) * (right-left)

Yes, you get right, this problem can be solved using the two-pointer method.

Putting the left pointer in the left and right pointer in the rightmost position, we will calculate the area. After checking which side is greater-smaller, we can move our pointer. That's all we need to do about this problem.

See the code for a better understanding.

Longest Substring Without Repeating Characters

Problem:

Given a string, find the length of the longest substring without repeating characters.

Examples:

Given"abcabcbb", the answer is"abc", which the length is 3.

Given"bbbbb", the answer is"b", with the length of 1.

Given"pwwkew", the answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

Constraints:

0 <= s.length() <= 5 * 10^4

Approach:

This problem can be solved using the "Two Pointers" method. Now the question is how can we move our pointers. We have to think a little bit, we can't sort our string or we can't take two pointers from 2 sides (left and right).

See, we can start our both pointers from starting position, every time we will increase one pointer, then if we met the current character before, then another pointer will be updated by the previous position of the current character. Okay, let's try to visualize,

Every time we will increase the right pointer, and at the same time, we will update our maximum length by (right - left + 1) and we will mark the current character position, if we see we have already met this character before, then simply we'll update left pointer by,

left = previous position + 1.
See the Code for a better understanding.

Time Complexity: O(n)

Space Complexity: O(1)

4Sum equal Target

Problem:

Given an array nums of n integers, return an array of all the unique quadruplets [nums[a], nums[b], nums[c], nums[d]] such that:

0 <= a, b, c, d < n

a, b, c, and d are distinct.

nums[a] + nums[b] + nums[c] + nums[d] == target

You may return the answer in any order.

Constraints:

1 <= nums.length <= 200

-109 <= nums[i] <= 109

-109 <= target <= 109

Example,

Input: nums = [1,0,-1,0,-2,2], target = 0

Output: [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

Input: nums = [2,2,2,2,2], target = 8

Output: [[2,2,2,2]], there are three quadruplets possible, but we have to print unique quadruplets.

Approach:

Again this problem is similar to previous all 3Sum problems, This problem also can be solved using the "Two Pointers" method.

let's try to visualize,

We saw that constraints are very low nearly 200, but we can't solve this problem in  O(n^4) approach, but we can solve this problem easily in O(n^3) approach. Initially, we target the first sum of two values,

then using the two pointers we will search for another sum of two values. Thats how we can solve this problem, simply after checking our current target we can move our pointers. See the code for a better understanding.

Here, we have to handle another case, since we have to print unique quadruplets, so we can use a set vector for using all quadruplets, then simply we can push it to a 2D vector.

3Sum Smaller

Problem:

Given an array of n integers nums and a target, find the number of index triplets i, j, k with 0 <= i < j < k < n that satisfy the condition

nums[i] + nums[j] + nums[k] < target.

For example, given nums = [-2, 0, 1, 3], and target = 2.Return 2. Because there are two triplets which sums are less than 2:

[-2, 0, 1], [-2, 0, 3]

Approach:
Again this problem is similar to the previous 3Sum and 3Sum Closest problems. This problem also can be solved using the Two pointers method. Let's illustrate,

Now how can we move our pointers right? see, if the current sum is less than the target that means from right pointer to left pointer all will be included in our answer because they are all smaller than the target because they are already in sorted order. So if the current sum is smaller than the target then we will move our left pointer forward otherwise we will decrease the right pointer. See the code for a better understanding.

3Sum equal Zero

Problem:

Given an integer array nums, return all the triplets [ nums[i], nums[j], nums[k] ] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

Notice that the solution set must not contain duplicate triplets.

Example, nums = [-1,0,1,2,-1,-4], Output: [[-1,-1,2],[-1,0,1]]

Approach:

This Problem is similar to this problem, again we will solve this problem using the "Two Pointers" method. Just simply we will avoid the duplicates indexes.

Simple Code:

3Sum Closest

Problem;
Given an array of n integers and an integer target, find three integers in the array such that the sum is closest to the target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

Example, [-1, 2, 1, -4], target =  1, the sum should be 2, we choose (-1, 2, 1) sum is 2

Remember you have to
choose 3 integers, it's not required to they should be contiguous.

Approach:

We can solve this problem using the "Two pointers" method. let's illustrate,

Here we tried to visualize two pointers method. While Calculating results we have to increase the left index or decrease the right index, simply we can do this by checking the case. When we got our answer, simply we will break the loop and will return our answer. Try to code your own, if you can't check the code given below.