vitspot/leetcode-daily

leetcode daily solutions

VITspot Engineering

👋 Welcome to our leetcode daily solutions base!

Solutions

Navigate using the following index:

• 2021
  • September
  • October
  • November

Contribution Guidelines

1. Go to the issues tab and open a new issue.
2. If you are the first one to open a issue
   • Start the issue by filling the form ( All fields are mandatory)
3. If you are not the first solution then open issue and fill mandatory fields in form( Question is optional).
4. Submit the issue
5. Happy contributing!

Workflow of Issue Forms feature in Github issues

1. Two new labels named "solution" and "accepted" have to be created. The solution label will be applied automatically when an issue is opened to submit a solution (so as to distinguish amongst other issues).
2. The accepted label has to be applied to the issue before closing it (denoting that it can be merged), so that the respective actions can be carried out. If an issue is closed without adding the accepted label, it means it isn't accepted as a solution and thus will not be processed.
3. All READMEs will be created by the script automatically based on the date mentioned in the submission.
4. Entering the question name and URL is mandatory while entering the question is optional. If a question is not entered the first time a solution is submitted for a given date, then only the name will be present in the README of that day and the question has to be appended manually.
5. In the README of a particular month, the name and link to the question of each day followed by the link to the day's README and links to the solutions will be present.

Submitting Solutions

Want to be part of this initiative and share your solutions with everyone? Share your solutions as a pull request, and get an option to get featured on the solutions page.

leetcode-daily's Issues

Leetcode Solution Submission

Question Name:

Longest Common Subsequence

Question URL:

https://leetcode.com/problems/longest-common-subsequence/

Leetcode Question:

Longest Common Subsequence

Given two strings text1 and text2, return the length of their longest common subsequence. If there is no common subsequence, return 0.

A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.

For example, "ace" is a subsequence of "abcde".
A common subsequence of two strings is a subsequence that is common to both strings.

Example 1:

Input: text1 = "abcde", text2 = "ace" 
Output: 3  
Explanation: The longest common subsequence is "ace" and its length is 3.

Example 2:

Input: text1 = "abc", text2 = "abc"
Output: 3
Explanation: The longest common subsequence is "abc" and its length is 3.

Example 3:

Input: text1 = "abc", text2 = "def"
Output: 0
Explanation: There is no such common subsequence, so the result is 0.

Constraints:

1 <= text1.length, text2.length <= 1000
text1 and text2 consist of only lowercase English characters.

Date:

01/10/2021

Language:

Cpp

Solution:

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
    // Dynamic programming important ques
        int len1 = text1.length();
        int len2 = text2.length();
        int dp[len1+1][len2+1]; //matrix dp of length + 1 of given texts

            // making first row and column 0
            for(int i=0;i<=len1;i++)  
                dp[i][0] = 0;

            for(int i=0;i<=len2;i++)
                dp[0][i] = 0;
            
            for(int i=1;i<=len1;i++){
                for(int j=1;j<=len2;j++){
                    if(text1[i-1]==text2[j-1])
                        dp[i][j] = 1+dp[i-1][j-1]; //incrementing the diagonal element
                    else
                        dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
                }
            }

            return dp[len1][len2];
        
    }
};

Leetcode Submission

Question Name:

Longest Common Subsequence

Question URL:

https://leetcode.com/problems/longest-common-subsequence/

Leetcode Question:

Longest Common Subsequence

Given two strings text1 and text2, return the length of their longest common subsequence. If there is no common subsequence, return 0.

A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.

For example, "ace" is a subsequence of "abcde".
A common subsequence of two strings is a subsequence that is common to both strings.

Example 1:

Input: text1 = "abcde", text2 = "ace" 
Output: 3  
Explanation: The longest common subsequence is "ace" and its length is 3.

Example 2:

Input: text1 = "abc", text2 = "abc"
Output: 3
Explanation: The longest common subsequence is "abc" and its length is 3.

Example 3:

Input: text1 = "abc", text2 = "def"
Output: 0
Explanation: There is no such common subsequence, so the result is 0.

Constraints:

1 <= text1.length, text2.length <= 1000
text1 and text2 consist of only lowercase English characters.

Date:

01/10/2021

Language:

Cpp

Solution:

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
    // Dynamic programming important ques
        int len1 = text1.length();
        int len2 = text2.length();
        int dp[len1+1][len2+1]; //matrix dp of length + 1 of given texts

            // making first row and column 0
            for(int i=0;i<=len1;i++)  
                dp[i][0] = 0;

            for(int i=0;i<=len2;i++)
                dp[0][i] = 0;
            
            for(int i=1;i<=len1;i++){
                for(int j=1;j<=len2;j++){
                    if(text1[i-1]==text2[j-1])
                        dp[i][j] = 1+dp[i-1][j-1]; //incrementing the diagonal element
                    else
                        dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
                }
            }

            return dp[len1][len2];
        
    }
};

Leetcode Solution Submission

Question Name:

Jump Game

Question URL:

https://leetcode.com/problems/jump-game/

Leetcode Question:

Jump Game

You are given an integer array nums. You are initially positioned at the array's first index, and each element in the array represents your maximum jump length at that position.

Return true if you can reach the last index, or false otherwise.

Example 1:

