DP: Longest Increasing Subsequence

The Longest Increasing Subsequence (LIS) problem is to find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.

Note: The subsequence is not necessarily unique or contiguous.

In this post, I'll be solving classic DP problem which involves finding lis of a given array as well as some of its variations.

The problems related to LIS that I'll be seeing are :

1. https://leetcode.com/problems/longest-increasing-subsequence/
2. https://www.interviewbit.com/problems/longest-increasing-subsequence
3. https://leetcode.com/problems/number-of-longest-increasing-subsequence/
4. https://www.interviewbit.com/problems/length-of-longest-subsequence/

Problem 1 and 2:

Let's see problem 1 and 2. Both the problems are similar. The task is to find the length of the longest increasing(strictly) subsequence.

eg: [0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15]

 Here length of LIS = 6. 

We can have multiple LIS with maximum length, but in this problem we are not concerned about the number of longest increasing subsequence(which we will see in 3rd problem here).


I'm gonna dive directly into bottom up approach for solving LIS in O(n ^ 2).

Approach:

Let's observe few scenarios.

A = [1 ,2 ,3, 4, 5]
If we have such array, then how can we find LIS upto length 1... 5. We're gonna need some kind of array to store those values. Let's say we make an array of size that of the given array and initialize with 1 as it is guaranteed that the minimum LIS for an array of length greater than 0 is always 1(Case when there is only 1 element)

What will be the approach to find lis upto index i????
Obviously we have to look at index from j = 0 to i - 1 and see if we can improve by taking element at index j such that element A[j] < A[i]

This roughly translates to below snipppet: lis[i] = max(lis[i], 1 + lis[j])
After building the LIS table , we can return the maximum value from the lis array

Implementation

int Solution::lis(const vector<int> &A) {
    // If the array is empty
    if(A.size() == 0){
            return 0;
        }
        // Initialize lis array with 1
        vector<int> lis(A.size(), 1);
        
        for(int i = 0; i < A.size(); i++){
            for(int j = 0; j < i; j++){
                // If jth element can be taken 
                // Maximize lis upto index i
                if(A[j] < A[i]){
                    lis[i] = max(lis[i], 1 + lis[j]);
                }
            }
        }
        return *max_element(lis.begin(), lis.end());
}

Read More

Leetcode 72. Edit Distance

Problem Link : https://leetcode.com/problems/edit-distance/

Given two words word1 and word2, find the minimum number of operations required to convert word1 to word2.

You have the following 3 operations permitted on a word:

1. Insert a character
2. Delete a character
3. Replace a character

Example 1:

Input: word1 = "horse", word2 = "ros"
Output: 3
Explanation: 
horse -> rorse (replace 'h' with 'r')
rorse -> rose (remove 'r')
rose -> ros (remove 'e')

Example 2:

Input: word1 = "intention", word2 = "execution"
Output: 5
Explanation: 
intention -> inention (remove 't')
inention -> enention (replace 'i' with 'e')
enention -> exention (replace 'n' with 'x')
exention -> exection (replace 'n' with 'c')
exection -> execution (insert 'u')

Solution:

Edit distance between two strings is the minimum number of operations required to convert one string to another. We are given two strings word1 and word2 and are asked to calculate minimum number of operations(insert, delete or replace) required to convert word1 to word2.

Let's try to solve this problem recursively with caching/ top down

class Solution {
public:
    
    // Stores precomputed (i, j) i,e cost for s with length i and
    // t with j length
    map<pair<int, int>, int> mp;
    
