773. Sliding Puzzle
source
Topic: BFS
Time Complexity: (n*m)!
Solution 01
class Solution{public: int slidingPuzzle (vector<vector<int>>& board) { constexpr int row = 2; constexpr int col = 3; string goal, start; ...
Showing posts with label LeetCode. Show all posts
Showing posts with label LeetCode. Show all posts
771. Jewels and Stones
771. Jewels and Stones
Solution 01:
Complexity: O(N^2)
class Solution {public: int numJewelsInStones(string J, string S) { int cnt = 0; for(int i = 0; i < S.size(); i++){ for(int k = 0; k < J.size(); k++){ ...
Minimize Max Distance to Gas Station
Minimize Max Distance to Gas Station
#include<bits/stdc++.h>using namespace std;struct Interval{ Interval (int d): num(d), den(1), dist(d){} bool operator< (const Interval &d) const {return dist < d.dist;} double num,den, dist; void update(){den++, dist = num/den;}};template<typename T>priority_queue<T>...
779. K-th Symbol in Grammar
779. K-th Symbol in Grammar
Nth row = (N-1)th row + (n-1)th Inverse.
Example;
1st row = 0
2nd row = 1st row + 1st row Inverse (01)
Every row will power of two.
Solution:
class Solution {public: int kthGrammar (int N, int k){ long s = 1 << (N - 1), flips = 0; while(s > 2){ if(k >...
SpliBST
SplitBST
It's a premium problem. So it's not tested;
Solution:
vector<TreeNode*> SplitBST(TreeNode* root, int V){ vector<TreeNode*> ans (2, nullptr) if(root == nullptr) return ans; int x = root->val > V ? 1 : 0; int y = root->val > V ? 0 : 1; auto& node = root->val > V ? root->left...
778. Swim in Rising Water
778. Swim in Rising Water
Complexity: O(n^2)
Topic: Flood Fill
Solution:
class Solution {public: using vi = vector<int>;struct pos{ pos(int a, int b, int c) : val(a), x (b), y(c) {} bool operator< (const pos &d) const {return val > d.val;} int val, x,y;};vi nx = {1,-1,0,0};vi ny = {0,...
786. K-th Smallest Prime Fraction
786. K-th Smallest Prime Fraction
Complexity: O(n*log(k))
Solution 1:
class Solution {public: struct fraction{ double val; int i,j; fraction(double d, int x, int y) : val(d), i(x), j(y){} bool operator< (const fraction& f)const{ return val > f.val;}};vector<int> kthSmallestPrimeFraction(vector<int>&...
790. Domino and Tromino Tiling
790. Domino and Tromino Tiling
Topic: DP
complexity: O(n)
Solution:
Code:
class Solution {public: int numTilings(int N) { const int MOD = 1e9 + 7;vector<long> dp = {0, 1, 2, 5};dp.resize...
795. Number of Subarrays with Bounded Maximum
795. Number of Subarrays with Bounded Maximum
Complexity: O(n)
Solution 1:
int numSubarrayBoundedMax(const vector<int>& A, int l, int r){ int result = 0, start = -1, end = -1; for(int i = 0; i < A.size(); i++){ if(A[i] >r)start = i; if(A[i] >= l)end = i; ...
802. Find Eventual Safe States
802. Find Eventual Safe States
Solution: DFS
concept:
যেই নোডগুলোতে সাইকেল নাই ওই গুলা প্রিন্ট করতে হবে।
Code:
class Solution {public: unordered_set<int> cycle_nodes, safe_nodes; bool dfs(vector<vector<int>>& g, int i, unordered_set<int>visited_nodes) ...
801. Minimum Swaps To Make Sequences Increasing
801. Minimum Swaps To Make Sequences Increasing
Solution:
class Solution {public: int minSwap(vector<int>& A, vector<int>& B){ int n = A.size(); vector<int> X(n,0); vector<int> Y(n,1); for(int i = 1; i < n; i++){ X[i] = Y[i] = n; ...
805. Split Array With Same Average
805. Split Array With Same Average
Topic: pruning + DP.
Copmplexity: O(n^3).
Soltion:
Code:
class Solution {public: bool is_possible(int m, int sum, int n){ bool possible = false; for(int i = 1; i <= m; i++) ...
Bus Routes
815. Bus Routes
complexity : O(n)
Topic: BFS
Eplanation
class Solution { #include<bits/stdc++.h>public: int numBusesToDestination(vector<vector<int> >& routes, int S, int T){ unordered_map<int, unordered_set<int>...
Consecutive Numbers Sum
829. Consecutive Numbers Sum
O( sqrt(N) )
Solution:
Code:
class Solution {public: int consecutiveNumbersSum(int N){ int ans = 0; for(int n = 2; n*(n+1)/2 <= N; ++n){ if(...
Shortest Bridge
934. Shortest Bridge
Problem Type: Recursion; Flood Fill.
Code:
using island = set<pair<int, int> >;using vi = vector<int>;using vvi = vector<vi>;class Solution{public: int n; vi dx = {0, 0, 1, -1}; vi dy = {1, -1, 0, 0}; bool is_valid(int x, int y){ ...
Groups of Special-Equivalent Strings
893. Groups of Special-Equivalent Strings
CODE:
class Solution {
public:
int numSpecialEquivGroups(vector<string>& A) {
unordered_set<string> s;
for(const auto& w: A){
...
Minimum Falling Path Sum
931. Minimum Falling Path Sum
1 2 3 4 ------------- 1 2 3 4
4 -1 3 -2 ------------- 5 0 5 1
-2 5 -3 2 ------------- -2 4 -3 3
7 -6 9 8 -------------...