Hi All, Good Morning !!!
I will post Leetcode Daily Problem and GFG POD here, apart from that you can find the resources for coding.

GFG | Problem Of The Day [2022-12-12]

🎯 Problem Statement:
Find minimum number of Laptops required

🎲 Test Cases:
Input:
N = 3
start[] = {1, 2, 3}
end[] = {4, 4, 6}
Output:
3
Explanation:
We can clearly see that everyone's supposed to be doing their job at time 3. So, 3 laptops will be required at minimum.

♟ Approach:
we can observe that every time we start work we need a computer and every time we end our work we free the computer. So basically we can keep a counter every time we encounter a start we increase no. of computers and every time we encounter the end we decrease no. of computers. and for each state we can maintain a variable that can keep track of max. computers required at a time.

For this approach, we should have a start time and end time in sorted order so we can pick which one is the minimum.

🏆 Code:
class Solution {
public int minLaptops(int n, int[] start, int[] end) {
Arrays.sort(start);
Arrays.sort(end);
int total = 0;
int max = 0;
int i = 0;
int j = 0;
while(i < n && j < n) {
if(start[i] < end[j]) {
i++;
total++;
} else {
j++;
total--;
}
max = Math.max(max, total);
}
return max;
}
}

🏎 Time Complexity: O(N logN) due to sorting
🚎 Space Complexity: O(1) no extra space

📌 Blog Link: https://vikasss7663.medium.com/find-minimum-number-of-laptops-required-7b402680c6c8

Leetcode | Daily Leetcode Challenge [2022-12-12]

🎯 Problem Statement:
980. Unique Paths III

🎲 Test Cases:
Input: grid = [[1,0,0,0],[0,0,0,0],[0,0,2,-1]]
Output: 2
Explanation: We have the following two paths:
1. (0,0),(0,1),(0,2),(0,3),(1,3),(1,2),(1,1),(1,0),(2,0),(2,1),(2,2)
2. (0,0),(1,0),(2,0),(2,1),(1,1),(0,1),(0,2),(0,3),(1,3),(1,2),(2,2)

♟ Approach:
The problem is the same as finding Unique Paths that we can find using DFS ( Depth First Search ). but only one twist is there and that is we should traverse all empty cells.

So first we count the empty cells and when we reach the final destination we check whether the empty cell count equal to 0 or not.

Once we leave the cell we mark it as unvisited and increase empty cells by 1.

🏆 Code:
class Solution {
public int uniquePathsIII(int[][] grid) {
int totalEmptyCells = 0;
int startRow = -1;
int startCol = -1;
for(int i=0;i<grid.length;i++) {
for(int j=0;j<grid[0].length;j++) {
if(grid[i][j] == 1) {
startRow = i;
startCol = j;
} else if(grid[i][j] == 0)
totalEmptyCells++;
}
}

return countPaths(grid, startRow, startCol, totalEmptyCells);
}

public int countPaths(int[][] grid, int startRow, int startCol, int totalEmptyCells) {
int m = grid.length;
int n = grid[0].length;
boolean[][] visited = new boolean[m][n];

return dfs(grid, startRow, startCol, m, n, visited, totalEmptyCells+1);
}

public int dfs(int[][] grid, int i, int j, int m, int n, boolean[][] visited, int totalEmptyCells) {

if(i<0) return 0;
if(j<0) return 0;
if(i>=m) return 0;
if(j>=n) return 0;

if(grid[i][j] == -1) return 0; // blocker

if(visited[i][j]) return 0; // already visited

if(grid[i][j] == 2) { // reached finish state
if(totalEmptyCells == 0) return 1;
return 0;
}

visited[i][j] = true;
totalEmptyCells--;

int ans = 0;
ans += dfs(grid, i+1, j, m, n, visited, totalEmptyCells);
ans += dfs(grid, i-1, j, m, n, visited, totalEmptyCells);
ans += dfs(grid, i, j+1, m, n, visited, totalEmptyCells);
ans += dfs(grid, i, j-1, m, n, visited, totalEmptyCells);

totalEmptyCells++;
visited[i][j] = false;
return ans;
}
}

📌 Blog Link: https://vikasss7663.medium.com/unique-paths-iii-b0feb87ebe6b

GFG | Problem Of The Day [2023-01-01]

