Leetcode - 1D array

There are few interesting algorithms to approach 1D array problems. First, Kadane’s algorithm. This is useful to find local max in 1D array. Second, two pointer technique. One pointer starts from the beginning of 1D array and another pointer starts from the end of 1D array. The one pointer is adjusted each iteration, when condition does not meet. Third, collect data from scanning the 1D array from left to right and collect data from scanning the 1D array from right to left. After collecting data, analyze both data to find the solution. Fourth, rotate array. It can be done by three steps; reverse array [0, n], reverse subarray [0, k-1], reverse subarray[k, n].

* Kadane’s algorithm can be implemented with repeating three steps.

1. Check the condition and if condition meets, go to step 2, otherwise, reset the accumulator variable and iterate to next element.

2. Accumulate(i.e. add, multiply)

3. Update the result if accumulator is greater than current max accumulator and iterate to next element

Example of Kadane’s algorithm.

53. Maximum Subarray

Note: To accumulate the sum, the accumulator variable should be reset as 0. The condition is that new element is less than zero.

152. Maximum Product Subarray

Note: To accumulate the product, the accumulator variable should be reset as 1. The condition is that new element is not equal to zero. Two negative value’s product can be maximum product. It requires to maximum product candidate while scanning from left to right and right to left, then, compare between two candidates. It is a bit more complicated than maximum sum problem.

* Example of Two pointers technique.

167. Two Sum II - Input Array Is Sorted

Find sum of two elements = target, in sorted array. Set head pointer at array position 0 and rear pointer at array position n-1.

If sum is greater than target, decrease rear pointer array position.

If sum is less than target, increase head pointer array position.

If sum is equal to target, return two values.

This process repeats where head pointer array position < rear pointer array position.

11. Container With Most Water

Each value contains the height. The width is a distance between two pointers. The amount of water is calculated by MIN(height[start], height[end]) * (end - start). Set start pointer at array position 0 and end pointer at array position n-1.

Calculate the area and update the result if new area is greater than current max area.

If height[start] > height[end], decrease end pointer array position.

If height[start] < height[end], increase start pointer array position.

This process repeats where start pointer array position < end pointer array position. Then, return current max area.

* Collecting data two times(each time with different moving direction) and analyze them

152. Maximum Product Subarray

This problem was already introduced above with Kadane’s algorithm. But it requires to collect data two times. First product candidate is generated while moving from start to end. Second product candidate is generated while moving from end to start. The answer is whichever bigger one.

42. Trapping Rain Water

The amount of water is calculated by MIN(lef_max[i], right_max[i]) - height[i] at array i position. left_max array can be collected while moving from start to end. It is the collection of MAX(left_max[i-1], height[i]). right_max array can be collected while moving from end to start. It is the collection of MAX(right_max[i+1], height[i]). The answer is accumulated of amount of water in array.

238. Product of Array Except Self

The product of array except self can be calculated by left_product[i]*right_product[i]. left_product is accumulated product on i’s left hand side. It is collected while i is moving from start to end. right_product is accumulated product on i’s right hand side. It is collected while i is moving from end to start. i as itself is excluded in product. Again, this is product as accumulator and the value should be reset as 1.

* Rotate array

189. Rotate Array

Note: given number k can be greater than array size. However, the pattern is repeated every kth.

void rotate(vector<int>& nums, int k) {
        k = k % nums.size();                //pattern is repeated every kth

        reverse(nums, 0, nums.size()-1);    //reverse whole array[0, n-1]
        reverse(nums, 0, k-1);              //reverse subarray[0, k-1]
        reverse(nums, k, nums.size()-1);    //reverse subarray[k, n-1]
}