SDE - 1

Approach (Using Merge Sort) :

1) The idea is similar to merge sort, divide the array into two equal or almost equal halves in each step until the base
case is reached.

2 )Create a function merge that counts the number of inversions when two halves of the array are merged, create two
indices i and j, i is the index for the first half, and j is an index of the second half. if a[i] is greater than a[j], then there
are (mid – i) inversions.

3) Create a recursive function to divide the array into halves and find the answer by summing the number of
inversions is the first half, the number of inversion in the second half and the number of inversions by merging the
two.

4) The base case of recursion is when there is only one element in the given half.

5) Print the answer


TC : O(N*log(N)), where N=size of the array.
SC : O(N)

Approach (Using Kadane's Algo) :

1) Declare a variable ‘maxSum’ and initialize it with ‘minimum integer’

2) Declare a variable ‘localSum’ and initialize it with ‘0’

3) Declare 3 counter variables as ‘start’ , ‘end’ , ‘newStart’ as 0, 0, 0

4) Run a loop from i = 0 to N
4.1) Add a current element to ‘localSum’

4.2) If 'localSum' is greater than 'maxSum'
Update ‘maxSum’ with 'localSum', update start with ‘newStart’ and end with loop counter ‘i’

4.3) If 'localSum' is equal to ‘maxSum’ and the difference between ‘end’ and ‘start’ is less than the
difference between ‘newStart’ and ‘i’
Update start with ‘newStart’ and end with ‘i’

4.4) If 'localSum' is below ‘0’
Update ‘localSum’ as 0 and set ‘newStart' as ‘i’ + 1

5) Return the part of the array starting from ‘start’ and ending at ‘end’


TC : O(N), where N=size of the array
SC : O(N), we need a final array to store the result maximum subarray.

Approach :

1) Declare2-dimensional array t to store the transpose of the matrix. This array will have the reversed dimensions as
of the original matrix.

2) The next step is to loop through the original array and to convert its rows to the columns of matrix t.
2.1) Declare 2 variables i and j.
2.2) Set both i,j=0
2.3) Repeat until i2.3.1) Repeat until j2.3.2) t[i][j] = p[j][i]
2.3.3) j=j+1
2.4) i=i+1

3) The last step is to display the elements of the transposed matrix t.


TC : O(N*M), where N=number of rows and M=number of columns in the matrix.
SC : O(N*M)


//Pseudo Code :

void transpose(int p[][n], int t[][m])
{
for(int i=0; ifor(int j=0; jt[i][j] = p[j][i];
for(int i=0; i{
for(int j=0; jcout<cout<}
}

Approach :

1) If the head is NULL, we simply return HEAD.

2) If there is only one element in the linked list, we simply return it as it is the midpoint.

3) Otherwise, we initialise 2 pointers ‘fast’ and ‘slow’ both poiniting to head initially.

4) We traverse the linked list until fast is the last element or fast is beyond the linked list i.e it points to NULL.

5) In each iteration, the ‘fast’ pointer jumps 2 times faster as compared to ‘slow’ pointer.

6) Finally, once the loop terminates, ‘slow’ pointer will be pointing to the middle element of the linked list, hence we
return the ‘slow’ pointer.


TC : O(N), where ‘N’ denotes the number of elements in the given Linked list.
SC : O(1)

Approach :

1) We create an empty string that will store our final result. We will return it at the end.

2) We iterate from 0 to the length of the string. Say, our loop variable is i. We can then access the ith character as
input[i]

3) If the ith character equals the character c i.e input[i] == c, then we skip this character and do nothing.

4) Else we need to append the character to the output string.

5) We finally return the output string.


TC : O(N), where N=length of the string
SC : O(N)

Approach (Using DP) : 

1) Create a boolean 2D array/list ‘DP’ of size (‘N+1’)*(‘K+1’) i.e. ‘DP[N+1][K+1]’.

2) If ‘K’ is equal to 0, then the answer should be ‘true’. Hence, run a loop from 0 to ‘N’ (say iterator = ‘i’):
‘DP[i][0]’ = true.

3) If ‘K’ is not zero but ‘ARR’ is empty then the answer should be ‘false’. Hence, run a loop from 1 to ‘K’ (say iterator = ‘i’):
‘DP[0][i]’ = false.

4) To fill the ‘DP’ table, run a loop from 1 to ‘N’ (say iterator = ‘i’):
4.1) Run a loop from 1 to ‘K’ (say iterator = ‘j’):
‘DP[i][j]’ = ‘DP[i-1][j]’.

4.2) If ‘j’ is greater than equal to ‘ARR[i-1]’:
‘DP[i][j]’ = ‘DP[i][j]’ OR ‘DP[i-1][j - ARR[i-1]]’.

5) Finally, return ‘DP[N][K]’.


TC : O(N*K), where N = size of the array and K = required sum
SC : O(N*K)

Approach (Using Sorting) : 

1) Sort the list of intervals first on the basis of their start time and then iterate through the array.

2) If the start time of an interval is less than the end of the previous interval, then there is an overlap and we can return true.

3) If we iterate through the entire array without finding an overlap, we can return false.


TC : O(N * logN), where N = total number of intervals.
SC : O(N)

Approach : 

Step 1: Divide the balls into three categories(C1, C2 and C3).
1) Let C1 consist of balls B1, B2 and B3.
2) Let C2 consist of balls B4, B5 and B6.
3) Let C3 consist of balls B7 and B8.

Step 2 : Put C1 on one side of the weighing machine and C2 on the other.
This can give rise to 3 conditions:
1) Condition 1: C1 equals C2
2) Condition 2: C1 < C2
3) Condition 3: C1 > C2 

Now let’s analyse the three conditions to find the defective ball:

Condition 1 : If C1 is equal C2, then C3 has the defective ball. Now measure the weights of ball B7 and B8.
i) If B7 < B8, B7 is defective
ii) If B7 > B8, B8 is defective.

Condition 2 : If C1 < C2, then C1 has the defective ball. Now measure the weights of ball B1 and B2.
i) If B1 equals B2, B3 is defective.
ii) If B1 < B2, B1 is defective.
iii) If B1 > B2, B2 is defective.

Condition 3 : If C1 > C2, then C2 has the defective ball. Now measure the weights of ball B4 and B5.
i) If B4 equals B5, B6 is defective.
ii) If B4 < B5, B4 is defective.
iii) If B4 > B5, B5 is defective.