Weekly Contest 300 LeetCode Solution

Problem 1 – Decode the Message LeetCode Solution

You are given the strings key and message, which represent a cipher key and a secret message, respectively. The steps to decode message are as follows:

  1. Use the first appearance of all 26 lowercase English letters in key as the order of the substitution table.
  2. Align the substitution table with the regular English alphabet.
  3. Each letter in message is then substituted using the table.
  4. Spaces ' ' are transformed to themselves.
  • For example, given key = "happy boy" (actual key would have at least one instance of each letter in the alphabet), we have the partial substitution table of ('h' -> 'a''a' -> 'b''p' -> 'c''y' -> 'd''b' -> 'e''o' -> 'f').

Return the decoded message.

Example 1:

Input: key = "the quick brown fox jumps over the lazy dog", message = "vkbs bs t suepuv"
Output: "this is a secret"
Explanation: The diagram above shows the substitution table.
It is obtained by taking the first appearance of each letter in "the quick brown fox jumps over the lazy dog".

Example 2:

Input: key = "eljuxhpwnyrdgtqkviszcfmabo", message = "zwx hnfx lqantp mnoeius ycgk vcnjrdb"
Output: "the five boxing wizards jump quickly"
Explanation: The diagram above shows the substitution table.
It is obtained by taking the first appearance of each letter in "eljuxhpwnyrdgtqkviszcfmabo".

