Matviy Ilyashenko
BAN USERMuch more efficient solution is to store only 1-th cells somewhere and then review only them looking for rectangle. Also we can notice that to make up a rectangle we need to have 2 pairs of points with same x or y coordinate, so let's store them grouped by y or x coordinate. Finally we should not check individually each pair or lines in matrix, we can just intersect sets of points in each line to see if final intersection will have 2 or more points.
Store all 1-th cells into a map take O(N*M), where N and M are matrix width and heigh, then we enumerate all pairs of lines/columns (it can be O(N^2) or O(M^2) what is less) and then make intersection of two sets, that takes O(N) or O(M) time. Lets assume that total it will be O(N*M+N^2*M) or (ON*M+M^2*N) - we can choose smaller dimension to have smaller from those two. Additional space needed is O(K) where K - number of 1-th in matrix. Code:
private static boolean isRectangle(byte[][] m) {
Map<Integer, Set<Integer>> yPoints = new HashMap<Integer, Set<Integer>>();
int h=m.length,w=m[0].length;
for(int y=0;y<h;y++)
for(int x=0;x<w;x++)
if(m[y][x]==1)
yPoints.computeIfAbsent(y,s->new HashSet<Integer>()).add(x);
List<Map.Entry<Integer, Set<Integer>>> lines =
new ArrayList<Map.Entry<Integer, Set<Integer>>>(yPoints.entrySet());
for(int i=0;i<lines.size();i++)
for(int j=i+1;j<lines.size();j++) {
Set<Integer> points = new HashSet<Integer>(lines.get(i).getValue());
points.retainAll(lines.get(j).getValue());
if(points.size()>=2) return true;
}
return false;
}
private static void doTest1Yes() {
byte[][] m = {
{1,0,0,1,0},
{0,0,1,0,1},
{0,0,0,1,0},
{1,0,1,0,1}};
System.out.println(isRectangle(m)?"YES":"NO");
}
private static void doTest2No() {
byte[][] m = {
{1,0,0,1,0},
{0,0,0,0,1},
{0,0,0,1,0},
{1,0,1,0,1}};
System.out.println(isRectangle(m)?"YES":"NO");
}
public static void main(String[] args) {
doTest1Yes();
doTest2No();
}
Simple brute-force solution with O(N^2*M^2) where N and M are matrix width and height, but O(1) memory complexity:
private static boolean isRectangle(byte[][] m) {
int h=m.length,w=m[0].length;
for(int y1=0;y1<h;y1++)
for(int x1=0;x1<w;x1++)
if(m[y1][x1]==1)
for(int y2=y1+1;y2<h;y2++)
for(int x2=x1+1;x2<w;x2++)
if(m[y1][x2]==1 && m[y2][x1]==1 && m[y2][x2]==1)
return true;
return false;
}
private static void doTest1Yes() {
byte[][] m = {
{1,0,0,1,0},
{0,0,1,0,1},
{0,0,0,1,0},
{1,0,1,0,1}};
System.out.println(isRectangle(m)?"YES":"NO");
}
private static void doTest2No() {
byte[][] m = {
{1,0,0,1,0},
{0,0,0,0,1},
{0,0,0,1,0},
{1,0,1,0,1}};
System.out.println(isRectangle(m)?"YES":"NO");
}
public static void main(String[] args) {
doTest1Yes();
doTest2No();
}
More efficient solution be time possible, but it will require additional memory, so this one also have chance to exists.
- Matviy Ilyashenko November 14, 2017Just precalculate all squares of numbers between 1 and SQRT(n). Space complexity: O(sqrt(n)), time complexity: O(n) (as it is O(sqrt(n)*sqrt(n)) = O(n)):
private static boolean isSumOfSquares(int n) {
List<Integer> squares = new ArrayList<Integer>();
for(long i=1;i*i<n;i++)
squares.add((int)(i*i));
for(Integer a : squares)
for(Integer b: squares)
if(a+b==n) {
System.out.println(n+" = "+a+" + "+b);
return true;
}
return false;
}
public static void main(String[] args) {
System.out.println(isSumOfSquares(16)?"YES":"NO");
System.out.println(isSumOfSquares(17)?"YES":"NO");
System.out.println(isSumOfSquares(26)?"YES":"NO");
}
}
We can just run DFS on a graph and check if vertices were already visited. If some vertex was already visited:
1) There is cycle in graph
2) Remove edge that make us a cycle (end with this visited vertex)
Because we visit each vertex only once, time complexity O(N), because we use hash to store visited vertices - space complexity is also O(N) (actually because we use recursion, it will always create extra variables on each level of recursion, so space complexity always not less then recursion depth, that can be also up to N in this case)
Code:
static class DirectedGraphNode {
int label;
List<DirectedGraphNode> neighbors;
DirectedGraphNode(int x) {
label = x;
neighbors = new ArrayList<>();
}
List<Integer> getNeighborsLabels() {
List<Integer> labels = new ArrayList<Integer>();
for(DirectedGraphNode neighbor : neighbors)
labels.add(neighbor.label);
return labels;
}
}
private static boolean removeCycles(DirectedGraphNode node, Set<Integer> visited) {
visited.add(node.label);
boolean isCycle=false;
Iterator<DirectedGraphNode> it=node.neighbors.iterator();
while(it.hasNext()) {
DirectedGraphNode neighbour = it.next();
if(visited.contains(neighbour.label)) {
isCycle=true;
it.remove();
} else {
isCycle|=removeCycles(neighbour, visited);
}
}
visited.remove(node.label);
return isCycle;
}
private static void doTest1Yes() {
DirectedGraphNode nodes[] = new DirectedGraphNode[3];
for(int i=0;i<3;i++)
nodes[i]=new DirectedGraphNode(i);
nodes[2].neighbors.add(nodes[0]);
nodes[1].neighbors.add(nodes[2]);
nodes[0].neighbors.add(nodes[1]);
System.out.println(removeCycles(nodes[0], new HashSet<Integer>())?"YES":"NO");
for(int i=0;i<3;i++)
System.out.println("Node "+i+": "+nodes[i].getNeighborsLabels());
}
private static void doTest2No() {
DirectedGraphNode nodes[] = new DirectedGraphNode[5];
for(int i=0;i<5;i++)
nodes[i]=new DirectedGraphNode(i);
nodes[0].neighbors.add(nodes[1]);
nodes[0].neighbors.add(nodes[2]);
nodes[1].neighbors.add(nodes[3]);
nodes[1].neighbors.add(nodes[4]);
System.out.println(removeCycles(nodes[0], new HashSet<Integer>())?"YES":"NO");
for(int i=0;i<5;i++)
System.out.println("Node "+i+": "+nodes[i].getNeighborsLabels());
}
private static void doTest3No() {
DirectedGraphNode nodes[] = new DirectedGraphNode[4];
for(int i=0;i<4;i++)
nodes[i]=new DirectedGraphNode(i);
nodes[0].neighbors.add(nodes[1]);
nodes[0].neighbors.add(nodes[2]);
nodes[1].neighbors.add(nodes[2]);
nodes[1].neighbors.add(nodes[3]);
nodes[3].neighbors.add(nodes[2]);
System.out.println(removeCycles(nodes[0], new HashSet<Integer>())?"YES":"NO");
for(int i=0;i<4;i++)
System.out.println("Node "+i+": "+nodes[i].getNeighborsLabels());
}
private static void doTest4Yes() {
DirectedGraphNode nodes[] = new DirectedGraphNode[4];
for(int i=0;i<4;i++)
nodes[i]=new DirectedGraphNode(i);
nodes[0].neighbors.add(nodes[1]);
nodes[0].neighbors.add(nodes[2]);
nodes[1].neighbors.add(nodes[3]);
nodes[2].neighbors.add(nodes[1]);
nodes[3].neighbors.add(nodes[2]);
System.out.println(removeCycles(nodes[0], new HashSet<Integer>())?"YES":"NO");
for(int i=0;i<4;i++)
System.out.println("Node "+i+": "+nodes[i].getNeighborsLabels());
}
public static void main(String[] args) {
doTest1Yes();
doTest2No();
doTest3No();
doTest4Yes();
}
}
Yes, it is well-known (classical) NP-complete problem that in general has solution O(n!) but practically many things can be done to reduce practical big-O for this problem:
- Use invariants as much as possible and it is proven that no matter how complicated invariant computation is, while it is polynomial time - it is still better to use it when graphs size rise to infinity
- Simplest invariant (that I used in my program): just be sure all vertices in both graphs in general have same sets of powers (number of adjacent vertices), and even with such simple invariant it is already a problem to construct example when graphs will be not insomorph but still fall into backtracking part (I put comment below to disable one line to actually test backtracking part)
- More complicated vertices invariants:
= calculate now many vertices adjacent to each vertex
= calculate how many vertex/edges will be in each vertex surrounding of X edges (+more strong - calculate for each value of X independent)
and many others.
For backtracking practically there is heruistic to compare first vertices with higher vertex power and then with lower (if graphs are not insomorph is it not important but if they are - such order will find mapping faster in general). I didn't used this heruistic in my code, just because I sure it is not possible to do during 30 minutes (but of course possible in real projects).
Here is the code. In general it is O(n!) time and O(n) space complexity where N - number of vertices in each graph (those should be equal):
private static class Graph {
private List<List<Integer>> adj=new ArrayList<List<Integer>>(); // Adjacency list
void addVertex(int vIndex, List<Integer> adjacentVertices) {
adj.add(vIndex, adjacentVertices);
}
int vertexPower(int vIndex) { return adj.get(vIndex).size(); }
int getVertexs() { return adj.size(); }
}
private static Map<Integer, Integer> vertexPowers(Graph g) {
Map<Integer, Integer> vertexPowers = new HashMap<Integer, Integer>();
for(int i=0;i<g.getVertexs();i++)
vertexPowers.put(i,g.vertexPower(i));
return vertexPowers;
}
private static boolean isVertexMappingAllowed(Graph a, Graph b,
Map<Integer, Integer> mapping,
int aVIndex, int bVIndex) {
for(Integer bVAdj : b.adj.get(bVIndex))
if(mapping.keySet().contains(bVAdj))
if(!a.adj.get(aVIndex).contains(mapping.get(bVAdj)))
return false;
return true;
}
private static boolean isomorphRecursive(Graph a, Graph b,
Map<Integer, Integer> mapping) {
if(mapping.size()==a.getVertexs()) return true;
int aVIndex = mapping.size();
for(int bVIndex=0;bVIndex<b.getVertexs();bVIndex++)
if(!mapping.keySet().contains(bVIndex))
if(isVertexMappingAllowed(a,b,mapping,aVIndex,bVIndex)) {
mapping.put(bVIndex, aVIndex);
if(isomorphRecursive(a,b,mapping))
return true;
mapping.remove(bVIndex);
}
return false;
}
private static boolean isomorph(Graph a, Graph b) {
// Simplest invariant - number of vertices should be the same
if(a.getVertexs()!=b.getVertexs()) return false;
Map<Integer, Integer> aVP = vertexPowers(a);
Map<Integer, Integer> bVP = vertexPowers(b);
// Also very simple invariant - powers on vertices should be the same
List<Integer> aVPowers = new ArrayList<Integer>(aVP.values());
List<Integer> bVPowers = new ArrayList<Integer>(bVP.values());
Collections.sort(aVPowers);
Collections.sort(bVPowers);
if(!aVPowers.equals(bVPowers)) return false; // disable this to have reason fot test2
Map<Integer, Integer> mapping = new HashMap<Integer, Integer>();
boolean isIsomorph = isomorphRecursive(a,b,mapping);
// here mapping will contains actual mapping if graphs are isomorph
System.out.println(mapping);
return isIsomorph;
}
private static void doTest0Yes() {
Graph a = new Graph();
a.addVertex(0, Arrays.asList(1));
a.addVertex(1, Arrays.asList(0));
Graph b = new Graph();
b.addVertex(0, Arrays.asList(1));
b.addVertex(1, Arrays.asList(0));
System.out.println(isomorph(a,b)?"YES":"NO");
}
private static void doTest0No() {
Graph a = new Graph();
a.addVertex(0, Arrays.asList(1));
a.addVertex(1, Arrays.asList(0));
Graph b = new Graph();
System.out.println(isomorph(a,b)?"YES":"NO");
}
private static void doTest1Yes() {
Graph a = new Graph();
a.addVertex(0, Arrays.asList(1,3));
a.addVertex(1, Arrays.asList(0,2,3,4));
a.addVertex(2, Arrays.asList(1,4));
a.addVertex(3, Arrays.asList(0,1,4));
a.addVertex(4, Arrays.asList(1,2,3));
Graph b = new Graph();
b.addVertex(0, Arrays.asList(1,2,3));
b.addVertex(1, Arrays.asList(0,3,4));
b.addVertex(2, Arrays.asList(0,3));
b.addVertex(3, Arrays.asList(0,1,2,4));
b.addVertex(4, Arrays.asList(1,3));
System.out.println(isomorph(a,b)?"YES":"NO");
}
private static void doTest2No() {
Graph a = new Graph();
a.addVertex(0, Arrays.asList(1,2,3));
a.addVertex(1, Arrays.asList(0,5));
a.addVertex(2, Arrays.asList(0,4));
a.addVertex(3, Arrays.asList(0,1,5));
a.addVertex(4, Arrays.asList(2,5));
a.addVertex(5, Arrays.asList(1,3,4));
Graph b = new Graph();
b.addVertex(0, Arrays.asList(1,2));
b.addVertex(1, Arrays.asList(0,2,3));
b.addVertex(2, Arrays.asList(0,1,3,4));
b.addVertex(3, Arrays.asList(1,2,5));
b.addVertex(4, Arrays.asList(2,5));
b.addVertex(5, Arrays.asList(3,4));
System.out.println(isomorph(a,b)?"YES":"NO");
}
public static void main(String[] args) {
doTest0Yes();
doTest0No();
doTest1Yes();
doTest2No();
}
@Alex, Program actually prints 22, it was my mistake in code (I didn't updated expected value)
- Matviy Ilyashenko November 13, 2017Wel... Actually you build a usual trie, but should take attention on next aspects:
1) Some words can be subwords of another, like: caw and cawboy, so you should have marker that will indicate complete words in a trie
2) '*' means that you should try to continue recursive backtracking search with any character on current level as well as with next character in pattern
3) Take into account that there can be '**' and more asterisk in line (I just replace such with single one)
4) Take into account that '*' could be last character in a pattern (and the only one character in a pattern).
Space complexity O(S*L), where S - number of words in trie, L - average length of word. Time complexity equals to number of nodes in a trie (in worst case of '*' pattern) should be O(S*L) (as we will visit each node one or two times in worst case).
It is tricky to take this all into account, but here is the code:
private static class Node {
boolean isWord;
Map<Byte,Node> children = new HashMap<Byte,Node>();
}
private static class Trie {
Node root=new Node();
void add(String str) {
Node node = root;
for(int i=0;i<str.length();i++) {
char ch=str.charAt(i);
node=node.children.computeIfAbsent((byte)ch,s->new Node());
}
node.isWord=true;
}
static String preparePattern(String pattern) {
return pattern.replaceAll("\\*+","*");
}
String stringFromPath(List<String> path) {
return String.join("",path);
}
void searchRecursive(Node node, String pattern, int pos,
LinkedList<String> path, Set<String> found) {
if(pos==pattern.length()) {
if(node.isWord)
found.add(stringFromPath(path));
return;
}
char ch = pattern.charAt(pos);
if(ch=='*') {
if(pos==pattern.length()-1 && node.isWord) {
found.add(stringFromPath(path));
if(node.children.size()==0)
return;
}
for(Map.Entry<Byte,Node> entry : node.children.entrySet()) {
Node nextNode = entry.getValue();
path.addLast(String.valueOf((char)(entry.getKey().byteValue())));
searchRecursive(nextNode, pattern, pos, path, found);
searchRecursive(nextNode, pattern, pos+1, path, found);
path.removeLast();
}
} else {
Node nextNode = node.children.get((byte)ch);
if(nextNode!=null) {
path.addLast(String.valueOf(ch));
searchRecursive(nextNode, pattern, pos+1, path, found);
path.removeLast();
}
}
}
Set<String> search(String pattern) {
pattern = preparePattern(pattern);
Set<String> found = new HashSet<String>();
searchRecursive(root, pattern, 0, new LinkedList<String>(), found);
return found;
}
}
private static void doTest(Trie trie, String pattern) {
System.out.println("Pattern: "+pattern+" : "+trie.search(pattern));
}
public static void main(String[] args) {
Trie trie = new Trie();
trie.add("car");
trie.add("caw");
trie.add("cauw");
trie.add("caqweruw");
trie.add("trie");
trie.add("computer");
trie.add("cawboy");
doTest(trie,"c*w");
doTest(trie,"ca*");
doTest(trie,"c**w*");
doTest(trie,"*r*");
doTest(trie,"*");
}
Well... You can find out that if there are less then 10 segments, each segment number will spend 5 characters. If there more then 9 segments, then first 9 will spend 6 characters and next (up to 90) will spend 7 characters. And so on. This leads us to next table of segmentation tests length:
- 5*9 (up to 9 segments)
- 6*9 + 7*90 (up to 99 segments)
- 7*9 + 8*90 + 9*900 (up to 999 segments)
- 8*9 + 9*90 + 10*900 + 11*9000 (up to 9999 segments)
Also you should take into account that it should be true: k-segment.length > 0, just to have at least 1 character for actual test in segment.
So in total you need to have two arrays:
- segments lengths
- base - how many segments with such segment length
Update those values on each iteration while your string length will not fit number of segments of k-segment.length == 0 (that means it is impossible to build such segmentation).
I assume that if it is impossible to build such segmentation - program will return -1:
private static int numberOfSegments(String str, int k) {
List<Integer> segLens = new ArrayList<Integer>();
segLens.add(5);
List<Integer> bases = new ArrayList<Integer>();
bases.add(9);
while(k-segLens.get(segLens.size()-1)>0) {
int length = str.length();
int i, segments=0;
for(i=0;i<segLens.size()-1;i++) {
length-=(k-segLens.get(i))*bases.get(i);
segments+=bases.get(i);
}
if(length <= (k-segLens.get(i))*bases.get(i)) {
segments+=(length + k-segLens.get(i)-1)/(k-segLens.get(i));
return segments;
}
for(int j=0;j<segLens.size();j++)
segLens.set(j, segLens.get(j)+1);
segLens.add(segLens.get(segLens.size()-1)+1);
bases.add(bases.get(bases.size()-1)*10);
}
return -1;
}
private static void doTest(String str, int k, int expectedSegments) {
int segments = numberOfSegments(str, k);
System.out.println(str+"\t"+expectedSegments+"\t"+segments);
}
public static void main(String[] args) {
doTest("That is a cat",8,5);
doTest("That is a cat and this is a dog",9,8);
doTest("That is a cat and this is a dog",8,22);
doTest("That is a cat and this is a dog",7,-1);
}
Possible solution with O(N) time complexity (where N - number of bits) and O(N) memory complexity:
- Calculate how many flips of '0' need to be done when you move from left to right to have all '1' in bits
- Calculate how many flips of '1' need to be done when you move from right to left to have all '0' in bits
- Walk through all positions between bits and find minimal sum of '0'-flips+'1'-flips from both arrays:
private static int minimalFilps(String bits) {
int flipsFromLeft[] = new int[bits.length()];
int flipsFromRight[]= new int[bits.length()];
int flips=0;
for(int i=0;i<bits.length();i++) {
if(bits.charAt(i)=='0') {
flips++;
}
flipsFromLeft[i]=flips;
}
flips=0;
for(int i=bits.length()-1;i>=0;i--) {
if(bits.charAt(i)=='1') {
flips++;
}
flipsFromRight[i]=flips;
}
int minFlips=Integer.MAX_VALUE;
for(int i=1;i<bits.length();i++) {
if(flipsFromLeft[i-1]+flipsFromRight[i] < minFlips)
minFlips=flipsFromLeft[i-1]+flipsFromRight[i];
}
return minFlips;
}
private static void doTest(String bits, int expectedFlips) {
int minFlips = minimalFilps(bits);
System.out.println(String.format("%s\t%d\t%d",bits, expectedFlips, minFlips));
}
private static void bulkTest() {
Map<String, Integer> tests = new LinkedHashMap<String, Integer>() {{
put("1000",0);
put("0001",2);
put("1001",1);
put("1011001",2);
put("10110000",1);
}};
System.out.println("Bits\tExpected\tActual");
for(Map.Entry<String, Integer> test : tests.entrySet())
doTest(test.getKey(), test.getValue());
}
public static void main(String[] args) {
bulkTest();
}
RepAre you looking for strong dua for husband love?Astrology is the perfect way to get your lost love back ...
@ChrisK, you are completely right, I just missed evidence that I can just calculate second term when I know n and first one. I even know such trick and used it already, but just forget in this case. Updated solution:
- Matviy Ilyashenko November 14, 2017