Hey everyone, I'm preparing for coding interviews, so I thought of documenting my journey of solving coding questions here. I'll post weekly blogs containing the questions that I solved in that week with concise approaches.
Here are this week's questions
1. Two Sums
Brute Force
First approach is to use two for loops (nested ones), outside loop for getting the first element, inside loop for getting the second element, then for each inside iteration checking whether their sum is equal to the target or not, if equal then return their indices in array.
Hash Map
Now, to find the two elements, for finding the first element we can just iterate over the array, for finding the second we use the second_element = target-first_element and search it in the hash map, if the second element is present in it, then we return the answer, if not then we insert the first element in hash map and move to the next element in array.
2. Best Time to Buy and Sell Stock
Brute Force
Use two for loops (nested ones) to get the maximum profit.
Pointer approach
Idea is to update the buying price amount when the selling price amount is smaller than it because we will by the stocks on that day and sell them on other next coming days. Because of this in one iteration maximum profit will be calculated easily by selling_price-buying_price.
3. Merge Sorted Array
Approach 1
Fill from the starting, compare elements of both the arrays, if element of first is smaller, then no swap is performed and move to the next element of nums1. If element of first is bigger than the element of nums2, then perform swap and sort the second array nums2 by comparing the new element with its adjacent. After all the elements of nums1 are travesed then add the nums2 elements in nums1.
Time Complexity : O(n*m)
Approach 2
Fill the nums1 array from the last. Compare the last elements first and then which ever is bigger append it to the end space of nums1 and continue this for the rest of the elements.
Time Complexity : O(n+m)
4. Move Zeros
Brute Force
Use another array to store the non zero elements and then append the zeros at the end of that array.
Two pointer
Use two pointers, first pointer for zero element and second pointer for non zero element. Swap the two pointers and move the zero elements to the end of the array.
5. Best Time to Buy and Sell Stock II
The thing here is that we have to calculate the max profit of the whole array. So when we encounter a best selling day, we sell the stocks and the buy new stocks on the same day. When the selling price is smaller than the buying price, we update the buying price to selling price and continue to process of calculating the max profit obtained in the array by adding profit earn doing the above process.
6. Running Sum of 1d Array
Use the idea of prefix sum and apply that on the given array for solving it inplace.
7. Find Pivot Index
Approach 1
Calculate prefix and suffix sum, and index at which both prefix and suffix values are equal is the answer index.
Time Complexity : O(n)
Space Complexity : O(2n) as both prefix and suffix array
Approach 2
Optimising the above solution, first calculate the sum of the total array and initialise a variable leftSum ( initially 0). Then traverse the array and at each index subtract that element from the total sum and compare it with leftSum, if equal the return the index else add the current element in leftSum.
Time Complexity : O(2n)
Space Complexity: O(1)
8. Majority Element
Hash map
Store the frequency count of all the elements in hash map. Then find which ever element occur more than n/2.
Time Complexity: O(n)
Space Complexity: O(n)
Boyer-Moore Voting Algorithm
We will maintain two variables, count and element, if we get the element we increase the count and if the count is zero then we change the element to the current element , if current element is not equal to the element then we decrease the count. After traversing the array, the element will be the majority element. How this works is that the majority element frequency is greater than n/2 so for each sub array, when the count becomes zero, the majority element will cancel the minority element in frequency. So, in the last subarray only majority element will be of high frequency.
Time Complexity: O(n)
9. Fibonacci Number
Do as it says, Fib(n) = Fib(n-1) + Fib(n-2)
10. Pascal's Triangle
Implement this, curr_row[i] = prev_row[i-1]+prev_row[i]
11. Squares of a Sorted Array
Brute Force
Square all the elements in array and then apply sort on the array.
Time Complexity: O(nlogn)
Space Complexity: O(1)
Two pointers
If we observe a test case, we get to know that after squaring all the elements the bigger no. are present at the extremes and it decreases when we move inside.
array = [-4,-1,0,3,10]
after squaring = [16,1,0,9,100]
So, we maintain two pointers start and end, and compare the elements, whichever is bigger is pushed at the end of the result array.
12. Remove Duplicates from Sorted Array
The idea is to replace the repeating elements with unique elements, we achieve this by maintaining a count of repeating elements and when we get a different element we place it at position currPosition - count by which the repeating elements goes to the unique element place and vice versa. The count is updated on each repeating element.
Top comments (0)