Happy Hour Wednesdays: Arrays Part I

As a community, we participate in our #HappyHourWednesdays to get better at our technical interviewing skills.
We do this by reviewing some of the most common data structures and algorithms and solving problems similar to those that are becoming increasingly common during the interviewing process. For the past couple of weeks, we’ve been going through one of the simplest data structure - the Array. This post will go through the questions we’ve seen so far and offer explanations on the best solution to the challenges.

Two Sum
This was our first Array challenge from LeetCode:
```
Given an array of integers nums and an integer target, return indices of
the two numbers such that they add up to target.
You may assume that each input would have exactly one solution, and you may
not use the same element twice. You can return the answer in any order.
```
With most array questions, there is usually a naive solution that includes looping through most elements once or twice. For this particular challenge, the brute force solution would be to iterate through each element to see if there’s another value in the array that equals to the target when subtracted from it. This, however, provides a solution with O(n^2) time complexity which will make the solution inefficient as the imput array increases in size.

To improve our time complexity, we’ll need a more efficient solution. One way to improve our solution is to keep track of complements of seen items in a hashmap such that when the complement stored is found in the existing array, we can return the indices at once. This means that we’ll only iterate through the array once, with each iteration including a check in the hashmap to see if its complement has already been seen before and stored. This reduces our run time complexity to O(n) as we’ll only iterate through the array once. Our space complexity, however, increases to O(n) due to the introduction of the hashmap (since the hashmap would only be able to store at most n items - the original size of the array).

This solution can be implemented as below in C++:
```
using namespace std;

vector<int> twoSum(vector<int>& nums, int target) {
        map<int, int> seen;
        auto size = nums.size();
        std::vector<int> result;
        int sum;

        for (auto i = 0; i < size; i++) {
                sum = target - nums[i];
                auto s = seen.find(sum);
                if (s != seen.end()) {
                        result.push_back(i);
                        result.push_back(s->second);
                }
                seen.emplace(nums[i], i);
        }

    return result;
}
```
Best Time to Buy and Sell Stock This challenge is also from LeetCode:
```
Say you have an array for which the ith element is the price of a given
stock on day *i*. If you were only permitted to complete at most one
transaction (i.e., buy one and sell one share of the stock), design an
algorithm to find the maximum profit.
Note that you cannot sell a stock before you buy one.
```
This challenge As with the previous challenge, this problem has a brute force solution that includes iterating over the items from one end twice (the inner loops starts from i + 1) while keeping track of the maximum difference seen up to that point. Once both loops complete, the stored difference should be the maximum profit that can be achieved. This solution will have a time complexity of O(n^2) as it has two loops iterating over the array.

To improve this solution, we’ll employ one loop that iterates over the array while keeping track of the largest differemce seen so far followed by the smallest price in the array. This enables us to see the largest deep as the loop progresses. At the end of the loop, the largest difference will be stored and returned.
This improves the run time complexity to O(n) as only a single loop is needed for the array with a space complexity of O(1).

This solution can be implemented as below in C++:
```
using namespace std;

int maxProfit(vector<int>& prices) {
        auto size = prices.size();
        int min = INT_MAX;
        int max = 0;

        for (auto i = 0; i < size; i++) {
                if (prices[i] < min) {
                        min = prices[i];
                }
                else if (prices[i] - min > max) {
                        max = prices[i] - min;
                }
        }
        return max;
}
```

From these two examples, it’s clear that most array questions can be solved through brute force solutions which lead to pretty inefficient solutions. Improving on these solutions can lead to a more efficient solution in both space and time complexities.
As #HappyHourWednesday continues, we hope that going over these challenges greatly improves our ability to come up with efficient solutions during interviews.