    string s, t;
    int helper(int i, int j){
        
        // If already computed for length i and j simply return computed value
        if (mp.find({i, j}) != mp.end()){
            return mp[{i, j}];
        }
        
        // If length of the first string is 0
        // Then we need to insert all the characters equal to length of 
        // second string
        // eg: s = "" and t = "ram"
        // Then we need to insert 3 characters "ram" into s
        
        if(i == 0){
            return j;
        }
        
        // If length of second string is 0
        // Then we need to delete 3 characters from first string
        if(j == 0){
            return i;
        }
        
        // If the corresponding ith and jth character matches 
        // we don't need any operations
        // we just solve for (i - 1) length and (j - 1) length of s and t
        // eg: s = "ram" and t = "cram"
        // Here s[2] == t[3]. So we dont need any additional operation
        // We just solve for its smaller instance i.e s becomes "ra" and t becomes "cra"
        if(s[i - 1] == t[j - 1]){
            return helper(i - 1, j - 1);
        }
        
        // Insert 
        // s = "horse", t = "ros"
        // We insert character 's' costing 1 operations
        // "horses" and "ros" i.e we can eliminate matcging characters from last
        // Then problem reduces to "horse" and "ro"
        // i.e length of string s doesn't change but string t reduces by size 1
        int ins = 1 + helper(i , j - 1);
        
        // Replace
        // eg: = "horse", t = "ros"
        // We can replace last character of string s to 's' with 1 cost operation
        // Then we can eliminate matching characters
        // Then problem reduces to "hors" and "ro"
        // i.e length of s reduces by 1 and t reduces by 1
        int rep = 1 + helper(i - 1, j - 1);
        
        // Delete
        // eg: "horse", t = "ros"
        // We can delete last character from string s with cost 1
        // Then problem reduces to "hors" and "ros"
        // i.e length of s reduces by 1 but length of t doesnt change
        int del = 1 + helper(i - 1, j);
        
        // Save the computed result in dictionary
        mp[{i, j}] = min({ins, rep, del});
        return mp[{i, j}];
        
    }
    int minDistance(string word1, string word2) {
       s = word1;
       t = word2;
       return helper(word1.size(), word2.size());
    }
};

Top-Down approach passes the testcases but sometimes may cause stack overhead due to more recursive calls and you may face issues in language like python unless you explicitly set recursion limit.
So let's try translating the code to bottom up dp.
The first thing we can observe is we are interested only in two parameters :

• length of word1 (i)
• length of word2 (j)

We can write f(i, j) as dp[i][j] which stores edit distance between two string word1 and word2

Translating the code is straight forward, just replace the function call with dp array states. See the implementation

class Solution {
public:
    int minDistance(string word1, string word2) {
        int n = word1.size();
        int m = word2.size();
        vector<vector<int>> dp(n + 1, vector<int>(m + 1, -1));
        
        for(int i = 0; i <= n; i++){
            dp[i][0] = i;
        }
        
         for(int j = 0; j <= m; j++){
            dp[0][j] = j;
        }
        for(int i = 1; i <= n; i++ ){
            for(int j = 1; j <= m; j++){
                if(word1[i - 1] == word2[j - 1]){
                    dp[i][j] = dp[i - 1][j - 1];
                }
                else{
                    //Insert
                    dp[i][j] = 1 + dp[i][j - 1];
                    //Delete
                    dp[i][j] = min(dp[i][j], 1 + dp[i - 1][j]);
                    //Replace
                    dp[i][j] = min(dp[i][j], 1 + dp[i - 1][j - 1]);
                    
                }
            }
        }
        return dp[n][m];
        
    }
};

Read More

Leetcode 931. Minimum Falling Path Sum

Problem Link: https://leetcode.com/problems/minimum-falling-path-sum/

Given a square array of integers A, we want the minimum sum of a falling path through A.

A falling path starts at any element in the first row, and chooses one element from each row.  The next row's choice must be in a column that is different from the previous row's column by at most one.

Example 1:

Input: [[1,2,3],[4,5,6],[7,8,9]]
Output: 12
Explanation: 
The possible falling paths are:

• [1,4,7], [1,4,8], [1,5,7], [1,5,8], [1,5,9]
• [2,4,7], [2,4,8], [2,5,7], [2,5,8], [2,5,9], [2,6,8], [2,6,9]
• [3,5,7], [3,5,8], [3,5,9], [3,6,8], [3,6,9]

The falling path with the smallest sum is [1,4,7], so the answer is 12.

Note:

1. 1 <= A.length == A[0].length <= 100
2. -100 <= A[i][j] <= 100

Solution:

We are given a square grid of size n * n.

What we want is the minimum falling path sum. ie. the minimum sum while falling through row 0 to row (n - 1)

The constraints in the problem is while falling from column of ith row to (i + 1)th row, we can fall on either of the columns {j - 1, j , j+ 1} as it is mentioned that the choice of next row must be in a column that is different from the previous row's column by at most one.


Similar to other grid dp problems, I'm gonna start with the case when I'm at (i, j) cell. How can I reach (i, j) cell??
We can reach (i, j) cell from either of (i - 1, j - 1), (i - 1, j) or (i - 1, j - 1) cell.


