Help needed in LeetCode medium problem

help
, ,
1

I am solving this problem using DSU.
But it fails on this test case, I can’t find the mistake.
Is my logic incorrect or some bug?
I saw that this can be easily solved using recursion(DFS) and queue(BFS).

problem link
test case 

class Solution
{
public:
      vector<int> parent;

      void makeSets()
      {
            for (int i = 0; i < parent.size(); i++)
            {
                  parent[i] = i;
            }
      }

      int findSet(int a)
      {
            if (a == parent[a])
            {
                  return a;
            }
            return parent[a] = findSet(parent[a]);
      }

      void unionSets(int a, int b)
      {
            a = findSet(a);
            b = findSet(b);
            if (a != b)
            {
                  parent[a] = b;
            }
      }

      bool canReach(vector<int> &arr, int start)
      {
            parent.assign(arr.size(), 0);
            makeSets();
            int n = arr.size();
            vector<int> zeroIndices;

            for (int i = 0; i < n; i++)
            {
                  int x = i + arr[i];
                  int y = i - arr[i];
                  if (arr[i] == 0)
                  {
                        zeroIndices.push_back(i);
                        continue;
                  }
                  if (0 <= x && x <= n - 1)
                  {
                        unionSets(i, x);
                  }
                  if (0 <= y && y <= n - 1)
                  {
                        unionSets(i, y);
                  }
            }

            for (auto i : zeroIndices)
            {
                  if (findSet(i) == findSet(start))
                  {
                        return true;
                  }
            }
            return false;
      }
};

Any help would be great.
Thanks

@ssrivastava990 what do you think?

2

Bro frankly , I don’t know DSU so much , @aneee004 will help .

3

If u have any problem in both of them i will surely help .

1 Like
4

There is no submission via DSU , is it really solvable by DSU ?
some user also said this - > HERE

5

I too read that, but DSU was my first intuition, so i just wanted to make sure if it can be solved.
Thanks anyway brother.

6

what made u think to solve this problem by DSU share your intutuion

7

if we can reach a zero value index by some start point, it means they must be connected,
So i thought why not use union set to combine the connected indices and and then find set to check if they belong to the same group or not.

8

Look at this test case
[0,1,3,3]
2
The 1st index is connected to the 0th and the 2nd index separately, in your code you connect the 0th index and the 2nd index too, giving you a false positive.

9

You cannot use DSU here, because the edges are directed. Lets say j = i + A[i] for some i. This means you can get from i to j, but it is not necessarily true that you can get from j to i too. Because i \neq j \pm A[j].

Example: The beautiful one pointed out by @preyam

[UPD]: My solution with dfs.

Code 
class Solution {
    vector<vector<int>> adj;
    vector<bool> vis;
    bool dfs(vector<int> &A, int u) {
        if(A[u] == 0) return true;
        vis[u] = 1;
        for(int v : adj[u]) if(not vis[v])
            if(dfs(A, v)) return true;
        return false;
    }
public:
    bool canReach(vector<int>& A, int start) {
        int n = A.size();
        adj.assign(n, vector<int>());
        vis.assign(n, false);
        for(int i = 0; i < n; i++) {
            if(i + A[i] < n)
                adj[i].push_back(i + A[i]);
            if(i - A[i] >= 0)
                adj[i].push_back(i - A[i]);
        }
        return dfs(A, start);
    }
};
1 Like
10

Thanks @preyam, now it get what is wrong.

11

Thanks @aneee004, It was silly to not think that.