For software developers, there's some pride in being able to solve complex algorithm questions. Day to day development might not require the same level of complexity, but pushing your understanding of data structures and algorithms can give you the right tools to solve other problems with a balance of simplicity and efficiency. That's why I wanted to check my understanding by summarizing the Leetcode Blind 75 problems and at least one solution.

My goal is to try explaining them without using code. For one, many good solutions to these problems are readily available, so I'm not trying to spend time thinking up some genius solution, only to gather tools to be a better developer.

So for this post, here are the summaries of the Array-type problems in the "Blind 75":

Two Sum

Given a list of numbers and a target, find 2 numbers in list that add up to the target.

Solution with O(n) Time complexity / O(n) Space complexity:

You are wanting to solve x+y=z, where z is target. Iterate through the list, for each number: save to a hash map the key y (which is z-x) → the value x. If the current number matches a key, that is the answer.

Best Time to Buy and Sell Stock

Given a sequential list of a stock’s price, find the 2 prices with the largest difference low to high.

Solution with O(n) Time / O(1) Space:

This is a two pointer solution. Pointer 1 tracks lowest price so far. Pointer 2 iterates the list. Save max profit so far.

Contains Duplicate

Given a list of numbers, return true if the list contains a duplicate number.

Solution with O(n) Time / O(n) Space:

Iterate through and save numbers to a hash set, if any number is already in the hash set, return true.

Product of Array Except Self

Given an array of numbers, return a corresponding array where each element is replaced with the product of all other elements.

Solution with O(n) Time / O(1) Space:

Iterate through the input left to right multiplying each element, while also inserting the running product into the result array 1 element to the right. Iterate right to left, calculating a similar running product, and multiplying with the result array one index to the left.

Maximum Subarray

Given an array of positive and/or negative numbers, find the max sum of a sequence of numbers.

Solution with O(n) Time / O(1) Space:

Iterate through the array, summing the numbers together, saving the max sum encountered so far. If at any time the sum is less than 0, reset the sum to 0.

Maximum Product Subarray

Given an input array of +/- numbers, find the max product of a sequence of numbers.

Solution with O(n) Time / O(1) Space:

The trick is that multiplication never decreases the absolute value of the numbers, so we need to keep track of the highest absolute value product so far, while also tracking any smaller subsequences of the opposite sign, because the max and min flip when a negative number is encountered.

Iterate through, keeping track of 2 subarray products: one for max so far and one for min so far. Every iteration, look at 3 numbers:

1. max * input
2. min * input
3. input

Save the maximum of these numbers as the max product so far. Likewise, save the minimum as the min product so far. The maximum of the max product at any point is the result.

Find Minimum in Rotated Sorted Array

Given an array of numbers that are sorted then offset so that the beginning could be anywhere in the array, find the minimum value.

Solution with O(logN) Time / O(1) Space:

The trick is that you can use standard binary search, by looking for the half that has descending endpoints.

Search in Rotated Sorted Array

Given an array similar to above, find the target value.

Solution with O(logN) Time / O(1) Space:

This will still involve binary search, but this time, look at the half that has ascending endpoints, and thus sorted, to check if the target is within the range. If not, the target must be in the unsorted half.

3 Sum

Given an array of +/- numbers, find all combinations of 3 numbers that add to 0.

Solution with O(n^2) Time / O(n) Space:

Sort the array. Iterate through, using two additional pointers at the low and high end for the inner loop. If the current sum is negative, increase the low pointer, otherwise decrease the high pointer.

Container With Most Water

Given an integer array, find the max area, where the index is the x-axis, and the values are the y-axis.

Solution with O(n) Time / O(1) Space:

Use two pointer starting with endpoints, calculate area as you Iterate. Move the pointer with the lower value.

Next post on binary algorithms