Compilation of my DSA journey in one place.

Question: Leetcode

Brute Force: For every element we can iterate through the entire array and check if there is a duplicate.
Time & Space Complexity: O(n^2) & O(1)

Optimised: Add each element in a Set(or List). Before adding each element to the set, we should check if its already present. If present, then we can stop since duplicate exists.
Time & Space Complexity: O(n) & O(n)

Code: Java

Back to top

Question: Leetcode

Solution We can add the occurences of all characters of the string into separate hashmaps & then compare them both
Time & Space Complexity: O(s+t) & O(s+t)

Code: Java

Back to top

Question: Two Sum

Brute Force: For each element iterate through the rest of the array and calcuate the sum. Basically we are calculating sum of of all possible combinations in the array.
Time & Space Complexity: O(n^2) & O(1)

Optimised: Eg- If target is 9, and the current element is 2, then we are looking for a difference of 7 to add it to 9. So we will add this difference in a hashmap where key:value as difference:index. Now we can check if the desired difference is available in the hashmap.
Time & Space Complexity: O(n) & O(n)

Code: Java

Back to top

Question: Leetcode

Solution: The catch here is only aplhanumeric characters should be considered. We start with 2 pointers. One at the beginning & one at the end of the string and start comparing the characters and converge in the middle. If any non alphanumeric characters are found, then simple proceed to the next index without considering them.
Time & Space Complexity: O(n) & O(1)

Code: Java

Back to top

Question: Leetcode

Brute Force: Iterate through the array. For each element, set it as day of buying and calculate the profit if sold on every day coming up and return the maximum profit in this process.
Time & Space Complexity: O(n^2) & O(1)

Optimised: We can have 2 pointers buy & sell and follow a sliding window approach. When starting, the buy pointer would be the first element and sell would be second.

• If the price of the sell pointer is less than that of buy, then we would change the buy pointer to the index of sell pointer and increment the sell pointer to next element.
• Else, calculate the profit and store if its the maximum and simply increment the sell pointer till the end of the array.
  

Time & Space Complexity: O(n) & O(1)

Code: Java

Back to top

Question: Leetcode

Solution: Iterate through every character of the string.

• If a character is an opening bracket of any type add it in an array and increment the length.
• Else if acharacter is a closing bracket and if the last character in the array is the opening charactr of the same type, then its valid and decrease the length of the array.

If the length of the array is 0, then its valid parentheses order.

Time & Space Complexity: O(n) & O(n)

Code: Java

Back to top

Question: Leetcode

Solution: We can solve this by using 2 stacks - basicStack & minStack. basicStack is to store the values given and minStack is for retrieving the minimum number in contant time O(1).

• push :
  • Always push the given element to basicStack.
  • If the given element is lesser than the top-most element of minStack, then push it to minStack.
• pop:
  • Always pop the element from basicStack.
  • If the popped element from basicStack is the last element in minStack. then pop.
• getMin: We are maintaining the minStack in such a way that the minimum number from the basicStack is always at the top of minStack. So with a simple peek() on minStack we can get the minimum number in constant time.
  

Time & Space Complexity: O(1) & O(n)

Code: Java

Back to top

Question: Leetcode

Brute Force: We can use simple linear search.
Time & Space Complexity: O(n) & O(1)
Optimised: As the name suggests, we can use a simple binary search. In binary search there are 3 pointers - left, right & mid. Initially left=0, right=len-1 and mid=(left+right)/2.

• If arr[mid]==target, then we can return mid.
• Else if arr[mid]<target, It means the value is in next half of the selected array. So we change left as mid+1.
• Else, It means the value can be narrowed down to the first half of the selected array. So we change right as mid-1.

We continue this process till either the element is found or till left <=right.

Time & Space Complexity: O(log(n)) & O(1)

Code: Java

Back to top