773. Sliding Puzzle

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;
    for(int i = 0; i  < board.size(); i++)
      for(int j = 0; j < board[0].size(); j++){
        start += (board[i][j] + '0');
        goal += (i*col + j + 1) % (row*col) + '0';//12345.....0
      }
      if (start == goal) return 0;

      constexpr int dirs[4][2] = {{-1,0}, {1,0}, {0,1}, {0, -1}};

      set<string> visited{start};
      int steps = 0;
      queue<string>Q;
      Q.push(start);
      while (!Q.empty()){
        steps++;
        int sz = Q.size();
        while(sz-- > 0){
        string s = Q.front();
        Q.pop();
        int p = s.find('0');
        int y = p/col;
        int x = p%col;
        for(int i = 0; i < 4; i++){
          int tx = x + dirs[i][0];
          int ty = y + dirs[i][1];
          if(tx < 0 || ty < 0 || tx >= col || ty >= row) continue;
          int pp = ty * col + tx;
          string t(s);
          swap(t[p], t[pp]);
          if(visited.count(t))continue;
          if(t == goal) return steps;
          visited.insert(t);
          Q.push(t);
         }  
        }
      }
      return -1;
  }
};

 

Solution 02

             Simplified, only works on 3×2 board

class Solution
{
public:
    int slidingPuzzle (vector<vector<int>> & board){
        const string goal = "123450";
        string start;
        for(int i = 0; i < board.size(); i++)
            for(int j = 0; j < board[0].size(); j++)
                start += (board[i][j] + '0');

            if(start == goal)return 0;

            const vector<vector<int>> idx{{1,3}, {0,2,4}, {1,5}, {0,4}, {1,3,5}, {2,4}};

            set<string> visited{start};
            int steps = 0;
            queue<pair<string,int>> Q;
            Q.emplace(start, start.find('0'));
            while(!Q.empty())
            {
                steps++;
                int sz = Q.size();
                while(sz-- > 0){
                    const auto& p = Q.front();
                    Q.pop();
                    for(int index: idx[p.second]){
                        string t(p.first);
                        swap(t[p.second], t[index])
                        if(visited.count(t))continue;
                        if(t == goal)return steps;
                        visited.insert(t);
                        Q.emplace(t, index);
                    }
                }
            }
            return -1;
    }
   
};

Share:

Read More

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++){
        if(S[i] == J[k])cnt++;
    }
    }
        return cnt;
    }
};

Solution 02:

complexity: N log(N)

class Solution {
public:
    int numJewelsInStones(string J, string S) {
   int cnt = 0;

unordered_set<char>jewels;

for(int i = 0; i < J.size(); i++){
    jewels.insert(J[i]);
  }

for(int i = 0; i < S.size(); i++){
    if(jewels.find(S[i]) != jewels.end()) cnt++;
}
return cnt;
    }
};

Solution 03:

Complexity: O(N)

class Solution {
public:
    int numJewelsInStones(string J, string S) {
   int cnt = 0;
        map<char, bool>jewels;

for(int i = 0; i < J.size(); i++){
    jewels[J[i]] = true;
  }

for(int i = 0; i < S.size(); i++){
    if(jewels[S[i]]) cnt++;
}
return cnt;
    }
};

Share:

Read More

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> make_priority_queue (vector<int>& v){
  vector<int> t(v.size());

  adjacent_difference(v.begin(), v.end(), t.begin());
  t.erase (t.begin());
  return priority_queue<T> (t.begin(), t.end());
}

double minmaxGasDist(vector<int>& stations, int k)
{
  auto PQ = make_priority_queue<Interval> (stations);
  double mx_dist = (stations.back() - stations.front())/static_cast<double> (k+1);

  while(k){
    auto top = PQ.top();
    PQ.pop();
    while(k && (top.dist >= PQ.top().dist || top.dist > mx_dist)){
      top.update();
      k--;
    }
    PQ.push(top);
  }
  return PQ.top().dist;
}

int main()
{
     #ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
  #endif

    vector<int>V;
    int n,k;
    cin >> n >> k;
    for(int i = 0; i < n; i++){
      int x;
      cin >> x;
      V.push_back(x);
    }
    cout << minmaxGasDist(V, k)<<endl;

}

Share:

Read More

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 > s/2){
      k -= s/2;
      flips++;
    }
    s /= 2;
  }
  k--;
  //cout << "---------"<<k<<endl;
  if(flips&1)k = 1 - k;
  return k;
}
};