Let dp[i][j] gives the minimum possible falling path sum. Then

 dp[i][j] = A[i][j] + min(dp[i - 1][j - 1], dp[i - 1][j], dp[i - 1][j - 1]) 

We must consider a special case for the first row(0th). There is no way to fall to 0th row so, minimum falling path cost is given by the weight of the cell itself

 dp[0][i] = A[0][i] 

Now we are almost done with the solution , for every cell(i, j) form(1, 0) to (n - 1, n- 1) we fill up the dp table in bottom up manner. See the implementation .

Implementation: 

class Solution {
public:
    int minFallingPathSum(vector<vector<int>>& A) {
        
        // Size of grid
        int n = A.size();
        
        // dp[i][j] gives the minimum sum of falling path for cell(i, j)
        vector<vector<int>> dp(n, vector<int> (n, INT_MAX));
        
        // For cell at 0th row we can't fall from any row
        // So for all cells at 0th row minimum sum of falling is the
        // value of eleement itself
        for(int i = 0; i < n; i++){
            dp[0][i] = A[0][i];
        }
        
        
        // Suppose our ans is infinite
        int ans = INT_MAX;
        
        // For all rows from 1 to n - 1
        // We can fall to cell (i, j) from (i - 1, j - 1) or (i - 1, j) or (i - 1, j          + 1)
        
        for(int i  = 1; i < n; i++){
            for(int j = 0; j < n; j++){
                
                // if cell(i, j) is not of last column
                // we can fall from previous row (i - 1, j + 1) with
                //  column greater than 1
                if(j + 1 < n){
                   dp[i][j] =   min(dp[i][j], dp[i - 1][j + 1]);
                }
                // if cell(i, j) is not of first column
                // we can fall from previous row (i - 1, j - 1) with
                //  column less than 1
                if(j - 1 >= 0){
                     dp[i][j] =  min(dp[i][j], dp[i - 1][j - 1]);
                }
                
                // Otherwise we can fall directly from the cell above it(i - 1, j -                 1)
                dp[i][j] =  min(dp[i][j] , dp[i - 1][j]);
                
                // Cost of falling is minimum of the paths and current value of the cell (i, j)
                dp[i][j] += A[i][j];
                
            }
        }
        
        
        // Loop through all elements at last row and compute the minimum value
        // which is the minimum sum of a falling path
        for(auto x: dp[n - 1]){
            ans = min(ans, x);
        }
        return ans;
    }  
};

Read More

Leetcode 198. House Robber

Problem Link https://leetcode.com/problems/house-robber/

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

Example 1:

Input: [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
             Total amount you can rob = 1 + 3 = 4.

Example 2:

Input: [2,7,9,3,1]
Output: 12
Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1).
             Total amount you can rob = 2 + 9 + 1 = 12.

Solution:
We are given integers representing the amount of money at ith house. Our task is to maximize the total money. The constraint is that we are not allowed to rob two consecutive houses.
Let's say we rob 0th house then we can't rob 1st house.

I'll be solving this problem using bottom-up dp.
Suppose dp[i] is the total maximum amount of money that we can rob till ith house.
Clearly:

 dp[0] = nums[0] 

as the total amount of money, we can rob till house 0 is what is in house 0 itself. Also, we can see that the total maximum amount we can rob till house 1st is

 dp[1] = max(nums[0], nums[1]) 

which means we rob either of the house 0 or 1 which has the maxim value.


For all other houses i , we can have maximum  if we don't rob the current house and rob (i - 1)th house or rob ith house with value nums[i]

 dp[i] = max(dp[i - 1], nums[i] +  dp[i - 2]); 

Implementation:

class Solution {
public:
    int rob(vector& nums) {
        // If there is no house
        //  Maximum sum that we can rob is 0
        if(nums.size() == 0){
            return 0;
        }
        
        // If there is only 1 house maximum money is \
        // by robbing the only house
        if(nums.size() == 1){
            return nums[0];
        }
        
        // If there are 2 houses we can rob one of the houses
        // But not both of them as they are consecutive
        // So we maximize the robbery by chossing the house with maximum value
        if(nums.size() == 2){
            return max(nums[0], nums[1]);
        }
        
        // dp[i] stores the maximum value that we can rob till ith house
        vector dp(nums.size(), 0);
        
        // Base Cases
        dp[0] = nums[0];
        dp[1] = max(nums[0], nums[1]);
        
        // For all houses from i = 2 to n - 1
        // Either rob the ith house giving maxm value = nums[i] + dp[i - 2]
        // Or dont rob ith house by giving maximum vale = d[i - 1]
        // We choose the maximum of these two values
        for(int i = 2; i < nums.size(); i++){
            dp[i] = max(dp[i - 1], nums[i] +  dp[i - 2]);
        }
        
        // return maximum value we can rob till (n - 1)th house
        return dp[nums.size() - 1];
    }
};

