Software Developer

Solved using dynamic programming

1) create a dp array, and initialize it as 0.

2) First, we need to initialize the base conditions of the recursive solution.

3) At ind==0, we are considering the first element, if the capacity of the knapsack is greater than the weight of the first item, we return val[0] as answer. We will achieve this using a for loop. 
4) Next, we are done for the first row, so our ‘ind’ variable will move from 1 to n-1, whereas our ‘cap’ variable will move from 0 to ‘W’. We will set the nested loops to traverse the dp array.

5) Inside the nested loops we will apply the recursive logic to find the answer of the cell.
6) When the nested loop execution has ended, we will return dp[n-1][W] as our answer.

Approach using two pointers(l and r) along with an iterator(i). The entire array will be divided into three ranges:

1) Index 0 to l-1 (range containing 0)
2) Index l to r (range containing unknown elements)
3) Index r+1 to n (range containing 2)
4) Initialise l=0 and r=n-1.
5) Inside a for loop, make sure i<=r and do the following steps:
6) If the i-th element is 0, swap it with arr[l] and increment l and i.
7) If the i-th element is 2, swap it with arr[r] and decrement r (not i). The loop will automatically check for the next updated value of arr[i].
8) If the i-th element is arr[i], simply increment i and continue.

Tip 1: be as real as possible