[1] Two Sum problem:

Given an array of integers, return the two numbers which add up to a given target. Assume exactly one solution, and the same element may not be used twice.

Problem Explanation: What this really requires us to write a function that determines if there is a pair of numbers in this array that sums up to the given target sum.

We will explain this problem and solution first by using a simple example.

Suppose we have been given [4,6,1, -5,8], and we got the target sum as 9. We want to find if there is a pair of number in this array that sums up to the given target sum.

As you would note that the function should return 8 and 1 which would add up to 9, which is indeed our given target sum.

So, the question here is what is the best approach to attack this problem?

Well, there can be multiple approaches to tackle this problem. We will start wth the most simple one.

1.1 Two For Loops — Not so optimal solution but still good to go

The naïve approach is to have two for loops and travel through the entire array twice to get the target sum.

So how that would work is that we would travel through the array once, while go through each of the numbers individually, and while you are at each of these numbers, travel through the rest of the array to check if you found the sum of the two numbers equal to the given sum.

For instance, we could start at number 4, and travel through each of the remaining numbers [6,1, -5,8] to see if adding 4 to any of the remaining numbers would result in 9. Since, adding none of the number in the array with 4 results in our target sum, 9, we would move to our next number, 6, and travel through all the remaining numbers [1, -5,8] to see if adding 6 to any of the number from this array would result in 9, and keep traversing in the array.

The point here is to note that while doing this may not be a very optimal way from the time standpoint. Since, two for loop is going to result in O(n²) time complexity because traveling two times using two for loop would mean we are traversing n² time from time complexity standpoint. Nevertheless, since, we are not storing any numbers, the space complexity is O(1).

This leads to the second possible solution which is to use a Python dictionary. That will require an extra space, but the algorithm will be much more optimal from time complexity standpoint.

1.2 Using Dictionary or the Hash Table:

In this approach, we can store every number of the array in a dictionary so each number can be accessed in constant time by the virtue of the key-value property of the python dictionary.

We will make this problem simpler by using the same example of array [4,6,1, -5,8]. Creating an empty dictionary or the hash table would initially look like below:

hashtable={ }

Next, we are going to check if the difference of the target sum and the number we are checking from [4,6,1, -5,8] is present in the hash table or not.

Using the previous example, suppose we are first at number 4, the difference between the target sum,9, and the first number of the array, 4, is 5. Since, 5 is not present in the hash table, 4 gets stored in the hash table, which now looks like below:

hashtable={4: True}

We move further in our array, now at number 6, we will check if the difference between the target sum,9, and number 6, which is 3, is present in the hash table or not. Since, the number 3 is not present in our hash table, the number 6 also gets stored in the hash table. Now the hash table looks like below:

hashtable={4: True, 6: True}

Next, we go to 1 and check if the difference between the target sum,9, and given number 1 — which is equal to 8 — is in hash table or not. The hash table contains 4 and 6 so far, and 8, is not present in the hash table. So, we will store 1 also in the hash table.

hashtable={4: True, 6: True, 1: True}

Next, we go to the following number of the given array, -5, and check if the difference between the target sum,9, and given number -5 — which is equal to 14 — is in hash table or not. The hash table contains 4, 6, and 1 so far, and -14, is not present in the hash table. So, we will store -5 also in the hash table.

hashtable={4: True, 6: True, 1: True, -5: True}

Next, we go to we go to the last number of the given array, 8, and check if the difference between the target sum,9, and given number 8 — which is equal to 1 — is in hash table or not. The hash table contains 4, 6, 1 and -5. Since, 1 is present in our hash table, we get the pair of numbers that we have been searching, which is 8 and 1.

We can print 8 and 1, as the required pairs which will give us the given sum 1, and we have found the answer we were looking for. Since we are only traveling through our array only once, the time complexity is O(n). The space complexity is also O(n) as we are storing all the numbers in the hash table.

The python code using the dictionary is given below:

1.3 Two Pointer Solution by using the sorting algorithm

In this method, we will make use of sorting algorithm as sorting requires nlog(n) time-steps so it is much more optimal than O(n²), the approach which was used using two for loops in the first strategy.

First step in this approach is to sort the numbers in the array. We will have two pointers, first a left pointer at the first number of the array and second a right pointer, located at the last number of the array.

We will simplify this problem again by using the prvious example of the array which is [4,6,1, -5,8]. We then sort it to reflect a sorted array which is [-5,1,4,6,8]. We will have our left pointer at -5 and the right pointer at 8. We will check if -5 +8 equals the given sum, 9. The answer is no, since 3 is less than given sum 9, we will move our pointer in the ascending order, that is from left to right.

Now we move to 1, and check if the sum of 1 and 8 is equal to 9, which is indeed the case. This gives us the pair that we care about. We will now print the pairs 1 and 8 as the pairs that would give the required two number sums.

