SDE - 1

Approach : 

1) Sort the array in ascending order.

2) Now since we want triplets such that x + y + z = ‘K’, we have x+ y = ‘K’ - z and now we can fix z as arr[i]. So we want to find the sum of two numbers x and y as ‘K’ - arr[i] in the array.

3) We will use two pointers, one will start from i+1, and the other will start from the end of the array.

4) Let the two pointers be ‘FRONT’ and ‘BACK’, where ‘FRONT’ = i + 1 and ‘BACK’ = n - 1. Let ‘SUM’ = x + y, where x = ‘ARR[FRONT]’ and y = ‘ARR[BACK]’. We have to find the triplets such that ‘TARGET’ = ‘SUM’.

5) While ‘FRONT’ < ‘BACK’, there will be 3 cases:
5.1) if ('SUM' < ‘TARGET’), we will have to increase the sum and hence increment front pointer.
5.2) Else if ('SUM' > ‘TARGET’), we will have to decrease the sum and hence decrease the ‘BACK’ 
pointer. 
5.3) Else print the triplet and since we want distinct triplets, do the following.
a) Increment the front pointer until ‘ARR[FRONT]’ = x and ‘FRONT’ < ‘BACK’.
b) Decrement the back pointer until ‘ARR[BACK]’ = y and ‘FRONT’ < ‘BACK’.

6) While ‘ARR[i]’ = ‘ARR[i+1]’, keep on incrementing i, this will automatically ensure that we are only finding distinct triplets.

TC : O(N^2) , where N=size of the array
SC : O(1)

Approach : I solved this problem using 2-pointer technique. 

1) Initialize the first pointer to the start of str1 and the second pointer to the start of the str2.

2) Now increase the first pointer till the character pointed by the first pointer in str1 matches the character at the second pointer in str2. And the number of character which did not match should be placed at the end of str1. Therefore increase our answer by how many times we needed to increase the first pointer.

3) Now character pointed by both the pointer is the same so simply increase both pointers as they are same. And perform this while both the pointer do not exhaust the str1 and str2 respectively.

4) One thing to note is that all the characters which did not match would be placed at the end optimally so that the cost will be equal to the unmatched characters with the prefix of str2.

TC : O(N+M), where N is the size of the first string and M is the size of the second string.
SC : O(1)

Approach : If a number N is power of 2 then bitwise & of N and N-1 will be zero. We can say N is a power of 2 or not based on the value of N&(N-1). The expression N&(N-1) will not work when N is 0.
So,handle that case separately.

TC : O(1)
SC : O(1)

Approach 1 (Brute Force) : 

Create an output array and and one by one copy all arrays to it. Finally, sort the output array using. This approach takes O(N Logn N) time where N is count of all elements.

Approach 2 (Using Min-Heap) :

1. Create an output array. 
2. Create a min heap of size k and insert 1st element in all the arrays into the heap 
3. Repeat following steps while priority queue is not empty. 
3.1) Remove minimum element from heap (minimum is always at root) and store it in output array. 
3.2) Insert next element from the array from which the element is extracted. If the array doesn’t have 
any more elements, then do nothing.

TC : O(N*log(K))
SC : O(N)