Happy Hour Wednesdays: Arrays Part II

As with our first post, this post continues to review the recently concluded #HappyHourWednesdays interview questions of arrays.
The last two array questions are as follows:

Product of Array Except Self
This challenge from LeetCode is as follows:

Given an array nums of n integers where n > 1,  return an array output
such that output[i] is equal to the product of all the elements of nums
except nums[i].
It's guaranteed that the product of the elements of any prefix or suffix
of the array (including the whole array) fits in a 32 bit integer.
Note: Please solve it without division and in O(n).
Could you solve it with constant space complexity? (The output array does
not count as extra space for the purpose of space complexity analysis.)

`` This challenge has a very simple solution using division - find the product of all the elements in the given array, then for each of the elements of the array, divide the product by x to find the product of array except self. However, the challenge explicitly forbids us from using division and therefore another approach is needed.

Another solution will be to find the product of all the elements before the given index and multiply it by the product of all the elements that occur after the given index.
This solution can be written as follows:

using namespace std;
vector<int> productExceptSelf(vector<int>& nums) {
    int size = nums.size();
    vector<int> left(size, 1);
    vector<int> right(size, 1);
    vector<int> result(size, 0);

    for (auto i = 1; i < size; i++) {
        left[i] = left[i - 1] * nums[i - 1];
    }

    for (auto i = size - 2; i >= 0; i--) {
        right[i] = nums[i + 1] * right[i + 1];
    }

    for (auto i = 0; i < size; i++) {
        result[i] = left[i] * right[i];
    }

    return result;
}

This solution iterates over the two parts of the array, and multiplies the results to produce the solution.
This algorithm runs in O(n) time where n is the size of the input array and has O(n) space complexity used by the three new arrays we’re using to keep track of the left, right and final elements.

Container with Most Water
This challenge is also from LeetCode and is as follows:
```
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 the line i is 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.
```
This challenge is looking for the maximum area that can be formed between the vertical lines using the shorter line as length and the distance between the lines as the width of the rectangle. As with most of the array questions, this challenge can be solved using brute force by iterating over the areas of every possible pair of the lines and picking the maximum area out of those. However this is not the most efficient solution as it will produce an algorithm with a runtime of (O^n2) which means that the solution will take longer for larger inputs.

To optimize the solution, we’ll consider that the area is always limited by the height of the shorter line as the maximum height the water can be at will always be the height of the shorter line. Further more, the area produced will increase as the lines grow farther from each other.
With this in mind, we can design a solution that works with this constraints using two pointers. One of these pointers will start at the beginning while the other one will start at the end of the array holding the lengths. These two pointers will then be used to iterate over the array as they start from different ends of the array. In each loop of the iteration, we’ll keep the maximum area found, updating it with the current area if it is larger than what was previously stored. At the end of each loop we’ll advance the pointer which points at the shorter line forward.
This solution can be written as follows in C++:
```
using namespace std;
int maxArea(vector<int>& height) {
    auto size = height.size();
    int first = 0;
    int last = size - 1;
    int max = 0;
    int curr;

    while (first < last) {
            curr = (last - first) * ((height[first] < height[last]) ? height[first] : height[last]);
            max =  curr > max ? curr: max;
            if (height[first] < height[last])
                    first++;
            else
                    last--;
    }

    return max;
}
```
This produces an algorithm with a time complexity of O(n) as it solves the challenge in a single pass with a space complexity of O(1) as no extra space has been allocated.

With that, we come to the end of our array series.
Here are some things to keep in mind when solving for arrays:
- There is almost always a brute-force solution to questions on arrays that includes iterating over the array/arrays. The most efficient solution is usually found by improving on this brute-force implementation.
- Know your array libraries! Most programming languages have libraries that provide various array operations and algorithms. Being familiar with the library in your language of choice will often save you time from having to implement certain procedures from scratch.
- Be comfortable with writing solutions to problems that involve subarrays!
- Some operations on arrays are expensive due to the inherent design of arrays, so always keep in mind how much time each operation might take especially for large inputs. For example, inserting an element from the beginning of an array is slower than inserting it from the end.
- Always solve for when the array is empty first!
That’s it for arrays, and happy coding!