Share:

Read More

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 : root->right;
  ans[x] = root;
  auto t = SplitBST(node, V);
  node = t[x];
  ans[y] = t[y];
  return ans;
}

Share:

Read More

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, 0, 1, -1};

bool is_valid(int x, int y, int n)
{
  return (x >= 0 && x < n && y >= 0 &&  y < n);
}

int swimInWater (vector<vector<int>>& grid)
{
  int n = grid.size();

  priority_queue<pos>PQ;

  PQ.push(pos(grid[0][0], 0, 0));

  vector<vector<int>> done(n, vi (n, -1));
  done[0][0] = grid[0][0];

  while(done[n-1][n-1] == -1){
    auto p = PQ.top();
    PQ.pop();

    for(int i = 0; i < 4; i++){
      int a = p.x + nx[i];
      int b = p.y + ny[i];

      if(is_valid(a,b,n) && done[a][b] == -1){
        int c = max(grid[a][b], p.val);
        PQ.push(pos(c,a,b));
        done[a][b] = c;
      }
    }
  }
  return done[n-1][n-1];
}
};

Share:

Read More

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>& A, int k)
{
  priority_queue<fraction>PQ;

  for(int i =0; i < A.size(); i++){
    PQ.push(fraction(static_cast<double> (A[i])/A.back(), i, A.size()-1 ));
  }
  while(k > 1){
    auto top = PQ.top();
    PQ.pop();
    top.j--;
    PQ.push(fraction(static_cast<double> (A[top.i])/A[top.j], top.i, top.j));
      k--;
  }

  return {A[PQ.top().i], A[PQ.top().j]};
}



};

Solution 2:

Compexity: N*C (c <= 31)

class Solution{
public:
  vector<int> kthSmallestPrimeFraction(vector<int>& A, int K)
  {
    const int n = A.size();
    double l = 0;
    double r = 1.0;
    while(l < r) {
      double m = (l + r)/2;
      double max_f = 0.0;
      int total = 0;
      int p, q = 0;
      for (int i = 0, j = 1; i < n - 1; ++i) {
       while (j < n && A[i] > m * A[j]) ++j;
        if(n == j)break;
        total += (n- j);
        const double f = static_cast<double> (A[i]) / A[j];
        if(f > max_f){
          p = i;
          q = j;
          max_f = f;
        }
      }
      if(total == K)return {A[p], A[q]};
      else if(total > K)r = m;
      else l = m;
    }
    return {};
  }
};

Share:

Read More

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 (N+1);

for(int i = 4; i <= N; i++){
  dp[i] = 2*dp[i - 1] + dp[i - 3];
  dp[i] %= MOD;
}
return dp[N];
    }
};

Share:

Read More

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;
    result += end - start;
  }
  return result;
}

Solution 2:

class Solution {
public:
 enum Valutype{
  RESET,
  NEEDED,
  OK
};

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++){
    auto val_type = A[i] > R ? RESET : A[i] >= L ? NEEDED : OK;

    switch(val_type){
      case RESET: start = i;
      case NEEDED: end = i;
      case OK: ///do nothing
      default: result += end - start;
    }
  }
  return result;
}
};

Share:

Read More

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)
    {
        if(safe_nodes.find(i) != safe_nodes.end())return true;
        if(cycle_nodes.find(i) != cycle_nodes.end())return false;
       
        if(visited_nodes.find(i) != visited_nodes.end()){
            cycle_nodes.insert(i);
            return false;
        }
       
        visited_nodes.insert(i);
        for(int node : g[i]){
            if(!dfs(g, node, visited_nodes)){
                cycle_nodes.insert(i);
                return false;
            }
        }
        safe_nodes.insert(i);
        return true;
    }
   
    vector<int> eventualSafeNodes(vector<vector<int>>& graph) {
        unordered_set<int>visited_nodes;
        vector<int>ans;
       
        for(int i = 0; i < graph.size(); i++){
            if(dfs(graph, i,visited_nodes))ans.push_back(i);
        }
        return ans;
    }
};

Share:

Read More

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;


    if(A[i-1] < A[i] && B[i - 1] < B[i]){
      X[i] = X[i-1];
      Y[i] = Y[i - 1] + 1;
    }

    if(A[i - 1] < B[i] && B[i-1] < A[i]){
      X[i] = min(X[i], Y[i-1]);
      Y[i] = min(Y[i], X[i-1] + 1);
    }

  }
  return min(Y[n-1], X[n-1]);
}
};

