Ace Your Coding Interview — Blind 75 Solved and Explained — Part 1 Arrays

Just graduating this May in Computer Science, a big part of my senior year was focused on finding a job as a software engineer. The road is not an easy one, but with some guidance, it can be accomplished.

Unfortunately, our industry evaluates people on their understanding of so-called “LeetCode” questions to dictate our ability to be successful in the work environment. I know this isn’t for every company but all the companies we may have dreamed of as undergraduates require these for internships and full-time jobs. As much as it’s a false evaluation of people’s abilities, the only way we can prosper through this system is to best study for these interview questions.

Now that we decided we are gonna follow the system, what next? How does one start to LeetCode? With over 2000 questions it is hard for a newbie to know how to tackle this huge question bank. The best way to approach this is to learn styles of problems and understand commonly used techniques.

Without further a due, say hello to the Blind 75, a list curated by Yangshun Tay in 2018. The list since has become famous as a great tool to start your interview preparation.

New Year Gift - Curated List of Top 75 LeetCode Questions to Save Your Time

The list is broken down into 10 categories: Array, Binary, Dynamic Programming, Graph, Interval, Linked List, Matrix, String, Tree, and Heap. Over my next 10 articles, I will individually go over each of the sections trying to provide solutions and explanations to each of these problems.

How to Study

The way to study these vary from person to person, however down below are my recommendations to have the most effective study methods.

I don’t believe in reinventing the wheel. People have already taken the time to solve these to perfection, why should we waste our time reinventing things when we can learn from others. We do this in every area of our lives why not for computer science. With that being said some of these solutions have been heavily inspired by other programmers from the discussion forums on LeetCode.

The goal is not to memorize. DO NOT MEMORIZE. These questions can sometimes be the exact questions or sometimes derivations. To best be prepared understand how each question is solved. Once you are comfortable with the techniques being used to solve each question you’ll often start seeing patterns emerge.

Once you start seeing these patterns these are when things get fun. You see things play out step by step in your approach.

Question 1-Two Sum

Two Sum - LeetCode

Solution to TwoSum

Let us start with arguably the “Hello World” of coding interviews, Two Sum.

This is an easy question that can be solved by brute-forcing through each option, however, we are trying to solve it more efficiently by only looping through the array once.

We loop through the array and for each integer we look to see what is the target value they need to reach the sum. So given the current number what is the matching number that gives us our 2Sum.

Once we have the necessary value we do the following we can follow through with our approach.

Our approach:

1. We create our HashMap in the format of integers, the key is going to be a number in the array, and the value is going to be the index of the number. This is because we need to be able to refer back to the index value of two integers when we are returning.
2. Check if the number exists in the HashMap, if it does it means we have previously seen a value that is complementary to help us achieve two sum.
3. If no matching number add the number into the HashMap, so as we loop in the future we can see that a number is an option.
4. If nothing is found, return null.

Time Complexity: O(n)

Question 2- Best Time to Buy and Sell Stock

Best Time to Buy and Sell Stock - LeetCode

The solution to Best Time to Buy and Sell Stock

Once again we are focusing on looping through our data only once. By the end of our loop, we should be able to return the maximum profit we were able to generate.

Let’s start with some simple math: maxSell = max-min. We are going to loop through our values and whenever we find the lowest value we are going to set that as our minimum. Then we are going to find the largest difference between the minimum and highest peak for the biggest profit.

Our approach:

1. Each time we go through our loop we keep track of our minimum price.
2. If our current value is less than our minimum price this indicates a new minimum, this is important as the greater the gap between the minimum and a current value greater the profit.
3. If our current price minus the minimum price is greater than our max profit we are going to set our max profit to the current price minus the minimum price.
4. Finally, return a maximum profit.

Time Complexity: O(n)

Question 3 - Contains Duplicate

Contains Duplicate - LeetCode

The Solution to Contains Duplicate

This question shows us the importance of HashSet. By utilizing a HashSet we can search a data structure in constant time complexity — O(1).

Our approach:

1. Create a HashSet
2. Loop through the array checking if HashSet contains the value we are currently on. This would indicate that a duplicate exists.
3. If a duplicate doesn’t exist we add it to the HashSet.

Time Complexity: O(n)

Question 4 - Product of Array Except Self

Product of Array Except Self - LeetCode

The Solution to Product Except Self

Solving this problem through a double for loop is easy, however, we are going to look for a solution with better time complexity.

By using two for loops we can solve this problem in linear time. Given the length of the array n, each value in the array will be multiplied by n-1 values.

By multiplying the values in the right by the time we reach the end of the loop we have multiplied every number together and placed the product at the end of the array — all are multiplied except the last position itself.

