Weekly Coding Questions W-1
Tags: coding, dsa, interviewprep, codinginterviews
Published: 2022-07-10 16:48:00

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](https://leetcode.com/problems/two-sum) 
**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](https://leetcode.com/problems/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](https://leetcode.com/problems/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](https://leetcode.com/problems/move-zeroes/)

**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](https://leetcode.com/problems/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](https://leetcode.com/problems/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] (https://leetcode.com/problems/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](https://leetcode.com/problems/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](https://leetcode.com/problems/fibonacci-number/)

Do as it says, `Fib(n) = Fib(n-1) + Fib(n-2)`

###10. [Pascal's Triangle](https://leetcode.com/problems/pascals-triangle/)

Implement this, `curr_row[i] = prev_row[i-1]+prev_row[i]`

###11. [Squares of a Sorted Array](https://leetcode.com/problems/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](https://leetcode.com/problems/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.