Share:

Read More

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++)
    if(sum*i % n == 0)possible = true;

  return possible;
}

bool splitArraySameAverage (const vector<int>& A)
{
  int n = A.size();
  int m = n/2;

  int sum = accumulate(A.begin(), A.end(), 0);

  if(!is_possible(m,sum,n)) return false;///pruning

  vector<unordered_set<int> > ans(m+1);

  ans[0].insert(0);

  for(int num : A)
    for(int i = m; i >= 1; i--)
      for(int t : ans[i-1])
        ans[i].insert(t+num);

  for(int i = 1; i <= m; i++){
    if(sum*i %n == 0 && ans[i].find(sum*i/n) != ans[i].end())return true;
  }
  return false;

/**

sums[0].insert (0);

for (int num : A)

for (int i = m; i >= 1; --i)

transform (sums[i - 1].begin (), sums[i - 1].end (),

inserter (sums[i], sums[i].end ()),

[num](int t) { return t + num; });

for (int i = 1; i <= m; ++i)

if (sum * i % n == 0 && sums[i].count (sum * i / n)) return true;

return false;
**/

vector<unordered_set<int>> sums (m + 1);

}
};

Share:

Read More

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> > stop_routes;

    for(int i = 0; i < routes.size(); i++){
        for(int j : routes[i])stop_routes[j].insert(i);
    }

    queue<pair<int, int> > to_visit;
    to_visit.push({S,0});
    unordered_set<int>stop_visited = { S };

    while(!to_visit.empty()){
        int stop = to_visit.front().first;
        int bus_n = to_visit.front().second;

        if(stop == T)return bus_n;

        to_visit.pop();

        for(const auto& route : stop_routes[stop]){
            for(const auto& next_stop : routes[route]){
                auto it = stop_visited.insert(next_stop);
                if(it.second)to_visit.push({next_stop, bus_n+1});
            }
            routes[route].clear();
        }
    }
        return -1;
}
};

Share:

Read More

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( (N - n*(n+1)/2) %n == 0)ans++;
    }
    return ans+1;
}
};

Share:

Read More

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){
        return (x >= 0 && x < n && y >= 0 && y < n);
    }

    void flood_fill(island& A, const vvi& g, int x, int y){
        A.insert({x,y});
        for(int i = 0; i < 4; i++){
            int nx = x + dx[i];
            int ny = x + dy[i];

            if(is_valid(nx, ny) && g[nx][ny] && !A.count({nx, ny})){
                flood_fill(A, g, nx, ny);
            }
        }
    }

    template<class T>
    int dist(T a, T b){
        return abs(a.first - b.first) + abs(a.second - b.second) - 1;
    }

    int shortestBridge(vvi& g){
        n = g.size();
        island A, B;
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                if(g[i][j] == 0)continue;
                if(A.empty())
                    flood_fill(A, g, i,j);
                else if(B.empty() && !A.count({i,j}))
                    flood_fill(B, g, i, j);
            }
        }
        int ans = 2*n;
        for(auto i: A){
            for(auto j: B){
                ans = min(ans, dist(i,j));
            }
        }

            return ans;
    }

};

Share:

Read More

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){
    string odd, even;
    for(int i = 0; i  < w.size(); i++){
        if(i%2) even += w[i];
        else odd += w[i];
    }
    sort(even.begin(), even.end());
    sort(odd.begin(), odd.end());
    s.insert(even+odd);
}
return s.size();
       
    }
};

Share:

Read More

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  ------------- 5   -9  6   5
minimun element = -9.
time complexity = O(n^2)

Code:


//#include<bits/stdc++.h>
using vi = vector<int>;
using vvi = vector<vi>:

int minFallingpathsum(vector<vector>>& a){
    int n =a.size();
    vvi dp(n,vi(n));
    dp[0] = a[0];
    for(int i = 1; i < n; i++){
        for(int j = 0; j < n; j++){
            dp[i][j] = a[i][j] + dp[i-1][j];
            if(j > 0)
                dp[i][j] = min(dp[i][j], a[i][j]+dp[i-1][j-1]);
            if(j < n- 1)dp[i][j] = min(dp[i][j], dp[i-1][j+1]);
        }
    }
    return *min_element(dp[n-1].begin(), dp[n-1].end());
}

Share:

Read More