🎯 Problem Statement:
Count even length
Given a number n, find count of all binary sequences of length 2n such that sum of first n bits is same as sum of last n bits.
The answer can be very large. So, you have to return answer modulo 10^9+7.

🎲 Test Cases:
Input: n = 2
Output: 6
Explanation: There are 6 sequences of length
2*n, the sequences are 0101, 0110, 1010, 1001,
0000 and 1111.

♟ Approach:
we can see that total combination =
for i -> o to n
(No. of combinations having i no. of 1s)^2

Now challenge is to know no. of combinations having k no. of 1s.
( where 0 <= k <= n )

If you know mathematics that's very easy because we have n position where we can put k 1s so it is C(n, k)

Now take an example n = 3
Total Combinations
= C(3,0)^2 + C(3,1)^2 + C(3,2)^2 + C(3,3)^2
= 1^2 + 3^2 + 3^2 + 1^2
= 1 + 9 + 9 + 1
= 20

Now take an example n = 2
Total Combinations
= C(2,0)^2 + C(2,1)^2 + C(2,2)^2
= 1^2 + 2^2 + 1^2
= 1 + 4 + 1
= 6

🏆 Code:
class Solution {
public long power(long x, long y, long p) {
long res = 1l;
x = x % p;
while (y > 0) {
if (y % 2 == 1)
res = (res * x) % p;
y = y >> 1;
x = (x * x) % p;
}
return res;
}

public long modInverse(long n, long p) {
return power(n, p - 2, p);
}

public int compute_value(int n) {
// code here
long ans = 1l;
long mod = (long)(Math.pow(10, 9) + 7l);
long compute = 1l;
for(int i=0;i<n;i++) {
compute = (compute%mod * (long)(n-i)%mod) % mod;
compute = (compute%mod * modInverse(i+1, mod)%mod) % mod;
ans = (ans%mod + (compute%mod*compute%mod)%mod) % mod;
}
return (int)(ans%mod);
}
}

🏎 Time Complexity: O(N logN) because we are calculating power in each iteration which takes O(logN) time.
🚎 Space Complexity: O(1) no extra space


📌 Blog Link: https://vikasss7663.medium.com/count-even-length-e14b981f79c8

Happy New Year !!!

Leetcode | Daily Leetcode Challenge [2022-01-01]

🎯 Problem Statement:
290. Word Pattern
Given a pattern and a string s, find if s follows the same pattern.
Here follow means a full match, such that there is a bijection between a letter in pattern and a non-empty word in s.

🎲 Test Cases:
Example 1:
Input: pattern = "abba", s = "dog cat cat dog"
Output: true

Example 2:
Input: pattern = "abba", s = "dog cat cat fish"
Output: false

Example 3:
Input: pattern = "aaaa", s = "dog cat cat dog"
Output: false

♟ Approach:
As we know that
“abba” -> “dog cat cat dog”
‘a’ -> “dog”
‘b’ -> “cat”
if we encounter a map with a different string then we can say it’s not a valid test case.
“abfa” -> “dog cat dog dog”
‘a’ -> “dog”
‘b’ -> “cat”
‘f’ -> “dog”
but the dog is already assigned to a. So we use two maps one will do mapping with a -> dog and another map will do mapping with dog -> a so that we know the dog is already being mapped with another character.

🏆 Code:
class Solution {
public boolean wordPattern(String pattern, String s) {
String[] tokens = s.split(" ");

if(pattern.length() != tokens.length)
return false;

HashMap<String, Character> map = new HashMap<>();
HashMap<Character, String> reverseMap = new HashMap<>();

for(int i=0;i<tokens.length;i++) {
String find = tokens[i];
char pt = pattern.charAt(i);

if(!map.containsKey(find))
map.put(find, pt);
if(!reverseMap.containsKey(pt))
reverseMap.put(pt, find);

char mapPt = map.get(find);
String mapStr = reverseMap.get(pt);

if(mapPt != pt)
return false;
if(!mapStr.equals(find))
return false;
}
return true;
}
}

🏎 Time Complexity: O(max(M,N)) where m is the length of pattern and n is the length of s
🚎 Space Complexity: O(N) storing mapping in two maps


📌 Blog Link: https://vikasss7663.medium.com/word-pattern-919ccf5da9c8

GFG | Problem Of The Day [2023-01-02]

🎯 Problem Statement:
Maximum Value
Given a binary tree, find the largest value in each level.

