J Coder

1. Trapping Rain Water
Given an array arr[] of N non-negative integers representing the height of blocks. If width of each block is 1, compute how much water can be trapped between the blocks during the rainy season.


Example 1:

Input:
N = 6
arr[] = {3,0,0,2,0,4}
Output: 10
Explanation:



Example 2:

Input:
N = 4
arr[] = {7,4,0,9}
Output: 10
Explanation: Water trapped by above
block of height 4 is 3 units and above
block of height 0 is 7 units. So, the
total unit of water trapped is 10 units.


Example 3:

Input:
N = 3
arr[] = {6,9,9}
Output: 0
Explanation: No water will be trapped.

Time complexity O(n)
Space complexity O(n)

2. Kandane's Algorithm
Given an array arr of N integers. Find the contiguous sub-array with maximum sum.



Example 1:

Input:
N = 5
arr[] = {1,2,3,-2,5}
Output: 9
Explanation: Max subarray sum is 9
of elements (1, 2, 3, -2, 5) which
is a contiguous subarray.


Example 2:

Input:
N = 4
arr[] = {-1,-2,-3,-4}
Output: -1
Explanation: Max subarray sum is -1
of element (-1)

Time complexity O(n)
space complexity O(1)

3. Merge without Extra space
Given two sorted arrays arr1[] and arr2[] of sizes N and M in non-decreasing order. Merge them in sorted order without using any extra space. Modify arr1 so that it contains the first N elements and modify arr2 so that it contains the last M elements.


Example 1:

Input:
N = 4, arr1[] = [1 3 5 7]
M = 5, arr2[] = [0 2 6 8 9]
Output:
arr1[] = [0 1 2 3]
arr2[] = [5 6 7 8 9]
Explanation: After merging the two
non-decreasing arrays, we get,
0 1 2 3 5 6 7 8 9.


Example 2:

Input:
N = 2, arr1[] = [10, 12]
M = 3, arr2[] = [5 18 20]
Output:
arr1[] = [5 10]
arr2[] = [12 18 20]
Explanation: After merging two sorted arrays
we get 5 10 12 18 20

Expected Time Complexity: O((n+m) log(n+m))
Expected Space complexity: O(1)

Above the problem solving Time limit 2 days

Every one Back to the code and create new things