Read More

Leetcode 63. Unique Paths II

Problem Link: https://leetcode.com/problems/unique-paths-ii/

A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).

Now consider if some obstacles are added to the grids. How many unique paths would there be?

An obstacle and empty space is marked as 1 and 0 respectively in the grid.

Note: m and n will be at most 100.

Example 1:
Input:
[
  [0,0,0],
  [0,1,0],
  [0,0,0]
]
Output: 2
Explanation:
There is one obstacle in the middle of the 3x3 grid above.
There are two ways to reach the bottom-right corner:
1. Right -> Right -> Down -> Down
2. Down -> Down -> Right -> Right

Solution:

Suppose we are at any cell (i, j). Then, the number of ways to reach the cell (i, j) is the sum of number of ways to reach cell (i - 1, j) (above) and (i, j - 1) (left) i.e

          numways(i, j) = numways(i - 1, j) + numways(i, j - 1) 

Instead of using the recursive approach I'm gonna use bottom-up dp to solve the problem.
Let's say dp[i][j] gives the number of ways to reach cell (i, j).
Then,

          dp[i][j] = dp[i - 1][j] + dp[i][j - 1]

The added constraints in the problem is that any cell(i, j) can be either 1 or 0 where 1 denotes there is an obstacle. Clearly

  if(obstacleGrid[i][j] == 1){
                    dp[i][j] = 0;
                }
                else{
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
             }

This is because if the cell(i, j) has obstacle then there is no way we can reach cell (i, j)

We have to handle the base case when the cell is of size 1 * 1. If the cell at (0, 0) has obstacle then there is no way we can reach cell(0, 0) . So we immediately return 0. Else we return 1 as there is only 1 way in tbis case

  if(m == 1 && n == 1){
             if(obstacleGrid[0][0] == 1){
                 return 0;
            }
            return 1;
        }

Let's see the first row and first column.

What is the number of ways to reach any cell (i, 0) or (0, j) ???

There is only one way to reach cell (i, 0) i.e only from upward direction i.e cell (i - 1, 0).

So,

          dp[i][0] = dp[i - 1][j]

Similarly, there is only one way to reach cell (0, j) i.e only from left direction i.e cell (0, j - 1).

So,

          dp[0][j] = dp[0][j - 1]

Using the added constraints in the problem we can rewrite these two conditions as:
We can write the code for first column as

if(obstacleGrid[i][0] == 1){
                dp[i][0] = 0;
}
else if(i < 1){
                dp[i][0] = 1;
}
else{
                dp[i][0] = dp[i - 1][0];
}

Similarly for first row:

if(obstacleGrid[i][0] == 1){
                dp[i][0] = 0;
}
else if(i < 1){
                dp[i][0] = 1;
}
else{
                dp[i][0] = dp[i - 1][0];
}