Subsequently, the same thing happens when we start multiplying from the last position towards the beginning we reach a point of having multiplied everything except the self.

Our approach:

1. We create an array of identical lengths to store our response and set the first index of this array to 1 — the reasoning for this is due to 1 multiplied by anything results in the number itself.
2. Loop one will be in charge of calculating all the left products, to do this we are gonna loop starting at the second index and we going to multiply the result of the answers array with the corresponding index of the numbers array. — I am aware that this is slightly confusing to explain so looking through a table can help us. I am gonna use variable values instead of numerical to ease the showing of all values being multiplied. A figure will be placed below.
3. After we have acquired the left products we are going to look at the right side. As we can see by the end of the first 4 loops the last element is already set, so now we need to work back to get the elements all multiplied for the other indexes.

Math is broken down for product of array except for self

Time Complexity: 2 for loops -> O(n)

Question 5 - Maximum Subarray

Maximum Subarray - LeetCode

The Solution to Maximum SubArray

What is nice about this problem is that you only need to return the value of the maximum subarray, no need to worry about the hassle of tracking the maximum subarray itself.

We are gonna need to track two things, our maximum subarray total and our current subarray total.

Since we are looking for a subarray, as we move forward we can either keep the subarray and grow it or reset it when we find an element of what growth would have been.

Our Approach:

1. Loop through the array and with each iteration set the value of the current subarray. To do this we get the maximum of either the value of the array at the given index or the value of the current subarray plus the value of the array at the given index.
2. We are going to check if the value of the current subarray is greater than the largest subarray we have previously found.
3. Return our maximum subarray value.

Time Complexity: O(n)

Question 6 - Maximum Product Subarray

Maximum Product Subarray - LeetCode

The solution to Maximum Product Subarray

We can call the maximum product subarray an extension of the maximum subarray. For this problem, we are seeking to find the largest product subarray.

We need to track a few things here, our current maximum, current minimum, and our final answer. We keep track of minimums and maximums in this problem because minimums can quickly turn into the new maximum. This happens because a negative multiplied by a negative can lead to a larger positive.

Our Approach:

1. Loop through our array and in each of our iterations we should check to see if the numerical value is negative. If so we swap the min and max values. The reason for this is we are trying to account for the possibility of negative multiplied by negative can create a larger positive.
2. Next, we are going to calculate new maximum and minimum values as well as evaluate our answer. For the maximum and minimum, we need to determine which is lower/higher. For the minimum, we compare the current value to the current value multiplied by the minimum. For the maximum, we evaluate which is greater than the current value or the maximum multiplied by the current value.
3. Return answer

Time Complexity: O(n)

Question 7 - Find Minimum in Rotated Sorted Array

Find Minimum in Rotated Sorted Array - LeetCode

The solution to Minimum in Rotated Sorted Array

This problem deals directly with binary search. This is because the array is sorted given a rotation point. Since we are looking to see the point of rotation once we find this point the question is essentially solved for us.

Our Approach:

1. If the list has one element return the list.
2. Since we are going to be using the binary search method we need to initialize left and right pointers
3. If the last element is greater than the first element then there is no rotation.
4. We start our modified binary search, as long as the right is greater than the left we continue our search.
5. First, find the element in the middle of the array.
6. If the mid element is greater than its next element then the mid+1 element is the smallest. This point would be the point of change. From higher to lower value. Return mid+1 as the minimum.
7. If the mid element is less than its previous element then the mid element is the smallest. Return mid element.
8. If the middle element’s value is greater than the first element this means the least value is still somewhere to the right as we are still dealing with elements greater than the first element.
9. Otherwise, if the first element is greater than the mid-value then this means the smallest value is somewhere to the left.

Time Complexity: O(log(n))

Question 8 - Search in Rotated Sorted Array

Search in Rotated Sorted Array - LeetCode

The solution to Search in Rotated Sorted Array

Similar to the previous question we are going to use a binary search to reach our conclusion. We are going to try to find a pivot point where we can implement a binary search.

Image inspired by https://leetcode.com/wfei26/ discussion response.

Understanding the figure above really allows us to visualize the problem and thus create a solution.

Our Approach

1. Since we are going to be using the binary search method we need to initialize left and right pointers
2. We start our modified binary search, as long as the right is greater than the left we continue our search.
3. First, in the loop, we find the element in the middle of the array.
4. If the mid element is greater than or equal to the leftmost element. We check if the target is between the leftmost element and the middle element. If so we declare our new right element to be before the current middle.
5. Otherwise, we understand the element we are searching for is the right side of the middle element. So we set our leftmost element to be the element that follows the middle.
6. If the element belongs to the right side of the middle we slide our leftmost element to follow the middle.
7. If the element belongs to the left side of the middle we slide the right pointer behind the middle.
8. If the leftmost element is equal to our target by the end of our search we return our left index value. Else we haven’t found the element.