Constraints:

  • 26 <= key.length <= 2000
  • key consists of lowercase English letters and ' '.
  • key contains every letter in the English alphabet ('a' to 'z'at least once.
  • 1 <= message.length <= 2000
  • message consists of lowercase English letters and ' '.

Decode the Message LeetCode Solution in C++

string decodeMessage(string key, string mess) {
    char m[128] = {}, cur = 'a';
    for (char k : key)
        if (isalpha(k) && m[k] == 0)
            m[k] = cur++;
    for (int i = 0; i < mess.size(); ++i)
        mess[i] = m[mess[i]] ?: mess[i];
    return mess;
}

Decode the Message LeetCode Solution in Java

class Solution {
    public String decodeMessage(String key, String message) {
        StringBuilder ans = new StringBuilder();//Using String Builder to append the string
        key = key.replaceAll(" ", "");
        //Removing the spaces
        HashMap<Character,Character> letters = new HashMap<>();
        //Mapping the key into a hashmap.
        char original = 'a';
        for (int i = 0; i < key.length() ; i++) {
            if (!letters.containsKey(key.charAt(i))){
                letters.put(key.charAt(i),original++);
            }
        }
        //After the first pass all the letters of the key will be mapped with their respective original letters.
        for (int i = 0; i < message.length(); i++) {
            if (letters.containsKey(message.charAt(i))){
                //Now replacing the letters of the message with appropriate letter according to the key
                ans.append(letters.get(message.charAt(i)));
            }else{
                ans.append(message.charAt(i));
                //This is for characters other than the letters in the key example a space " "
                //They will not be replaced by any letters hence original letter is appended into the StringBuilder
            }
        }
        return ans.toString();
    }
}

Decode the Message LeetCode Solution in Python

class Solution:
    def decodeMessage(self, key: str, message: str) -> str:
        alpha = ['a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z']
        i=0
        d={}
        for j in key:
            if j!=" " and j not in d:
                d[j]=alpha[i]
                i+=1
            if len(d)==26:
                break
        res=""
        d[" "]=" "
        for i in message:
            res+=d[i]
        return res

Problem 2 – Spiral Matrix IV LeetCode Solution

You are given two integers m and n, which represent the dimensions of a matrix.

You are also given the head of a linked list of integers.

Generate an m x n matrix that contains the integers in the linked list presented in spiral order (clockwise), starting from the top-left of the matrix. If there are remaining empty spaces, fill them with -1.

Return the generated matrix.

Example 1:

Input: m = 3, n = 5, head = [3,0,2,6,8,1,7,9,4,2,5,5,0]
Output: [[3,0,2,6,8],[5,0,-1,-1,1],[5,2,4,9,7]]
Explanation: The diagram above shows how the values are printed in the matrix.
Note that the remaining spaces in the matrix are filled with -1.

Example 2:

Input: m = 1, n = 4, head = [0,1,2]
Output: [[0,1,2,-1]]
Explanation: The diagram above shows how the values are printed from left to right in the matrix.
The last space in the matrix is set to -1.

Constraints:

  • 1 <= m, n <= 105
  • 1 <= m * n <= 105
  • The number of nodes in the list is in the range [1, m * n].
  • 0 <= Node.val <= 1000

Spiral Matrix IV LeetCode Solution in C++

vector<vector<int>> spiralMatrix(int m, int n, ListNode* head) {
    int i = 0, j = 0, cur_d = 0, d[5] = {0, 1, 0, -1, 0};
    vector<vector<int>> res(m, vector<int>(n, -1));
    for (; head != nullptr; head = head->next) {
        res[i][j] = head->val;
        int ni = i + d[cur_d], nj = j + d[cur_d + 1];
        if (min(ni, nj) < 0 || ni >= m || nj >= n || res[ni][nj] != -1)
            cur_d = (cur_d + 1) % 4;
        i += d[cur_d];
        j += d[cur_d + 1];
    }
    return res;
}

Spiral Matrix IV LeetCode Solution in Python

class Solution:
    def spiralMatrix(self, m: int, n: int, head: Optional[ListNode]) -> List[List[int]]:
        num = m * n
        res = [[-1 for j in range(n)] for i in range(m)]
        x, y = 0, 0
        dx, dy = 1, 0
        while head:
            res[y][x] = head.val
            if x + dx < 0 or x + dx >= n or y + dy < 0 or y + dy >= m or res[y+dy][x+dx] != -1:
                dx, dy = -dy, dx
            x = x + dx
            y = y + dy
            head = head.next
        return res

Spiral Matrix IV LeetCode Solution in Java


class Solution {
    public int[][] spiralMatrix(int m, int n, ListNode head) {
        int[][] result = new int[m][n];
        int top =0;
        int bottom = m-1;
        int left =0; 
        int right = n-1;
        int len = m*n;
        int count =0;
        int val=0;
        while(count<len){
            //Top
            for(int i = left; i<=right && count<len; i++){
                if(head !=null) {
                    val = head.val;
                    head=head.next;
                } else val=-1;
                result[top][i] = val;
                count++;
            }
            top++;
            // right
            for(int i = top; i<=bottom && count<len; i++){
                if(head !=null) {
                    val = head.val;
                    head=head.next;
                } else val=-1;
                result[i][right] = val;
                count++;
            }
            right--;
            // bottom
            for(int i = right; i>=left && count<len; i--){
                if(head !=null) {
                    val = head.val;
                    head=head.next;
                } else val=-1;
                result[bottom][i] = val;
                count++;
            }
            bottom--;
           // left
            for(int i = bottom; i>=top && count<len; i--){
                if(head !=null) {
                    val = head.val;
                    head=head.next;
                } else val=-1;
                result[i][left] = val;
                count++;
            }
            left++;            
        }
        
        return result;
    }

Problem 3 – Number of People Aware of a Secret LeetCode Solution

On day 1, one person discovers a secret.

You are given an integer delay, which means that each person will share the secret with a new person every day, starting from delay days after discovering the secret. You are also given an integer forget, which means that each person will forget the secret forget days after discovering it. A person cannot share the secret on the same day they forgot it, or on any day afterwards.

Given an integer n, return the number of people who know the secret at the end of day n. Since the answer may be very large, return it modulo 109 + 7.

Example 1:

Input: n = 6, delay = 2, forget = 4
Output: 5
Explanation:
Day 1: Suppose the first person is named A. (1 person)
Day 2: A is the only person who knows the secret. (1 person)
Day 3: A shares the secret with a new person, B. (2 people)
Day 4: A shares the secret with a new person, C. (3 people)
Day 5: A forgets the secret, and B shares the secret with a new person, D. (3 people)
Day 6: B shares the secret with E, and C shares the secret with F. (5 people)

Example 2:

Input: n = 4, delay = 1, forget = 3
Output: 6
Explanation:
Day 1: The first person is named A. (1 person)
Day 2: A shares the secret with B. (2 people)
Day 3: A and B share the secret with 2 new people, C and D. (4 people)
Day 4: A forgets the secret. B, C, and D share the secret with 3 new people. (6 people)

Constraints:

  • 2 <= n <= 1000
  • 1 <= delay < forget <= n

Number of People Aware of a Secret LeetCode Solution in Java

    public int peopleAwareOfSecret(int n, int delay, int forget) {
        long dp[] = new long[n + 1], mod = (long)1e9 + 7, share = 0, res = 0;
        dp[1] = 1;
        for (int i = 2; i <= n; ++i)
            dp[i] = share = (share + dp[Math.max(i - delay, 0)] - dp[Math.max(i - forget, 0)] + mod) % mod;
        for (int i = n - forget + 1; i <= n; ++i)
            res = (res + dp[i]) % mod;
        return (int)res;
    }

Number of People Aware of a Secret LeetCode Solution in C++

    int peopleAwareOfSecret(int n, int delay, int forget) {
        vector<long> dp(n + 1);
        dp[1] = 1;
        int share = 0, mod = 1e9 + 7, res = 0 ;
        for (int i = 2; i <= n; ++i)
            dp[i] = share = (share + dp[max(i - delay, 0)] - dp[max(i - forget, 0)] + mod) % mod;
        for (int i = n - forget + 1; i <= n; ++i)
            res = (res + dp[i]) % mod;
        return res;
    }

Number of People Aware of a Secret LeetCode Solution in Python

    def peopleAwareOfSecret(self, n, delay, forget):
        dp = [1] + [0] * (n - 1)
        mod = 10 ** 9 + 7
        share = 0
        for i in range(1, n):
            dp[i] = share = (share + dp[i - delay] - dp[i - forget]) % mod
        return sum(dp[-forget:]) % mod

Problem 4 – Number of Increasing Paths in a Grid LeetCode Solution

You are given an m x n integer matrix grid, where you can move from a cell to any adjacent cell in all 4 directions.

Return the number of strictly increasing paths in the grid such that you can start from any cell and end at any cell. Since the answer may be very large, return it modulo 109 + 7.

Two paths are considered different if they do not have exactly the same sequence of visited cells.

Example 1:

Input: grid = [[1,1],[3,4]]
Output: 8
Explanation: The strictly increasing paths are:
- Paths with length 1: [1], [1], [3], [4].
- Paths with length 2: [1 -> 3], [1 -> 4], [3 -> 4].
- Paths with length 3: [1 -> 3 -> 4].
The total number of paths is 4 + 3 + 1 = 8.

Example 2:

Input: grid = [[1],[2]]
Output: 3
Explanation: The strictly increasing paths are:
- Paths with length 1: [1], [2].
- Paths with length 2: [1 -> 2].
The total number of paths is 2 + 1 = 3.

Constraints:

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 1000
  • 1 <= m * n <= 105
  • 1 <= grid[i][j] <= 105

Number of Increasing Paths in a Grid LeetCode Solution in C++

static int MOD=1e9+7;
static vector<int> dirs={0,1,0,-1,0};
class Solution {
public:
    vector<vector<long>> memo;
    long dp(vector<vector<int>>& grid,int i,int j) {
        long result=1;  // Contribution of current cell as an increasing sequence.
        if(memo[i][j]!=-1)  // Return the cached results if they exist.
            return memo[i][j];
        for(int d=0;d<4;d++) {  // Check all 4 directions.
            int x=i+dirs[d],y=j+dirs[d+1];
            if(x>=0&&y>=0&&x<grid.size()&&y<grid[0].size()&&grid[x][y]>grid[i][j])
                result=(result+dp(grid,x,y))%MOD;       // Add the total number of cells in the longest path for all directions.
        }
        return memo[i][j]=result;
    }
    int countPaths(vector<vector<int>>& grid) {
        long result=0;
        memo.resize(grid.size(),vector<long>(grid[0].size(),-1));
        for(int i=0;i<grid.size();i++)      // For each cell as a starting point calculate the number of increasing paths it can contribute.
            for(int j=0;j<grid[0].size();j++)
                result=(result+dp(grid,i,j))%MOD;
        return result;
    }
};

Number of Increasing Paths in a Grid LeetCode Solution in Python

def countPaths(self, A: List[List[int]]) -> int:
    m, n, mod, dirs = len(A), len(A[0]), (10 ** 9) + 7, [(0, 1), (1, 0), (-1, 0), (0, -1)]
    @cache
    def dp(i, j):
        return sum((1 + dp(i + x, j + y)) for x, y in dirs if 0 <= i + x < m and 0 <= j + y < n and A[i + x][j + y] > A[i][j]) % mod
    return (sum(dp(i, j) % mod for i in range(m) for j in range(n)) + (m * n)) % mod

Number of Increasing Paths in a Grid LeetCode Solution in Java

    long mod=1000000007;
    long dp[][];
    public int countPaths(int[][] grid) {
        
        int n=grid.length,m=grid[0].length;
        dp=new long[n][m];
        long ans=0;
       for(int i=0;i<n;i++){
           for(int j=0;j<m;j++){

               ans=(ans+find(i,j,grid))%mod;
               ans=(ans+mod)%mod;
           }
       }
        return (int)(ans%1000000007);
    }
    int dir[][]={{-1,0},{1,0},{0,1},{0,-1}};
     long find(int i,int j,int grid[][]){

        if(dp[i][j]!=0) return dp[i][j];

        long ans=1;
        for(int k=0;k<4;k++){
            int i1=i+dir[k][0],j1=j+dir[k][1];

            if(i1<0 || j1<0 || i1==dp.length || j1==dp[0].length || grid[i][j]<=grid[i1][j1])
             continue;

            ans=(ans+find(i1,j1,grid))%mod;
        }
        ans=(ans+mod)%mod;
        return dp[i][j]=(ans);
    }
Weekly Contest 300 LeetCode Solution Review:

In our experience, we suggest you solve this Weekly Contest 300 LeetCode Solution and gain some new skills from Professionals completely free and we assure you will be worth it.

If you are stuck anywhere between any coding problem, just visit Queslers to get the Weekly Contest 300 LeetCode Solution

Find on LeetCode

Conclusion:

I hope this Weekly Contest 300 LeetCode Solution would be useful for you to learn something new from this problem. If it helped you then don’t forget to bookmark our site for more Coding Solutions.

This Problem is intended for audiences of all experiences who are interested in learning about Data Science in a business context; there are no prerequisites.

Keep Learning!

More Coding Solutions >>

LeetCode Solutions

Hacker Rank Solutions

CodeChef Solutions

Leave a Reply

Your email address will not be published.