Let us make this problem, a bit more complex. Imagine, if the target sum was 10, and the sum of 1 and 8, is less than 10, we will move the left pointer in the ascending order, now to 4.

The sum of 4 and 8 is 12 which is more than the target sum. So, we will move the right pointer in the descending order, or from right to left. Now the left pointer is at 4 and the right pointer moves to the number 6.We are at the required pair 4 and 6 that will give us the required sum of 10 in this case.

From a spcae complexity standpoint, the last approach uses O(1) as in space as we are not storing any numbers, and hence,the space complexity is better than the hashing solution given in the second approach. In terms of time complexity, we are using O(nlogn) due to sorting, hence, the time complexity is better than the approach which is given in the first solution, which is a bit more expensive as it uses O(n²).

Python code using the two-pointer solution is given below.

[2] Merged Intervals

The problem: Given an array of integers, merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.

Problem Explanation: What this really requires us to write a function that will print the merged interval for the given set of numbers in an array if there is an overlap in the interval.

Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]

So between [1,3] and [2,6] there is an overlap so the goal is to print the numbers [1,6] which result from the merged intervals between [1,3] and [2,6].

Further, to emphasise the point that the function will keep the array unchanged in case there is no overlap in the intervals — for example the 3rd array, [8,10] and 4th array, [15,18], there is no overlap so the function will keep the array as is.

Hence, the output printed by our function is a 2-dimensional array as shown below:

Output: [[1,6],[8,10],[15,18]]

So how can we determine this programetically?

To simplify this problem, we can simply consider a number line and place these intervals to figure out the tasks.

So we are given this two dimensional array- [[1,3],[2,6],[8,10],[15,18]] and there is clearly an overlap between the 1st and 2nd array but there is no overlap between the 3rd and 4th array. So the required function should be able to print the merged intervals which can be pictured on the number line as shown below.

This suggests that if the array number are sorted, similar to how the numbers are placed in a number line.

This problem becomes very simple, and can be thought to have following three steps algorethmically

a) Sort the arrays in the order of their first number.

a) Check the condition-if the ending number of the first array is bigger than the starting number of the 2nd array- this would mean that there indeed exists an overlapping interval. Otherwise there is no overlapping interval.

Just to illustrate, the ending number of the first array[1,3], which is 3, is bigger than the starting numberof the second array[2,6], which is 2, this would indicate that there exists an overlapping interval. However, as explained before, the number needs to be sorted by the first element of all the arrays, otherwise this condition would fail.

Python code for the same is given below:

[3] Best Time to Buy and Sell Stock

In this problem, we are given an array prices where prices[i] is the price of a given stock on ith day. We want to maximize our profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock. We need to basically write a function that returns the maximum profit we can achieve from this transaction.

To illustrate the problem, we have the stock price results from the Day-1 to Day-6 as shown below:

Now the profit can be computed by subtracting the buy price from the sale price.

The option below would provide a maximum difference in the two prices but will not result in a maximum profit as we can only sell a stock once we have already bought it.

However, once we have already bought it at the minimum price, 1, we can sell it at the maximum price, which is 6, after we have bought the stock.

We can solve this problem using a Brute Force approach as below, which will use two for loops.

The same problem can be solved more optimally with 1 for loop, which is going to require O(n). Python code to solve this problem in O(n) is given below:

[4] Product of Array Except Self

Problem: In this problem, we are given an integer array, the problem requires us to write a function that returns an array such that the output array[i] is equal to the product of all elements of the input array except the ith element of the input array. This problem needs to be solved in O(n) of time complexity.

Suppose the input array nums = [1,2,3,4]

The function should return an output =[24,12,8,6]

Python code that utilizes only 1 for loop and consumes only n order of time complexity can be given as below:

[5] Largest Sum Subarray

Problem Statement

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Example 1

Input: [-2,1,-3,4,-1,2,1,-5,8],

Output: 9

Explanation: [4,-1,2,1,-5,8] has the largest sum = 9.

Example 2

Input: [-2,1,-3,4,-1,2,1,-5,4,6],

Output: 10

Example 3:

Input: nums = [5,4,-1,7,8]

Output: 23

Solution Approach

We will follow a simple approach in this seemingly tricky problem:

If the subarray’sum greater than the current value of the element of the array, we keep the subarray’s sum in the subarray and make it become new subarray of largest sum.
If the subarray’ sum is less than the current value, we will rather keep the current value.

Python Code

BigO Notation

Optimally, as we use just one for loop, the time complexity is O(n). In terms of space complexity, since, we are not storing the values in any array and we are checking the values and discarding it simultaneously, the space complexity is O(1).

Top Leetcode Array Problems