We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
I just want to say that O(n^2) in editorial for this problem seems a wrong time complexity. That is because the total number of edges is O(mn). If one applies a standard Ford-Fulkerson algorithm, it is O(|E|f_max) = O(mn^2) in the problem setting. If one aims better one, try Horpcroft-Karp's algorithm for the bipartite matching. It should give you O(sqrt(|V|)|E|) = O(mn(m+n)^0.5) time complexity.
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Real Estate Broker
You are viewing a single comment's thread. Return to all comments →
I just want to say that O(n^2) in editorial for this problem seems a wrong time complexity. That is because the total number of edges is O(mn). If one applies a standard Ford-Fulkerson algorithm, it is O(|E|f_max) = O(mn^2) in the problem setting. If one aims better one, try Horpcroft-Karp's algorithm for the bipartite matching. It should give you O(sqrt(|V|)|E|) = O(mn(m+n)^0.5) time complexity.