Implementation:

 class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
     
     
     // FInd number of rows
        int m = obstacleGrid.size();
        
        // Find number of columns 
        int n = obstacleGrid[0].size();
        
        // dp[i][j] gives the num of ways to reach cell(i, j)
        // Initialise 2d array of size m * n with 0
        vector<vector<long long>> dp(m, vector<long long> (n, 0));
        
        // Base condition: If there is only 1 cell
        if(m == 1 && n == 1){
             if(obstacleGrid[0][0] == 1){
                 return 0;
            }
            return 1;
        }
        
        
        
  
        // First column cell (i, 0) can be reached from cell (i - 1, 0)
        for(int i = 0; i < m; i++){
         // If any cell (i, 0) contains obstacle then there is no way to reach the cell(i, j)
         // so dp[i][0] = 0
            if(obstacleGrid[i][0] == 1){
                dp[i][0] = 0;
            }
            // else if it is the first cell (0, 0) and there is no obstacle then
         // dp[i][0] = 1
            else if(i < 1){
                 dp[i][0] = 1;
            }
            // Otherwise we can reach cell (i, 0) from cell(i - 1, 0)
      // so dp[i][0] = dp[i - 1][0]
            else{
                 dp[i][0] = dp[i - 1][0];
            }
           
        }
        
        // First row cell (0, i) can be reached from cell (0, i - 1)
         for(int i = 0; i < n; i++){
          // If any cell (0, i) contains obstacle then there is no way to reach the cell(0, i)
         // so dp[0][i] = 0
            if(obstacleGrid[0][i] == 1){
                dp[0][i] = 0;
            }
            // else if it is the first cell (0, 0) and there is no obstacle then
         // dp[0][i] = 1
            else if(i < 1){
                 dp[0][i] = 1;
            }
            // Otherwise we can reach cell (0, j) from cell(0, j - 1)
         // so dp[0][i] = dp[0][i - 1]
            else{
                    dp[0][i] = dp[0][i - 1];
            }
        }
        
        
        // For every other cells (1, 1) to (m - 1, n - 1)
        // Build dp table in bottom up manner
        for(int i = 1; i < m; i++){
            for(int j = 1; j < n; j++){
             // If obstacle no way to reach cell(i, j)
             // So dp[i][j] =0 
                if(obstacleGrid[i][j] == 1){
                    dp[i][j] = 0;
                }
                //Else num of ways to reach cell(i, j) is
                // the sum of num of ways to reach cell(i - 1, j) and (i, j - 1)
                else{
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
            }
         
        }

  // return num of ways to reach cell(m - 1, n - 1)      
        return dp[m - 1][n - 1];
    }
};

Here is a slightly simpler version of this problem: https://leetcode.com/problems/unique-paths/

Read More

Leetcode 62: Unique Paths

Problem Link: https://leetcode.com/problems/unique-paths/

A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).

How many possible unique paths are there?

Above is a 7 x 3 grid. How many possible unique paths are there?

Note: m and n will be at most 100.

Example 1:

Input: m = 3, n = 2
Output: 3
Explanation:
From the top-left corner, there are a total of 3 ways to reach the bottom-right corner:
1. Right -> Right -> Down
2. Right -> Down -> Right
3. Down -> Right -> Right

Example 2:
Input: m = 7, n = 3
Output: 28

Solution:

Suppose we are at any cell (i, j). Then ,  the number of ways to reach the cell (i, j) is the sum of number of ways to reach cell (i - 1, j) (above) and (i, j - 1) (left) i.e

          numways(i, j) = numways(i - 1, j) + numways(i, j - 1) 

Instead of using recursive approach I'm gonna use bottom up dp to solve the problem.
Let's say dp[i][j] gives the number of ways to reach cell (i, j).
Then,

          dp[i][j] = dp[i - 1][j] + dp[i][j - 1]

Let's see the first row and first column.
What is the number of ways to reach any cell (i, 0) or (0, j) ???
There is only one way to reach cell (i, 0) i.e only from upward direction i.e cell (i - 1, 0).
So,

          dp[i][0] = 1 

Similarly, there is only one way to reach cell (0, j) i.e only from left direction i.e cell (0, j - 1).
So,

          dp[0][j] = 1 

