Apna Coding Adda

 sliding window Introduction Sliding window technique is use for reducing some redundant calculation which slow down program. like it can reduce time complexity from O(n^2) to O(n) with O(1) space complexity. Why use it? First of all it reduce time coplexity and also with O(1) space complexity. so let’s understand with Example… So we want to find maximum sum of k consecutive integer from array, so brute force would look like this for k=5, #include<iostream> #include<vector> using namespace std; int main(){ vector<int> arr = {5,2,6,7,7,3,2,1,3,9}; int final_max = 0; for(int i=0;i<arr.size()-5;i++){ int temp_max = 0; for(int j=i;j<i+5;j++){ temp_max += arr[j]; } if(temp_max>final_max){ final_max = temp_max; } } cout << final_max << endl; return 0; } But time complexity of above program is O(nk) Brute Force Approach As per we can see

 Pascal's Triangle Introduction In mathematics, Pascal’s triangle is triangular array of binomial coefficient. below you can see how it looks like… 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 How to Build it? First of all start with “1” and second rows as “1 1” then we can clearly see every element in next rows(except 1) if sum of two elements from above row. (i.e, 1+1=2, 1+2=3, 1+3=4) and with this rules we can create pascal’s triangle of n rows. Below is visual of how it will look like, Formula let’s take 0th row as first row and 0th column as first column, so we can get each value using formula where n is row number and k is column number. so for finding 1st(0 indexed) element in 2nd row we can write 2C1 which will give 2. There is one another technique, in which we need to solve (x + y)^n for nth row, if we solve (x +y)² then we will get 2nd row as coefficient of x and y in this solved formula which is x² + 2xy + y² . coefficients are (