Time Complexity: O(log(n))

Question 9 - 3Sum

3Sum - LeetCode

Solution to 3Sum

To best solve this question we need to evaluate all the prerequisites that allow us to create valid solutions. [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

The way I visualize this problem is almost a sliding window inside a sliding window. This is hard to explain but a visual should do the trick here. A picture is indeed a thousand words.

Drawing showing the movements of i, j, and k

Our Approach:

1. We need to create our return variable and sort our arrays.
2. Next loop through our elements
3. After our first iteration of the loop, we can check if the current index and previous index are the same if so we can skip this iteration as it doesn’t fit our criteria to pass for a 3Sum
4. Next, we need to set up our elements i, j, and k. We set i and j to be next to each other and k at the very end of our array. The reason for this is since we have a sorted array and we know nums[i] + nums[j] + nums[k] == 0 by knowing i and j are going to be smaller than k — hopefully negative — we can reach the sum of one.
5. Next, we are going to create a loop that will allow us to look at possibilities as long as k is greater than j.
6. First, we check if this combination of nums[i] + nums[j] + nums[k] == 0 if they do we add each value to a list, and add the list to our results.
7. Next, we need to iterate the numbers to get rid of possible duplicates in the list. To do this we are going to iterate the j variable forward until we see a different variable from the one we are currently on. We are going to repeat the same process for k, however, we are going to iterate it backward.
8. At the end of the while loop, we are going to push j forward one and k backward once so we can be in different values compared to where we started the loop.
9. Following the while loop, we have two options either our current sum is greater or smaller than 0.
10. If the sum is greater than zero we need to make one of our numbers smaller. Since k is on the right side of the array decreasing k allows us to lower the sum. On the other hand, if our sum is too small we know we need to increase it, since j is on the left side increasing j would allow us to increase the value of the sum.
11. Return final results

Time Complexity: O(n²)

Question 10- Container With Most Water

Container With Most Water - LeetCode

The Solution to Container to with Most Water

Once again we are met with a sliding window problem. We are going to have two pointers one starting at the end of the list and one at the beginning and we are going to inch these pointers closer toward one another

Our Approach:

1. We are going to create a while loop which we will stay inside until our pointers cross one another, to ensure this we are just going to check that left is smaller than right
2. If the left side is taller than the right side. We can say the pool will fill up to the right side so we are going to take the distance between the left and right indexes and multiply it by the height of the shorter side — the right side in this first instance.
3. Since we know the right side to be shorter we are going to decrease it so we can try to find taller elements in the array. This also gets us closest to the left element.
4. If the right side is taller than the left side. We can say the pool will fill up to the left side so we are going to take the distance between the left and right indexes and multiply it by the height of the shorter side — the left side in this first instance.
5. Since we know the left side to be shorter we are going to increase it so we can try to find taller elements in the array. This also gets us closest to the right element.
6. Next, we are going to check if one of the areas we found is larger than the greatest area we previously had.
7. Return our largest area.

Time Complexity: O(n)

What’s Next?

Like I said in the beginning, it’s more important to understand the techniques that we used to solve these questions. If you can understand the steps it takes to reach the solution coding becomes a lot easier.

Down below I have put the links to the other articles that walk through the other Blind 75 sections. I will be releasing one every week on Fridays.

Binary: https://medium.com/@ulucozdenvar01/ace-your-coding-interview-blind-75-solved-part-2-binary-27160cd04462

Interval: https://medium.com/@ulucozdenvar01/ace-your-coding-interview-blind-75-solved-and-explained-part-3-intervals-ef6adbcc93fe

LinkedList: https://medium.com/@ulucozdenvar/ace-your-coding-interview-blind-75-solved-and-explained-part-4-linked-list-6c05a9a92b75

String: https://medium.com/@ulucozdenvar/ace-your-coding-interview-blind-75-solved-and-explained-part-5-string-3cae5fd56f36

Tree: https://medium.com/@ulucozdenvar/ace-your-coding-interview-blind-75-solved-and-explained-part-6-1-trees-fe2576392f54

Trees Part 2: https://medium.com/@ulucozdenvar/ace-your-coding-interview-blind-75-solved-and-explained-part-6-2-trees-continued-64cf6f60350

Matrix: https://medium.com/@ulucozdenvar/ace-your-coding-interview-blind-75-solved-and-explained-part-7-matrix-244b4b308bfc

Heap: https://medium.com/@ulucozdenvar/ace-your-coding-interview-blind-75-solved-and-explained-part-8-heaps-560ab652094f

Dynamic Programming: Coming Soon

Graph: Coming Soon