Implementation:

 class Solution {
public:
    int uniquePaths(int m, int n) {
     
     // dp[i][j]  gives the number of ways to reach cell (i, j)
        int dp[m][n];
        
        // There is only 1 way to reach any cell at first column i.e
        // from the cell upward 
        // So dp[i][0] = 1
        for(int i = 0; i < m; i++){
            dp[i][0] = 1;
        }
        
        
        // There is only 1 way to reach any cell at first row i.e
        // from the cell left 
        // So dp[0][j] = 1
        for(int i = 0; i < n; i++){
            dp[0][i] = 1;
        }
        
        
        // For all cells (i, j) from (1, 1) to (m - 1, n - 1)
        // we build the table in bottom up manner
        // We can reach any cell (i, j) from (i - 1, j) or (i, j - 1)
        // So dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
        for(int i = 1; i < m; i++){
            for(int j = 1; j < n; j++){
                dp[i][j]  = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        
        // Return number of ways to reach cell (m - 1, n - 1)
        return dp[m - 1][n - 1];
        
    }
};

Here is a slightly modified version of this problem: https://leetcode.com/problems/unique-paths-ii/

Read More

Python Data Structures 101: 1. How to LIST??

In this post, I'm going to talk about the list, one of the most common but powerful data structures in Python. Let's get started.

Q1. What is a python list?
 Ans: List is a part of core Python Language. It is implemented as a dynamic array. It is heterogeneous(can hold elements of different data types) and is mutable unlike string and tuples in Python.


Q2. How to declare a list?
Ans: We can use list() to make a list

l = list()

Alternatively, we can use

l = []

Just to be sure, we can view the type of the object by writing

print(type(l))

Q3. How to add items in a list?
Ans: 

• Use append() method: 

  l.append(1) 

  This adds 1 to the list.
• Use insert() method: 

  # Using insert we can insert an element at particular index
  # But this increments the size of list by 1 by shifting all the elements towards right
  l = [1, 2, 3, 4, 5]
  l.insert(2, 0)
  print(l)

Q4.  How to find the length of the list?

length_of_list = len(l)

Q5. How to combine two lists?

A = [1, 2, 3, 4, 5]
B = [6, 7, 8, 9]

Non Pythonic Way
combined_list = list()
for a in A:
    combined_list.append(a)
    
for b in B:
    combined_list.append(b)
print(combined_list)


Using extend()

# extend() is inplace i.e modifies the original list 
A.extend(B)
print(A)


Using + operator
combined_list = A + B
print(combined_list)




Q6. How to modify item in a list? Suppose



l = [1, 2, 3, 4, 5]


and we want to set element at index 2 = modified"?


l[2] = "modified"





Q7.  How to remove item from a list?
Ans: 

Using pop() method
# pop() removes the last elemeent from the list
popped_item = l.pop()
print(popped_item)
#Trying to pop from an empty list throws an IndexError
empty_list = []
empty_list.pop()

Using pop() method to delete element at particular index
# We can use pop() method with arguments to delete element at particular index
l = [1, 2, 3, 4]
# Delete element at index 2
l.pop(2)
# Note that pop returns the value of deleted element
Using del
l = [1, 2, 3, 2, 3]
# deletes element ar index 2
del l[2]
# We can use slicing to delete elements
l = [1, 2, 3, 2, 3]
# Deletes elements from index 2 till the end of the list
del l[2: ]
Using remove() method to delete all element by value
# remove() remove the element by value
l = [1, 2, 3, 2, 2]
# removes 2 from the list
# Note that there are multiple occurence of 2 in the list
# remove deletes the first occurence of the 2
print("Before Removing {}".format(l))
l.remove(2)
print("After removing {}".format(l))



Q8. How to reverse the list?
Ans:


using reverse() method:
# reverse() method reverses the list
# It is an inplace operation i.e the original list is modified
l = [1, 2, 3]
l.reverse()
print(l)
using reversed function:
# reversed function returns an reverse iterator to access the list

l = [1, 2, 3]
print(type(reversed(l)))

# TO obtain the reverse list we must first obtain the list from iterator using list(reversed(l)) and assign it to some variable
reversed_list = list(reversed(l))
print(reversed_list)
Using slicing:
l  = [1, 2, 3]
reversed_list = l[: :-1]
print(reversed_list)

Q9. How to find index of particular element?

Ans:

# index() returns the index of irst foccurence of  the element
l = [1, 2, 2, 3, 4, 5]
l.index(2)

Q10. How to count number of occurence of element in list?

Ans:

l = [1, 2, 2, 4, 3, 2, 6]
l.count(2)

Q11. How to clear the list?

ANS:

l = [1, 2, 2]
l.clear()

l = [1, 2, 3]
l = []

Q12. How to copy list?

A = [1 ,2 ,3]
B = A[:]

A = [1, 2, 3]
B = A.copy()

Note: Do not use the below snippet to copy as the memory location is copied instead of actually creating copies of values.

A = [1, 2, 3]
B = A

What if we do?

B[0] = "1"

Does it change the contents of only B or both A and B?


Q13. How to see what methods are available in list?
Ans: 

print(dir(list())

Note: You can use the dir() function for any objects to see what's available

     

Q14. How to make a list of size n initialized with 0?
Ans:

l = [0] * n 

Q15. How to make a list of size m * n initialized with 0?
Ans:

l = [[0] * n] * m 

Read More