Input: nums = [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

Example 2:

Input: nums = [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. 

Its maximum jump length is 0, which makes it impossible to reach the last index.

Constraints:

1 <= nums.length <= 104
0 <= nums[i] <= 105

Date:

03/10/2021

Language:

Cpp

Solution:

class Solution {
public:
    bool canJump(vector<int>& nums) {
        
        int len = nums.size();
        int reach_till = 0;
        
        for(int i=0; i<len;i++){
            
            if(reach_till < i) return false;
            
            reach_till = max(reach_till, i+ nums[i]);
        }
        return true;
    }
};

Leetcode Solution Submission

Question Name:

Surrounded Regions

Question URL:

https://leetcode.com/problems/surrounded-regions/

Leetcode Question:

Given an m x n matrix board containing 'X' and 'O', capture all regions that are 4-directionally surrounded by 'X'.

A region is captured by flipping all 'O's into 'X's in that surrounded region.

Example 1:

Input: board = [["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]]
Output: [["X","X","X","X"],["X","X","X","X"],["X","X","X","X"],["X","O","X","X"]]
Explanation: Surrounded regions should not be on the border, which means that any 'O' on the border of the board are not flipped to 'X'. Any 'O' that is not on the border and it is not connected to an 'O' on the border will be flipped to 'X'. Two cells are connected if they are adjacent cells connected horizontally or vertically.

Example 2:

Input: board = [["X"]]
Output: [["X"]]

Constraints:

m == board.length
n == board[i].length
1 <= m, n <= 200
board[i][j] is 'X' or 'O'.

Date:

01/11/2021

Language:

Py

Solution:

class Solution:
    def solve(self, board: List[List[str]]) -> None:
        def dfs(x,y):
            if not (0<=x<n and 0<=y<m) or board[x][y]!='O':
                return
            board[x][y] = 'S'
            dfs(x+1,y) ; dfs(x-1,y) # up and down
            dfs(x,y+1) ; dfs(x,y-1) # left and right
            
        n = len(board) # no of rows
        m = len(board[0]) # no of column
        
        # Looping throw the first and last column to find 'O'
        for i in range(n):
            dfs(i,0)
            dfs(i,m-1)
        
        # Looping throw the first and last row to find 'O'
        for j in range(m):
            dfs(0,j)
            dfs(n-1,j)
        
        # Now Change the 'S' that are in borders to 'O'
        
        # Changin the 'S' in first and last column to 'O'
        for i in range(n):
            if board[i][0] == 'S': board[i][0] = 'O'
            if board[i][m-1] == 'S': board[i][m-1] = 'O'
                
        # Changin the 'S' in first and last row to 'O'
        for j in range(m):
            if board[0][j] == 'S': board[0][j] = 'O'
            if board[n-1][j] == 'S': board[n-1][j] = "O"
                
        """
        Now all the 'S' which are inside the border are not surrounded 
        by X, so change it to 'O' and rest of the 'O' can be 
        converted to 'X' as it is surrounded by 'X'
        """
        
        for i in range(1,n-1):
            for j in range(1,m-1):
                if board[i][j] == 'O': board[i][j] = "X"
                if board[i][j] == "S": board[i][j] = "O"

Leetcode Solution Submission

Question Name:

Word Search

Question URL:

https://leetcode.com/problems/word-search/

Leetcode Question:

Given an m x n grid of characters board and a string word, return true if word exists in the grid.

The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once.

Example 1:

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
Output: true

Example 2:

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
Output: true

Example 3:

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
Output: false

Constraints:

m == board.length
n = board[i].length
1 <= m, n <= 6
1 <= word.length <= 15
board and word consists of only lowercase and uppercase English letters.

Date:

07/10/2021

Language:

Py

Solution:

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        n = len(word)
        N = len(board)
        M = len(board[0])
        
        def dfs(x,y,i):
            if i == n: return True
            if not (0<=x<N and 0<=y<M): return False
            if board[x][y]!=word[i]: return False
            
            board[x][y] = '  '
            path = [(-1,0),(1,0),(0,-1),(0,1)]
            
            result = any(dfs(x+r,y+m,i+1) for r,m in path)
            board[x][y] = word[i]
            return result
        
        C,starts = Counter(word),[]
        for x in range(N):
            for y in range(M):
                C[board[x][y]] -= 1
                if board[x][y] == word[0]: starts.append((x,y))
                    
        if max(C.values())>0: return False
        for r,c in starts:
            if dfs(r,c,0): return True
        
        return False

Leetcode Solution Submission

Question Name:

Climbing Stairs

Question URL:

https://leetcode.com/problems/climbing-stairs/

Leetcode Question:

Climbing Stairs

You are climbing a staircase. It takes n steps to reach the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Example 1:

Input: n = 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps
3. 

Example 2:

Input: n = 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step

Constraints:

1 <= n <= 45

Date:

05/10/2021

Language:

Cpp

Solution:

class Solution {
public:
    int climbStairs(int n) {
     // for n=2 -> 2
    // for n= 3 -> 3
        // for n =4 -> 5
        // for n=5 ->8
        // as we cab see it's forming fibonacci series: sum of previous 2 digits
        int a =1, b=1,c = a+b, i=2;
        if(n == 1) return 1;
        //while conditon will give output starting from n =2;
        while(i++<n){
            a = b;
            b =c;
            c =a+b;
            
        }
        return c;
        
    }
};

Leetcode Solution Submission

Question Name:

Dungeon Game

Question URL:

https://leetcode.com/problems/dungeon-game/

Leetcode Question:

No response

Date:

02/10/2021

Language:

Py

Solution:

class Solution:
    def calculateMinimumHP(self, dungeon: List[List[int]]) -> int:
        n = len(dungeon)-1
        m = len(dungeon[0])-1
        
        dp = dungeon
        dp[n][m] = max(1,1-dp[n][m])
        
        for r in reversed(range(n)):
            dp[r][m] = max(1,dp[r+1][m]-dp[r][m])
        
        for c in reversed(range(m)):
            dp[n][c] = max(1,dp[n][c+1]-dp[n][c])
        
        for r in reversed(range(n)):
            for c in reversed(range(m)):
                ans = min(dp[r+1][c],dp[r][c+1])-dp[r][c]
                dp[r][c] = max(1,ans)
        
        return dp[0][0]

Leetcode Solution Submission

Question Name:

Jump Game

Question URL:

https://leetcode.com/problems/jump-game/

Leetcode Question:

Jump Game

You are given an integer array nums. You are initially positioned at the array's first index, and each element in the array represents your maximum jump length at that position.

Return true if you can reach the last index, or false otherwise.

Example 1:

Input: nums = [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

Example 2:

Input: nums = [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. 

Its maximum jump length is 0, which makes it impossible to reach the last index.

Constraints:

1 <= nums.length <= 104
0 <= nums[i] <= 105

Date:

03/10/2021

Language:

Cpp

Solution:

class Solution {
public:
    bool canJump(vector<int>& nums) {
        
        int len = nums.size();
        int reach_till = 0;
        
        for(int i=0; i<len;i++){
            
            if(reach_till < i) return false;
            
            reach_till = max(reach_till, i+ nums[i]);
        }
        return true;
    }
};

Leetcode Solution Submission

Question Name:

Jump Game

Question URL:

https://leetcode.com/problems/jump-game/

Leetcode Question:

Jump Game

You are given an integer array nums. You are initially positioned at the array's first index, and each element in the array represents your maximum jump length at that position.

Return true if you can reach the last index, or false otherwise.

Example 1:

Input: nums = [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

Example 2:

Input: nums = [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum jump length is 0, which makes it impossible to reach the last index.

Constraints:

1 <= nums.length <= 104
0 <= nums[i] <= 105

Date:

03/10/2021

Language:

Cpp

Solution:

class Solution {
public:
    bool canJump(vector<int>& nums) {
        
        int len = nums.size();
        int reach_till = 0;
        
        for(int i=0; i<len;i++){
            
            if(reach_till < i) return false;
            
            reach_till = max(reach_till, i+ nums[i]);
        }
        return true;
    }
};

Leetcode Solution Submission

Question Name:

Split Linked List in Parts

Question URL:

https://leetcode.com/explore/challenge/card/september-leetcoding-challenge-2021/640/week-5-september-29th-september-30th/3992/

Leetcode Question:

Given the head of a singly linked list and an integer k, split the linked list into k consecutive linked list parts.

The length of each part should be as equal as possible: no two parts should have a size differing by more than one. This may lead to some parts being null.

The parts should be in the order of occurrence in the input list, and parts occurring earlier should always have a size greater than or equal to parts occurring later.

Return an array of the k parts.

Example 1:


Input: head = [1,2,3], k = 5
Output: [[1],[2],[3],[],[]]
Explanation:
The first element output[0] has output[0].val = 1, output[0].next = null.
The last element output[4] is null, but its string representation as a ListNode is [].

Example 2:

Input: head = [1,2,3,4,5,6,7,8,9,10], k = 3
Output: [[1,2,3,4],[5,6,7],[8,9,10]]
Explanation:
The input has been split into consecutive parts with size difference at most 1, and earlier parts are a larger size than the later parts.


Constraints:

The number of nodes in the list is in the range [0, 1000].
0 <= Node.val <= 1000
1 <= k <= 50

Date:

29/09/2021

Language:

Cpp

Solution:

  class Solution {
  public:
   
      vector<ListNode*> splitListToParts(ListNode* head, int k) {
          
        
          ListNode* ptr = head;
          int siz =0;
          while(ptr){
              siz++; ptr = ptr->next;
          }
          
          int sizeinPart = siz / k, extrapart = siz % k;
           ListNode *temp =NULL;
          vector<ListNode*> result(k);
          
          for(int i=0; i<k; i++){
              result[i]= head;
              for(int j =0; j< sizeinPart + (i < extrapart); j++){
                  temp = head;
                  head =head->next;
              }
              if(temp) temp->next = NULL;
          }
          return result;
          
      }
  };

Leetcode Solution Submission

Question Name:

Jump Game

Question URL:

https://leetcode.com/problems/jump-game/

Leetcode Question:

Jump Game

You are given an integer array nums. You are initially positioned at the array's first index, and each element in the array represents your maximum jump length at that position.

Return true if you can reach the last index, or false otherwise.

Example 1:

Input: nums = [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

Example 2:

Input: nums = [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. 

Its maximum jump length is 0, which makes it impossible to reach the last index.

Constraints:

1 <= nums.length <= 104
0 <= nums[i] <= 105

Date:

03/10/2021

Language:

Cpp

Solution:

class Solution {
public:
    bool canJump(vector<int>& nums) {
        
        int len = nums.size();
        int reach_till = 0;
        
        for(int i=0; i<len;i++){
            
            if(reach_till < i) return false;
            
            reach_till = max(reach_till, i+ nums[i]);
        }
        return true;
    }
};

Add contributing guidelines

• Commit message structure
• Also Fix any typos in readme

Leetcode Solution Submission

Question Name:

Arithmetic Slices

Question URL:

https://leetcode.com/problems/arithmetic-slices/

Leetcode Question:

An integer array is called arithmetic if it consists of at least three elements and if the difference between any two consecutive elements is the same.

For example, [1,3,5,7,9], [7,7,7,7], and [3,-1,-5,-9] are arithmetic sequences.
Given an integer array nums, return the number of arithmetic subarrays of nums.

A subarray is a contiguous subsequence of the array.

Example 1:

Input: nums = [1,2,3,4]
Output: 3
Explanation: We have 3 arithmetic slices in nums: [1, 2, 3], [2, 3, 4] and [1,2,3,4] itself.

Example 2:

Input: nums = [1]
Output: 0

Constraints:

• 1 <= nums.length <= 5000
• -1000 <= nums[i] <= 1000

Date:

03/03/2022

Language:

Py

Solution:

class Solution:
    def numberOfArithmeticSlices(self, nums: List[int]) -> int:
        N = len(nums)
        if N < 3: return 0
        cnt, prev_diff, total_slice = 0, inf, 0
        for i in range(N-1):
            diff = nums[i+1] - nums[i]
            if prev_diff != diff:
                prev_diff = diff
                cnt = 0
            else:
                cnt += 1
                total_slice += cnt
            print(prev_diff, diff, cnt, total_slice)
            
        return total_slice

Leetcode Solution Submission

Question Name:

Split Linked List in Parts

Question URL:

https://leetcode.com/explore/challenge/card/september-leetcoding-challenge-2021/640/week-5-september-29th-september-30th/3992/

Leetcode Question:

Split Linked List in Parts

Given the head of a singly linked list and an integer k, split the linked list into k consecutive linked list parts.

The length of each part should be as equal as possible: no two parts should have a size differing by more than one. This may lead to some parts being null.

The parts should be in the order of occurrence in the input list, and parts occurring earlier should always have a size greater than or equal to parts occurring later.

Return an array of the k parts.

Example 1:

Input: head = [1,2,3], k = 5
Output: [[1],[2],[3],[],[]]
Explanation:
The first element output[0] has output[0].val = 1, output[0].next = null.
The last element output[4] is null, but its string representation as a ListNode is [].

Example 2:

Input: head = [1,2,3,4,5,6,7,8,9,10], k = 3
Output: [[1,2,3,4],[5,6,7],[8,9,10]]
Explanation:
The input has been split into consecutive parts with size difference at most 1, and earlier parts are a larger size than the later parts.

Constraints:

The number of nodes in the list is in the range [0, 1000].
0 <= Node.val <= 1000
1 <= k <= 50

Date:

29/09/2021

Language:

Cpp

Solution:

class Solution {
public:

vector<ListNode*> splitListToParts(ListNode* head, int k) {
    
  
    ListNode* ptr = head;
    int siz =0;
    while(ptr){
        siz++; ptr = ptr->next;
    }
    
    int sizeinPart = siz / k, extrapart = siz % k;
     ListNode *temp =NULL;
    vector<ListNode*> result(k);
    
    for(int i=0; i<k; i++){
        result[i]= head;
        for(int j =0; j< sizeinPart + (i < extrapart); j++){
            temp = head;
            head =head->next;
        }
        if(temp) temp->next = NULL;
    }
    return result;
    
}

};

Leetcode Solution Submission

Question Name:

Jump Game

Question URL:

https://leetcode.com/problems/jump-game/

Leetcode Question:

Jump Game

You are given an integer array nums. You are initially positioned at the array's first index, and each element in the array represents your maximum jump length at that position.

Return true if you can reach the last index, or false otherwise.

Example 1:

Input: nums = [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

Example 2:

Input: nums = [3,2,1,0,4]
Output: false
  Explanation: You will always arrive at index 3 no matter what. Its maximum jump length is 0, which makes it impossible to reach the last index.

Constraints:

1 <= nums.length <= 104
0 <= nums[i] <= 105

Date:

03/10/2021

Language:

Cpp

Solution:

class Solution {
public:
    bool canJump(vector<int>& nums) {
        
        int len = nums.size();
        int reach_till = 0;
        
        for(int i=0; i<len;i++){
            
            if(reach_till < i) return false;
            
            reach_till = max(reach_till, i+ nums[i]);
        }
        return true;
    }
};

Leetcode Solution Submission

Question Name:

Diameter of Binary Tree

Question URL:

https://leetcode.com/problems/diameter-of-binary-tree/

Leetcode Question:

Diameter of Binary Tree

Given the root of a binary tree, return the length of the diameter of the tree.

The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.

The length of a path between two nodes is represented by the number of edges between them.

Example 1:

Input: root = [1,2,3,4,5]
Output: 3
Explanation: 3 is the length of the path [4,2,1,3] or [5,2,1,3].

Example 2:

Input: root = [1,2]
Output: 1

Constraints:

The number of nodes in the tree is in the range [1, 104].
-100 <= Node.val <= 100

Date:

11/10/2021

Language:

Cpp

Solution:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int diameterOfBinaryTree(TreeNode* root) {
        int d=0;
        CalcHeightNode(root, d);
        return d;
        
    }
     int CalcHeightNode(TreeNode* node, int& d){
        if(!node) return 0;
        int leftht =CalcHeightNode(node->left, d);
        int rightht =CalcHeightNode(node->right, d);
        
        d = max(d,(leftht+rightht));
        
        return 1 + max(leftht, rightht);
    }
    
};

Leetcode Solution Submission

Question Name:

Longest Common Subsequence

Question URL:

https://leetcode.com/problems/longest-common-subsequence/

Leetcode Question:

Longest Common Subsequence

Given two strings text1 and text2, return the length of their longest common subsequence. If there is no common subsequence, return 0.

A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.

For example, "ace" is a subsequence of "abcde".
A common subsequence of two strings is a subsequence that is common to both strings.

Example 1:

Input: text1 = "abcde", text2 = "ace" 
Output: 3  
Explanation: The longest common subsequence is "ace" and its length is 3.

Example 2:

Input: text1 = "abc", text2 = "abc"
Output: 3
Explanation: The longest common subsequence is "abc" and its length is 3.

Example 3:

Input: text1 = "abc", text2 = "def"
Output: 0
Explanation: There is no such common subsequence, so the result is 0.

Constraints:

1 <= text1.length, text2.length <= 1000
text1 and text2 consist of only lowercase English characters.

Date:

01/10/2021

Language:

Cpp

Solution:

class Solution {
public:
int longestCommonSubsequence(string text1, string text2) {
// Dynamic programming important ques
int len1 = text1.length();
int len2 = text2.length();
int dp[len1+1][len2+1]; //matrix dp of length + 1 of given texts

            // making first row and column 0
            for(int i=0;i<=len1;i++)  
                dp[i][0] = 0;

            for(int i=0;i<=len2;i++)
                dp[0][i] = 0;
            
            for(int i=1;i<=len1;i++){
                for(int j=1;j<=len2;j++){
                    if(text1[i-1]==text2[j-1])
                        dp[i][j] = 1+dp[i-1][j-1]; //incrementing the diagonal element
                    else
                        dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
                }
            }

            return dp[len1][len2];
        
    }
};

Leetcode Solution Submission

Question Name:

Jump Game

Question URL:

https://leetcode.com/problems/jump-game/

Leetcode Question:

Jump Game

You are given an integer array nums. You are initially positioned at the array's first index, and each element in the array represents your maximum jump length at that position.

Return true if you can reach the last index, or false otherwise.

Example 1:

Input: nums = [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

Example 2:

Input: nums = [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. 

Its maximum jump length is 0, which makes it impossible to reach the last index.

Constraints:

1 <= nums.length <= 104
0 <= nums[i] <= 105

Date:

03/10/2021

Language:

Cpp

Solution:

class Solution {
public:
    bool canJump(vector<int>& nums) {
        
        int len = nums.size();
        int reach_till = 0;
        
        for(int i=0; i<len;i++){
            
            if(reach_till < i) return false;
            
            reach_till = max(reach_till, i+ nums[i]);
        }
        return true;
    }
};

Leetcode Solution Submission

Question Name:

Sum of Left Leaves

Question URL:

https://leetcode.com/problems/sum-of-left-leaves/

Leetcode Question:

Given the root of a binary tree, return the sum of all left leaves.

Example 1:

Input: root = [3,9,20,null,null,15,7]
Output: 24
Explanation: There are two left leaves in the binary tree, with values 9 and 15 respectively.

Example 2:

Input: root = [1]
Output: 0

Constraints:

The number of nodes in the tree is in the range [1, 1000].
-1000 <= Node.val <= 1000

Date:

04/11/2021

Language:

Py

Solution:

class Solution:
    def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:
        stack = deque([(root,False)])
        
        result = 0
        
        while stack:
            node,isleft = stack.popleft()
            if not node: continue
            if not (node.left or node.right) and isleft:
                result+=node.val
                continue
            stack.append((node.left,True))
            stack.append((node.right,False))
        
        return result

Leetcode Solution Submission

Question Name:

Bitwise AND of Numbers Range

Question URL:

https://leetcode.com/problems/bitwise-and-of-numbers-range/

Leetcode Question:

Bitwise AND of Numbers Range

Given two integers left and right that represent the range [left, right], return the bitwise AND of all numbers in this range, inclusive.

Example 1:

Input: left = 5, right = 7
Output: 4

Example 2:

Input: left = 0, right = 0
Output: 0

Example 3:

Input: left = 1, right = 2147483647
Output: 0

Constraints:

0 <= left <= right <= 231 - 1

Date:

10/10/2021

Language:

Cpp

Solution:

class Solution {
public:
    int rangeBitwiseAnd(int mleft, int nright) {
        
        int k = 0;
      while(mleft != nright){
         mleft >>= 1;
         nright >>= 1;
         k++;
      }
      return mleft << k;
    }
};

Leetcode Solution Submission

Question Name:

Dungeon Game

Question URL:

https://leetcode.com/problems/dungeon-game/

Leetcode Question:

No response

Date:

02/10/2021

Language:

Py

Solution:

class Solution:
    def calculateMinimumHP(self, dungeon: List[List[int]]) -> int:
        n = len(dungeon)
        m = len(dungeon[0])
        
        @lru_cache(None)
        def rec(i,j):
            if i>=n or j>=m:
                return inf
            
            if (i,j) == (n-1,m-1):
                ans = max(1,1-dungeon[i][j])
                return ans
            
            ans = min(rec(i+1,j),rec(i,j+1))
            ans-=dungeon[i][j]
            
            return max(1,ans)
        
        return rec(0,0)

Leetcode Solution Submission

Question Name:

Jump Game

Question URL:

https://leetcode.com/problems/jump-game/

Leetcode Question:

Jump Game

You are given an integer array nums. You are initially positioned at the array's first index, and each element in the array represents your maximum jump length at that position.

Return true if you can reach the last index, or false otherwise.

Example 1:

Input: nums = [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

Example 2:

Input: nums = [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. 

Its maximum jump length is 0, which makes it impossible to reach the last index.

Constraints:

1 <= nums.length <= 104
0 <= nums[i] <= 105

Date:

03/10/2021

Language:

Cpp

Solution:

class Solution {
public:
    bool canJump(vector<int>& nums) {
        
        int len = nums.size();
        int reach_till = 0;
        
        for(int i=0; i<len;i++){
            
            if(reach_till < i) return false;
            
            reach_till = max(reach_till, i+ nums[i]);
        }
        return true;
    }
};

Leetcode Solution Submission

Question Name:

Summary Ranges

Question URL:

https://leetcode.com/problems/summary-ranges/

Leetcode Question:

You are given a sorted unique integer array nums.

Return the smallest sorted list of ranges that cover all the numbers in the array exactly. That is, each element of nums is covered by exactly one of the ranges, and there is no integer x such that x is in one of the ranges but not in nums.

Each range [a,b] in the list should be output as:

"a->b" if a != b
"a" if a == b

Example 1:

Input: nums = [0,1,2,4,5,7]
Output: ["0->2","4->5","7"]
Explanation: The ranges are:
[0,2] --> "0->2"
[4,5] --> "4->5"
[7,7] --> "7"

Example 2:

Input: nums = [0,2,3,4,6,8,9]
Output: ["0","2->4","6","8->9"]
Explanation: The ranges are:
[0,0] --> "0"
[2,4] --> "2->4"
[6,6] --> "6"
[8,9] --> "8->9"

Constraints:

• 0 <= nums.length <= 20
• -231 <= nums[i] <= 231 - 1
• All the values of nums are unique.
• nums is sorted in ascending order.

Date:

28/02/2022

Language:

Py

Solution:

class Interval(NamedTuple):
    start: int
    end: int
    
    def __str__(self) -> str:
        if self.start == self.end:
            return str(self.start)
        else:
            return f"{self.start}->{self.end}"

class Solution:
    def summaryRanges(self, nums: List[int]) -> List[str]:
        return list(map(str, self.range_iterator(nums)))
    
    def range_iterator(self, nums: List[int]) -> Iterable[Interval]:
        start = end = -inf
        for n in nums:
            if end < n-1:
                if end > -inf:
                    yield Interval(start, end)
                start = end = n
            end = n
        if end > -inf: yield Interval(start, end)

Leetcode Solution Submission

Question Name:

141. Linked List Cycle

Question URL:

https://leetcode.com/problems/linked-list-cycle/

Leetcode Question:

Given head, the head of a linked list, determine if the linked list has a cycle in it.

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail's next pointer is connected to. Note that pos is not passed as a parameter.

Return true if there is a cycle in the linked list. Otherwise, return false.

Example 1:

Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the 1st node (0-indexed).

Example 2:

Input: head = [1,2], pos = 0
Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the 0th node.

Example 3:

Input: head = [1], pos = -1
Output: false
Explanation: There is no cycle in the linked list.

Constraints:

• The number of the nodes in the list is in the range [0, 104].
• -105 <= Node.val <= 105
• pos is -1 or a valid index in the linked-list.

Follow up: Can you solve it using O(1) (i.e. constant) memory?

Date:

08/03/2022

Language:

Py

Solution:

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        slow, fast = head, head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow is fast: return True
        return False

Leetcode Solution Submission

Question Name:

Jump Game

Question URL:

https://leetcode.com/problems/jump-game/

Leetcode Question:

Jump Game

You are given an integer array nums. You are initially positioned at the array's first index, and each element in the array represents your maximum jump length at that position.

Return true if you can reach the last index, or false otherwise.

Example 1:

Input: nums = [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

Example 2:

Input: nums = [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum jump length is 0, which makes it impossible to reach the last index.

Constraints:

1 <= nums.length <= 104
0 <= nums[i] <= 105

Date:

03/10/2021

Language:

Cpp

Solution:

class Solution {
public:
    bool canJump(vector<int>& nums) {
        
        int len = nums.size();
        int reach_till = 0;
        
        for(int i=0; i<len;i++){
            
            if(reach_till < i) return false;
            
            reach_till = max(reach_till, i+ nums[i]);
        }
        return true;
    }
};

Leetcode Solution Submission

Question Name:

Find All Duplicates in an Array

Question URL:

https://leetcode.com/problems/find-all-duplicates-in-an-array/

Leetcode Question:

Find All Duplicates in an Array

Given an integer array nums of length n where all the integers of nums are in the range [1, n] and each integer appears once or twice, return an array of all the integers that appears twice.

You must write an algorithm that runs in O(n) time and uses only constant extra space.

Example 1:

Input: nums = [4,3,2,7,8,2,3,1]
Output: [2,3]

Example 2:

Input: nums = [1,1,2]
Output: [1]

Example 3:

Input: nums = [1]
Output: []

Constraints:

n == nums.length
1 <= n <= 105
1 <= nums[i] <= n
Each element in nums appears once or twice.

Date:

06/10/2021

Language:

Cpp

Solution:

class Solution {
public:
    vector<int> findDuplicates(vector<int>& nums) {
        //we can't use map or set as they take more space
        // one idea is to sort and check adjacent elements ut in that case time
        // complexity will be O(nlogn)
        //now it's given that numbers in array ae less than equal to length of array and all are positive
        // the idea is to traverse the array and go at the position of the number encounterd and make them negative, if they are already negative store abs value of n in another array as it will be going to the same position 2nd time.
        
        vector<int> results;
        for(int n:nums){
           
            if(nums[abs(n)-1] > 0) nums[abs(n)-1] *=-1;
            else
                results.push_back(abs(n));
            
        }
        return results;
        
    }
};

Leetcode Solution Submission

Question Name:

799. Champagne Tower

Question URL:

https://leetcode.com/problems/champagne-tower/

Leetcode Question:

We stack glasses in a pyramid, where the first row has 1 glass, the second row has 2 glasses, and so on until the 100th row. Each glass holds one cup of champagne.

Then, some champagne is poured into the first glass at the top. When the topmost glass is full, any excess liquid poured will fall equally to the glass immediately to the left and right of it. When those glasses become full, any excess champagne will fall equally to the left and right of those glasses, and so on. (A glass at the bottom row has its excess champagne fall on the floor.)

For example, after one cup of champagne is poured, the top most glass is full. After two cups of champagne are poured, the two glasses on the second row are half full. After three cups of champagne are poured, those two cups become full - there are 3 full glasses total now. After four cups of champagne are poured, the third row has the middle glass half full, and the two outside glasses are a quarter full, as pictured below.

Now after pouring some non-negative integer cups of champagne, return how full the jth glass in the ith row is (both i and j are 0-indexed.)

Date:

04/03/2022

Language:

Py

Solution:

  class Solution:
      def champagneTower(self, poured: int, query_row: int, query_glass: int) -> float:
          dp = [poured]
      
          for i in range(1,query_row+1):
              dp_new = [0] * (i+1)
              for j in range(i):
                  prev = max((dp[j] - 1) / 2, 0)
                  dp_new[j] += prev
                  dp_new[j+1] += prev
              dp = dp_new
              
          return min(dp[query_glass],1)

Leetcode Solution Submission

Question Name:

Guess Number Higher or Lower

Question URL:

https://leetcode.com/problems/guess-number-higher-or-lower/

Leetcode Question:

Guess Number Higher or Lower

We are playing the Guess Game. The game is as follows:

I pick a number from 1 to n. You have to guess which number I picked.

Every time you guess wrong, I will tell you whether the number I picked is higher or lower than your guess.

You call a pre-defined API int guess(int num), which returns 3 possible results:

 -1: The number I picked is lower than your guess (i.e. pick < num).
 1: The number I picked is higher than your guess (i.e. pick > num).
 0: The number I picked is equal to your guess (i.e. pick == num).

Return the number that I picked.

Example 1:

Input: n = 10, pick = 6
Output: 6

Example 2:

Input: n = 1, pick = 1
Output: 1

Example 3:

Input: n = 2, pick = 1
Output: 1

Example 4:

Input: n = 2, pick = 2
Output: 2

Date:

12/10/2021

Language:

Cpp

Solution:

/** 
 * Forward declaration of guess API.
 * @param  num   your guess
 * @return 	     -1 if num is lower than the guess number
 *		      1 if num is higher than the guess number
 *                    otherwise return 0
 * int guess(int num);
 */


class Solution {
public:
    int guessNumber(int n) {
        
        if(guess(n)==0) return n;
        if(guess(n)==-1) return guessNumber(n-1);
        return guessNumber(n+1);

    }
};

Leetcode Solution Submission

Question Name:

Word Search II

Question URL:

https://leetcode.com/problems/word-search-ii/

Leetcode Question:

Given an m x n board of characters and a list of strings words, return all words on the board.

Each word must be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.

Example 1:

Input: board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]], words = ["oath","pea","eat","rain"]
Output: ["eat","oath"]

Example 2:

Input: board = [["a","b"],["c","d"]], words = ["abcb"]
Output: []

Constraints:

m == board.length
n == board[i].length
1 <= m, n <= 12
board[i][j] is a lowercase English letter.
1 <= words.length <= 3 * 104
1 <= words[i].length <= 10
words[i] consists of lowercase English letters.
All the strings of words are unique.

Date:

09/10/2021

Language:

Py

Solution:

class Node:
    def __init__(self,c,end=False):
        self.child = {}
        self.c = c
        self.end = end
        
class Trie:
    def __init__(self):
        self.root = Node("/")
        
    def insert(self,word):
        cur = self.root
        for c in word:
            if c not in cur.child: cur.child[c] = Node(c)
            cur = cur.child[c]
        cur.end = True
                


class Solution:
    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
        lookup = Trie()
        for w in words:
            lookup.insert(w)
            
        def dfs(r,c,cur,word):
            if not (0<=r<n and 0<=c<m): return
            w = board[r][c]
            if w not in cur.child: return
            if cur.child[w].end:
                ans.add(word+w)
            board[r][c] = " "
            dfs(r+1,c,cur.child[w],word+w)
            dfs(r-1,c,cur.child[w],word+w)
            dfs(r,c+1,cur.child[w],word+w)
            dfs(r,c-1,cur.child[w],word+w)

            board[r][c] = w
            
        n = len(board)
        m = len(board[0])
        ans = set()
        
        for r in range(n):
            for c in range(m):
                dfs(r,c,lookup.root,"")
        
        return ans

Leetcode Solution Submission

Question Name:

Implement Trie (Prefix Tree)

Question URL:

https://leetcode.com/problems/implement-trie-prefix-tree/

Leetcode Question:

A trie (pronounced as "try") or prefix tree is a tree data structure used to efficiently store and retrieve keys in a dataset of strings. There are various applications of this data structure, such as autocomplete and spellchecker.

Implement the Trie class:

Trie() Initializes the trie object.
void insert(String word) Inserts the string word into the trie.
boolean search(String word) Returns true if the string word is in the trie (i.e., was inserted before), and false otherwise.
boolean startsWith(String prefix) Returns true if there is a previously inserted string word that has the prefix prefix, and false otherwise.

Example 1:

Input
["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
Output
[null, null, true, false, true, null, true]

Explanation
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple");   // return True
trie.search("app");     // return False
trie.startsWith("app"); // return True
trie.insert("app");
trie.search("app");     // return True

Constraints:

1 <= word.length, prefix.length <= 2000
word and prefix consist only of lowercase English letters.
At most 3 * 104 calls in total will be made to insert, search, and startsWith.

Date:

08/10/2021

Language:

Py

Solution:

class Node:
    def __init__(self,c,end=False):
        self.c = c
        self.child = {}
        self.end = end
        
class Trie:

    def __init__(self):
        self.root = Node("/")

    def insert(self, word: str) -> None:
        cur = self.root
        for c in word:
            if c not in cur.child: cur.child[c] = Node(c)
            cur = cur.child[c]
        cur.end = True

    def search(self, word: str) -> bool:
        cur = self.root
        for c in word:
            if c not in cur.child: return False
            cur = cur.child[c]
        return cur.end

    def startsWith(self, prefix: str) -> bool:
        cur = self.root
        for c in prefix:
            if c not in cur.child: return False
            cur = cur.child[c]
        return True


# Your Trie object will be instantiated and called as such:
# obj = Trie()
# obj.insert(word)
# param_2 = obj.search(word)
# param_3 = obj.startsWith(prefix)

Leetcode Solution Submission

Question Name:

Island Perimeter

Question URL:

https://leetcode.com/problems/island-perimeter/

Leetcode Question:

463. Island Perimeter

You are given row x col grid representing a map where grid[i][j] = 1 represents land and grid[i][j] = 0 represents water.

Grid cells are connected horizontally/vertically (not diagonally). The grid is completely surrounded by water, and there is exactly one island (i.e., one or more connected land cells).

The island doesn't have "lakes", meaning the water inside isn't connected to the water around the island. One cell is a square with side length 1. The grid is rectangular, width and height don't exceed 100. Determine the perimeter of the island.

Example 1:

Input: grid = [[0,1,0,0],[1,1,1,0],[0,1,0,0],[1,1,0,0]]
Output: 16
Explanation: The perimeter is the 16 yellow stripes in the image above.

Example 2:

Input: grid = [[1]]
Output: 4

Example 3:

Input: grid = [[1,0]]
Output: 4

Constraints:

• row == grid.length
• col == grid[i].length
• 1 <= row, col <= 100
• grid[i][j] is 0 or 1.
• There is exactly one island in grid.

Date:

04/10/2021

Language:

Py

Solution:

class Solution:
    def islandPerimeter(self, grid: List[List[int]]) -> int:
        n = len(grid)
        m = len(grid[0])
        ans = 0
        for r in range(n):
            for c in range(m):
                if grid[r][c] == 0: continue
                cur = 4
                if c+1<m and grid[r][c+1] == 1: cur-=1
                if r+1<n and grid[r+1][c] == 1: cur-=1
                if c-1>-1 and grid[r][c-1] == 1: cur-=1                   
                if r-1>-1 and grid[r-1][c] == 1: cur-=1
                ans+=cur
        
        return ans

Leetcode Solution Submission

Question Name:

Island Perimeter

Question URL:

https://leetcode.com/problems/island-perimeter/

Leetcode Question:

Island Perimeter

You are given row x col grid representing a map where grid[i][j] = 1 represents land and grid[i][j] = 0 represents water.

Grid cells are connected horizontally/vertically (not diagonally). The grid is completely surrounded by water, and there is exactly one island (i.e., one or more connected land cells).

The island doesn't have "lakes", meaning the water inside isn't connected to the water around the island. One cell is a square with side length 1. The grid is rectangular, width and height don't exceed 100. Determine the perimeter of the island.

Example 1:

Input: grid = [[0,1,0,0],[1,1,1,0],[0,1,0,0],[1,1,0,0]]
Output: 16
Explanation: The perimeter is the 16 yellow stripes in the image above.

Example 2:

Input: grid = [[1]]
Output: 4

Example 3:

Input: grid = [[1,0]]
Output: 4

Constraints:

row == grid.length
col == grid[i].length
1 <= row, col <= 100
grid[i][j] is 0 or 1.
There is exactly one island in grid.

Date:

04/10/2021

Language:

Cpp

Solution:

class Solution {
public:
    int islandPerimeter(vector<vector<int>>& grid) 
    {
        
        int result=0; 
        
        for(int i=0; i<grid.size(); i++)
        {
            for(int j=0; j<grid[0].size(); j++)
            {
                if(grid[i][j])
                {
                    result+=4;
                    
                    if(i>0 && grid[i-1][j]) 
                        result-=2;
                    if(j>0 && grid[i][j-1]) 
                        result-=2;
                }
            }
        }
        return result;
    }
};

Leetcode Solution Submission

Question Name:

Word Search

Question URL:

https://leetcode.com/problems/word-search/

Leetcode Question:

Word Search

Given an m x n grid of characters board and a string word, return true if word exists in the grid.

The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once.

Example 1:

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
Output: true

Example 2:

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
Output: true

Example 3:

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
Output: false

Constraints:

m == board.length
n = board[i].length
1 <= m, n <= 6
1 <= word.length <= 15
board and word consists of only lowercase and uppercase English letters.

Follow up: Could you use search pruning to make your solution faster with a larger board?

Date:

07/10/2021

Language:

Cpp

Solution:

class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) {
         int len = board.size(), ans =0;
        for(int i = 0; i<len;i++){
            for(int j=0; j<board[0].size();j++){
                // if((board[i][j] == word.at(0)) && solve(board, i, j, 0, word))
                //     return true;
                ans += solve(i, j, word, board, 0);
                if(ans > 0) return true;
            }
            
        }
        
    return false;

   }
    
    // bool solve (vector<vector<char>>& board, int i, int j, int count, string &word)
     int solve (int i, int j, string word, vector<vector<char>>& board, int count)
    {
       
         int found =0;
         if(i>=0 and j>=0 and i< board.size() and j < board[0].size() and word[count] == board[i][j] )
         {
             char temp = word[count];
             board[i][j] ='*';
             
             count++;
             if(count == word.size()) found +=1;
         
             else{
                 found += solve(i+1, j, word, board, count);
                 found += solve(i-1, j, word, board, count);
                 found += solve(i, j+1, word, board, count);
                 found += solve(i, j-1, word, board, count);

             }
             board[i][j] = temp;
             
         }
         return found;
    
}
};

Leetcode Solution Submission

Question Name:

Island Perimeter

Question URL:

https://leetcode.com/problems/island-perimeter/

Leetcode Question:

463. Island Perimeter

You are given row x col grid representing a map where grid[i][j] = 1 represents land and grid[i][j] = 0 represents water.

Grid cells are connected horizontally/vertically (not diagonally). The grid is completely surrounded by water, and there is exactly one island (i.e., one or more connected land cells).

The island doesn't have "lakes", meaning the water inside isn't connected to the water around the island. One cell is a square with side length 1. The grid is rectangular, width and height don't exceed 100. Determine the perimeter of the island.

Example 1:

Input: grid = [[0,1,0,0],[1,1,1,0],[0,1,0,0],[1,1,0,0]]
Output: 16
Explanation: The perimeter is the 16 yellow stripes in the image above.

Example 2:

Input: grid = [[1]]
Output: 4

Example 3:

Input: grid = [[1,0]]
Output: 4

Constraints:

• row == grid.length
• col == grid[i].length
• 1 <= row, col <= 100
• grid[i][j] is 0 or 1.
• There is exactly one island in grid.

Date:

04/10/2021

Language:

Py

Solution:

class Solution:
    def islandPerimeter(self, grid: List[List[int]]) -> int:
        n = len(grid)
        m = len(grid[0])
        
        def dfs(x,y):
            if not (0<=x<n and 0<=y<m) or grid[x][y] == 0:
                return 1
            if grid[x][y] == -1:
                return 0
            grid[x][y] = -1
            paths = [(0,1),(0,-1),(1,0),(-1,0)]
            return sum(dfs(x+i,y+j) for i,j in paths)
        
        for r in range(n):
            for c in range(m):
                if grid[r][c]: return dfs(r,c)