sleepycoder
BAN USERFor each user, look at index [i][i]. then check the row and column which intersect there. If the row has any 1s and the column has any 0s, you can stop searching that user immediately as you know they aren't the influencer.
Furthermore, any time you find a 1 while checking the column, you know that the user who corresponds to the row it's in is also not the influencer.
int getInfluencer(boolean[][] followingMatrix) {
Set<Integer> candidates = new HashSet<Integer>();
for (int i = 0; i < followingMatrix.length; i++)
candidates.add(i);
while (candidates.size() != 0) {
Integer cur;
for (Integer i : candidates) {
cur = i;
candidates.remove(cur);
break;
}
// Check row
boolean breakFlag = false;
for (int i = 0; i < followingMatrix.length; i++) {
if (breakFlag)
break;
if (i != cur) {
if (followingMatrix[cur][i]) {
breakFlag = true;
break;
}
}
}
if (breakFlag)
continue;
// Check column
for (int i = 0; i < followingMatrix.length; i++) {
if (breakFlag)
break;
if (i != cur) {
if (!followingMatrix[i][cur]) {
breakFlag = true;
break;
}
}
candidates.remove(i);
}
if (!breakFlag)
return cur;
}
return -1;
}
@kr.neeray you're right. I confused an anagram with a palindrome.
- sleepycoder February 19, 2014Any anagram? I assume you mean an anagram needle (the entire string), otherwise your example makes no sense.
Anyway, this is pretty straightforward. Reverse needle and then perform the KMP string matching algorithm. O(n) time and O(1) space.
You can find every subsequence and then select the longest one which is repeated at least once. O(n^2) time and O(n^2) space in Python:
- sleepycoder April 03, 2014