🎲 Test Cases:
Example 1:
Input:
1
/ \
2 3
Output:
1 3
Explanation:
At 0 level, values of nodes are {1}
Maximum value is 1
At 1 level, values of nodes are {2,3}
Maximum value is 3

♟ Approach:
For every level, we check the existing value for that level and update if the current node’s value is maximum.

We are using preorder traversal so that we go level by level and append new level’s data.

🏆 Code:
class Solution {
ArrayList<Integer> res;

ArrayList<Integer> maximumValue(Node node) {
//code here
res = new ArrayList<>();
preorderTraversal(node, 0);
return res;
}

void preorderTraversal(Node node, int depth) {
if(node == null) return;
if(res.size() <= depth) {
res.add(node.data);
} else {
int stored = res.get(depth);
if(node.data > stored) {
res.remove(depth);
res.add(depth, node.data);
}
}
preorderTraversal(node.left, depth+1);
preorderTraversal(node.right, depth+1);
}
}

🏎 Time Complexity: O(N) wher N is no. of nodes in tree
🚎 Space Complexity: O(D) where D is depth of tree


📌 Blog Link: https://vikasss7663.medium.com/maximum-value-738f8e4bff45

Leetcode | Daily Leetcode Challenge [2022-01-02]

🎯 Problem Statement:
Detect Capital
We define the usage of capitals in a word to be right when one of the following cases holds:

All letters in this word are capitals, like "USA".
All letters in this word are not capitals, like "leetcode".
Only the first letter in this word is capital, like "Google".
Given a string word, return true if the usage of capitals in it is right.

🎲 Test Cases:
Example 1:
Input: word = "USA"
Output: true

Example 2:
Input: word = "FlaG"
Output: false

♟ Approach:
I will give you a couple of scenarios regarding this

“Flag” [ Valid ]
“fLAG” [ InValid ]
“FLAG” [ Valid ]
“flag” [ Valid ]
“fLAg” [ InValid ]
so we care about the type of first letter and the count of each type of letter.

🏆 Code:
class Solution {

public boolean isUpperCase(char x) {
return x >= 'A' && x <= 'Z';
}

public boolean detectCapitalUse(String word) {
int n = word.length();

if(n == 0) return true;

boolean firstUpperCase = isUpperCase(word.charAt(0));
int upperCaseCount = 0;
int lowerCaseCount = 0;

for(int i=1;i<n;i++) {
char x = word.charAt(i);
if(isUpperCase(x)) {
upperCaseCount++;
} else {
lowerCaseCount++;
}
}

if(!firstUpperCase && upperCaseCount > 0) return false;
if(lowerCaseCount > 0 && upperCaseCount > 0) return false;

return true;
}
}

🏎 Time Complexity: O(N)
🚎 Space Complexity: O(1)


📌 Blog Link: https://vikasss7663.medium.com/detect-capital-1891cc7c483b

After a long time guys, but I will provide this months problem solution everyday.

GFG | Problem of The Day [ 01 August 2023 ]

🏆 Code:
class Solution {
// Function to return a list containing the DFS traversal of the graph.
public ArrayList<Integer> dfsOfGraph(int V, ArrayList<ArrayList<Integer>> adj) {
// Code here
boolean[] visited = new boolean[V];
return solve(V, adj, 0, visited);
}

public ArrayList<Integer> solve(int V, ArrayList<ArrayList<Integer>> adj, int ind,
boolean[] visited) {
ArrayList<Integer> curr = new ArrayList<>();
if(ind >= adj.size() || visited[ind]) return curr;
curr.add(ind);
visited[ind] = true;
for(int x: adj.get(ind)) {
if(!visited[x]) {
curr.addAll(solve(V, adj, x, visited));
}
}
return curr;
}
}

Leetcode | Daily Leetcode Challenge [ 01 August 2023 ]

🏆 Code:
class Solution {

List<List<Integer>> res = new ArrayList<>();

public List<List<Integer>> combine(int n, int k) {
solve(0, n, k, new ArrayList<>());
return res;
}

public void solve(int ind, int n, int k, List<Integer> curr) {
if(ind > n) {
return;
}
if(k == 0) {
res.add(new ArrayList<>(curr));
return;
}
for(int i=ind+1;i<=n;i++) {
curr.add(i);
solve(i, n, k-1, curr);
curr.remove(curr.size()-1);
}
}
}