Google Interview Question Software Engineer / Developers
Country: United States
Interview Type: Phone Interview
I don' t think this takes into encounter whether it forms an increasing sequence It just ensures hat the values taken are consequent. Ex:
5 6 7 4
1 7 6 2
will probably give 6 7 6 7 as ans, if I am interpreting your algorithm correctly. Kindly correct me if I am wrong.
First, the question tells us to assume that we have all numbers from 1 to n*n EXACTLY once, so your situation cannot happen.
Also, if you're not guaranteed distinct integers, the algorithm does not make any sense. What do you store in arr[5] if one of the 6s is adjacent to 7 but the other one isn't?
I hope that clears up some confusion.
Yes, the algorithm is only valid if all the integers are distinct. We can still solve in linear time and space with respect to the size of the input if they're not distinct, but you would need a different algorithm. You could do it using dynamic programming. Let F(x,y) be the longest sequence starting from coordinates (x, y). Then F(x, y) = 1 if there are no neighbors with value arr[x][y]+1, or 1 + max over all such neighbors if any exist.
The problem statement says " NxN matrix which contains all distinct 1 to n^2 numbers" and this is an elegant solution. It's probably the answer the interviewer expecting too. +1.
@Eugene says it's linear time, but it's actually O(N^2) time and space, because input size is N^2.
Note that I said the algorithm is "linear in time and space with the size of the input", not linear in terms of N. The input size is N^2, so the time and space complexities are O(N^2). I chose to talk about the performance relative to the size of the input because that makes it clear that this algorithm is asymptotically optimal, since any algorithm must look at all or most of the input.
can you explain how will you modify the entry in the boolean array when you traverse the matrix? I might be missing something. The solution is a bit unclear to me.
time O(n^2) space O(n^2) solution.
we will need a 2D array visited[n][n] and two global vars->start and max=0.
Now we will traverse the matrix row by row.
for each 'not visited' element k start a recursive dfs such that next element is k+1.
Mark all traversed elements as visited so that you do not start a traversal from them again
the dfs() will return you the depth value till which it could go.
e.g. for 6 it will return 4 (6-7-8-9). for 7 it will return 3 (7-8-9).
if this value is greater than max, then update max and start value.
At last print max no. of consecutive characters from start value.
@neerajlakhotia08: based on your idea
#include <stdio.h>
#define X 4
#define Y 4
int m[X][Y] = {
1, 2, 4, 0,
5, 12, 11, 100,
6, 7, 10, 111,
1111, 8, 9, 122
};
int dfs(int i, int j, int visit[][Y])
{
if (i-1 > 0 && j > 0 && ((m[i-1][j]) == (m[i][j]+1)) && !visit[i-1][j]) {
visit[i-1][j] = 1;
return 1 + dfs(i-1, j, visit);
}
if (i+1 < X && j < Y && ((m[i+1][j]) == (m[i][j]+1)) && !visit[i+1][j]) {
visit[i+1][j] = 1;
return 1 + dfs(i+1, j, visit);
}
if (i < X && j-1 > 0 && ((m[i][j-1]) == (m[i][j]+1)) && !visit[i][j-1]) {
visit[i][j-1] = 1;
return 1 + dfs(i, j-1, visit);
}
if (i > 0 && j+1 < Y && ((m[i][j+1]) == (m[i][j]+1)) && !visit[i][j+1]) {
visit[i][j+1] = 1;
return 1 + dfs(i, j+1, visit);
}
return 0;
}
int main()
{
int visited[X][Y] = {0};
int old_max = 0;
int max = 0, i, j, k, l;
for (i=0;i<X;i++)
for (j=0;j<Y;j++) {
max = dfs(i, j, visited);
if (max >= old_max)
old_max = max;
}
printf("%d\n", old_max);
return 0;
}
1. In an array, store the position of every integer from 1 to n^2 by simply reading every entry of the matrix.
2. Iterate through the array. At every step, check if the next position is adjacent to the current position. If so, your current sequence's size increases by 1. If not, your current sequence is over. Every time a sequence terminates, if its length is greater than the longest sequence seen so far, remember its length and where it ends.
3. Knowing the size of the longest sequence and on which number it ends, you can easily print the sequence by printing the numbers from "end - length + 1" to "end".
Running the algorithm on the given example looks like this:
input
1 5 9
2 3 8
4 6 7
1. Produce the following array:
[(0,0), (0,1), (1,1), (0,2), (1,0), (1,2), (2,2), (2,1), (2,0)]
2.
Set length counter to 1.
(0,0) is adjacent to (0,1): +1;
(0,1) is adjacent to (1,1): +1;
(1,1) is not adjacent to (0,2): sequence length is 3, our current best, so lets remember the length and that it ended on the 3rd entry. Reset length counter to 1.
(0,2) is not adjacent to (1, 0): sequence length is 1, not our best. Simply reset counter to 1.
(1,0) is not adjacent to (1, 2): sequence length is 1, not our best. Simply reset counter to 1.
(1,2) is adjacent to (2,2): +1;
(2,2) is adjacent to (2,1): +1;
(2,1) is adjacent to (2,0): +1;
(2,0) is the end of the array, so the sequence ends: sequence length is 4, our current best, so lets remember the length and that it ended on the 9th entry.
3.
Our longest sequence has length 4 and ends at 9. So it starts at 9 - 4 + 1 = 6. So we output 6 7 8 9.
This algorithm has O(n^2) time and space complexity. O(n^2) is optimal for time complexity because you have to at least look at all of the entries, but O(n^2) is not optimal for space complexity. I can't seem to reduce the space complexity without increasing the time complexity however...
In Java:
void printLongestSnake(int[][] matrix) {
int n = matrix.length;
int nSquared = n * n;
Coordinate[] positions = new Coordinate[nSquared];
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
positions[matrix[i][j] - 1] = new Coordinate(i, j);
}
}
int maxLength = 1;
int maxEnd = 1;
int currentLength = 1;
for (int i = 1; i < nSquared; ++i) {
if (positions[i].isAdjacent(positions[i - 1])) {
++currentLength;
} else {
if (currentLength > maxLength) {
maxLength = currentLength;
maxEnd = i;
}
currentLength = 1;
}
}
if (currentLength > maxLength) {
maxLength = currentLength;
maxEnd = nSquared;
}
for (int i = maxEnd - maxLength + 1; i < maxEnd; ++i) {
System.out.print(i + " ");
}
System.out.println(maxEnd);
}
where Coordinate is the following simple class (you could just use an array of size 2 instead of making a class if you want to be more efficient, but then, you shouldn't be using Java lol)
class Coordinate {
private int x;
private int y;
public Coodinate(int x, int y) {
this.x = x;
this.y = y;
}
public boolean isAdjacent(Coordinate c) {
if (x == c.x && (y == c.y - 1 || y == c.y + 1) {
return true;
}
if (y == c.y && (x == c.x - 1 || x == c.x + 1) {
return true;
}
return false;
}
}
I assumed that you want to print the *longest* sequence of of consecutive numbers that are adjacent in the array. If not could you please clarify your question please, thanks.
public static class LongestSequence
{
public static void PrintLongestSeq(int[][] M)
{
if (M == null || M.Length == 0 || M[0].Length == 0)
return;
var maxSeq = new List<int>();
for (var i = 0; i < M.Length; i++)
for (var j = 0; j < M[0].Length; j++)
{
var currSeq = GetLongestSeq(M, i, j);
if (maxSeq.Count < currSeq.Count)
maxSeq = currSeq;
}
maxSeq.Print();
}
private static void Print(this List<int> l)
{
foreach (var e in l)
Console.Write(e);
}
private static List<int> GetLongestSeq(int[][] M, int i, int j)
{
var res = new List<int>();
if (i >= M.Length || j >= M.Length) return res;
res.Add(M[i][j]);
bool done = false;
while (!done)
{
done = true;
if (i < M.Length - 1 && M[i][j] == M[i + 1][j] - 1)
{
res.Add(M[i + 1][j]);
i += 1;
done = false;
}
if (i > 0 && M[i][j] == M[i - 1][j] - 1)
{
res.Add(M[i - 1][j]);
i -= 1;
done = false;
}
if (j < M.Length - 1 && M[i][j] == M[i][j + 1] - 1)
{
res.Add(M[i][j + 1]);
j += 1;
done = false;
}
if (j > 0 && M[i][j] == M[i][j - 1] - 1)
{
res.Add(M[i][j - 1]);
j -= 1;
done = false;
}
}
return res;
}
public static void Test()
{
var m = new int[3][];
m[0] = new[] { 1, 5, 9 };
m[1] = new[] { 2, 3, 8 };
m[2] = new[] { 4, 6, 7 };
PrintLongestSeq(m);
}
}
Please explain the increasing sequence here as there are others that might be possible of the same sequence.
We can implement using below graph by getting the adjacent value then check for increasing order needs extra effort.
1 2 3 4 5 6 7 8 9
1 0 1 0 0 1 0 0 0 0
2 1 0 1 1 1 0 0 0 0
3 0 1 0 0 1 1 0 1 0
4 0 1 0 0 0 1 0 0 0
5 1 0 1 0 0 0 0 0 1
6 0 0 1 1 0 0 1 0 0
7 0 0 0 0 0 1 0 1 0
8 0 0 1 0 0 0 1 0 1
9 0 0 0 0 1 0 0 1 0
the sequence can be pushed into the stack for the result.
Suggest if the above solution is wrong.
might not be super efficient; but would work
package Google;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
public class mSort {
public static ArrayList<Integer> mergeSort(ArrayList<Integer> a) {
if (a.size() <= 1) {
return a;
}
ArrayList<Integer> firstHalf = new ArrayList<Integer>();
ArrayList<Integer> secondHalf = new ArrayList<Integer>();
for (int i = 0; i < a.size() / 2; i++) {
firstHalf.add(a.get(i));
}
for (int i = a.size() / 2; i < a.size(); i++) {
secondHalf.add(a.get(i));
}
return merge(mergeSort(firstHalf), mergeSort(secondHalf));
}
public static ArrayList<Integer> merge(ArrayList<Integer> l1, ArrayList<Integer> l2) {
if (l1.size() == 0) {
return l2;
}
if (l2.size() == 0) {
return l1;
}
ArrayList<Integer> result = new ArrayList<Integer>();
int nextElement;
if (l1.get(0) > l2.get(0)) {
nextElement = l2.get(0);
l2.remove(0);
} else {
nextElement = l1.get(0);
l1.remove(0);
}
result.add(nextElement);
result.addAll(merge(l1,l2));
return result;
}
public static HashSet<Integer> getLargestSequence(Integer [] A) {
HashSet<Integer> result = new HashSet<Integer>();
if (A == null) {
return result;
}
int len = A.length;
Map<Integer, HashSet<Integer>> dataMap = new HashMap<Integer, HashSet<Integer>>();
for (int i=0; i<len; i++) {
int less = A[i] - 1;
int more = A[i] + 1;
HashSet<Integer> list = new HashSet<Integer>();
boolean leftUpdated = false;
boolean rightUpdated = false;
if (dataMap.containsKey(less)) {
list = dataMap.get(less);
list.add(A[i]);
dataMap.put(less, list);
HashSet<Integer > keylist = dataMap.get(A[i]);
if (keylist != null) {
keylist.add(less);
keylist.addAll(list);
} else {
keylist = new HashSet<Integer>();
keylist.addAll(list);
}
dataMap.put(A[i], keylist);
leftUpdated = true;
}
if (dataMap.containsKey(more)) {
list = dataMap.get(more);
list.add(A[i]);
dataMap.put(more, list);
HashSet<Integer > keylist = dataMap.get(A[i]);
if (keylist != null) {
list.add(more);
//keylist.add(more);
keylist.addAll(list);
} else {
keylist = new HashSet<Integer>();
keylist.addAll(list);
}
dataMap.put(A[i], keylist);
rightUpdated = true;
}
if (!leftUpdated && !rightUpdated) {
list.add(A[i]);
dataMap.put(A[i], list);
}
}
Iterator<Entry<Integer, HashSet<Integer>>> it = dataMap.entrySet().iterator();
while (it.hasNext()) {
Map.Entry<Integer, HashSet<Integer>> pair = (Map.Entry<Integer, HashSet<Integer>>)it.next();
if (pair.getValue().size() > result.size()) {
result = pair.getValue();
}
}
return result;
}
public static void main(String[] args) {
int [][] M ={ {1,2,3,4},{12,6,10,22},
{11,9,7,8},{20,29,28,15}};
ArrayList<Integer> list = new ArrayList<Integer>();
//First sort the MxM matrix; complexity O(nlogn)
for(int r=0;r<4;r++){
for(int c=0;c<4;c++){
list.add(M[r][c]);
}
}
list = mergeSort(list);
Integer[] list1 = list.toArray(new Integer[0]);
// from the sorted list find the largest sequence
HashSet<Integer> sequenceList = getLargestSequence(list1);
Iterator<Integer> iter = sequenceList.iterator();
System.out.println("Subset which forms the longest consecutive sequence: ");
while (iter.hasNext()) {
System.out.print(iter.next() + " ");
}
System.out.println();
}
}
The question says the array is square and NxN in size; and that it is populated with numbers 1...n^2. Why does your 4x4 array have numbers like 29 and 28 in it?
#include<iostream>
#include<vector>
using namespace std;
int X[4] = {0, -1, 0, 1};
int Y[4] = {-1, 0, 1, 0};
int n;
vector<int> curr_seq, max_seq;
void explore(int a[][3], int i, int j, int x){
if(i<0 || i>n-1 || j<0 || j>n-1)
return;
if(a[i][j] - x != 1 && a[i][j]-x!=a[i][j])
return;
curr_seq.push_back(a[i][j]);
for(int t=0;t<4;t++){
explore(a, i+X[t], j+Y[t], a[i][j]);
}
}
int MaxSequence(int a[][3]){
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
explore(a, i, j, 0);
if(curr_seq.size() > max_seq.size()){
max_seq.clear();
for(int i=0;i<curr_seq.size();i++)
max_seq.push_back(curr_seq[i]);
}
curr_seq.clear();
}
}
for(int i=0;i<max_seq.size();i++)
cout<<max_seq[i]<<" ";
}
int main(){
int a[3][3]= {{2, 3, 9},
{1, 4, 8},
{6, 5, 7}};
n=3;
MaxSequence(a);
}
public static void search(int cur, ArrayList<Node> mat,String result, ArrayList<String> results){
int left = cur%3 -1;
int right = cur%3 +1;
int up = cur/3 -1;
int down = cur/3 +1;
mat.get(cur).visit = true;
result += mat.get(cur).num+"";
boolean haha = false;
if(left >=0 && left < 3){
if(mat.get(cur-1).num-mat.get(cur).num == 1 && !mat.get(cur-1).visit){
search(cur-1, mat,result, results);
haha = true;
}
}
if(right >=0 && right < 3){
if(mat.get(cur+1).num-mat.get(cur).num == 1 && !mat.get(cur+1).visit){
search(cur+1, mat,result, results);
haha = true;
}
}
if(up >=0 && up < 3){
if(mat.get(cur-3).num-mat.get(cur).num == 1 && !mat.get(cur-3).visit){
search(cur-3, mat,result, results);
haha = true;
}
}
if(down >=0 && down < 3){
if(mat.get(cur+3).num-mat.get(cur).num == 1 && !mat.get(cur+3).visit){
search(cur+3, mat,result, results);
haha=true;
}
}
if(!haha){
results.add(result);
}
}
public static void search(int cur, ArrayList<Node> mat,String result, ArrayList<String> results){
int left = cur%3 -1;
int right = cur%3 +1;
int up = cur/3 -1;
int down = cur/3 +1;
mat.get(cur).visit = true;
result += mat.get(cur).num+"";
boolean haha = false;
if(left >=0 && left < 3){
if(mat.get(cur-1).num-mat.get(cur).num == 1 && !mat.get(cur-1).visit){
search(cur-1, mat,result, results);
haha = true;
}
}
if(right >=0 && right < 3){
if(mat.get(cur+1).num-mat.get(cur).num == 1 && !mat.get(cur+1).visit){
search(cur+1, mat,result, results);
haha = true;
}
}
if(up >=0 && up < 3){
if(mat.get(cur-3).num-mat.get(cur).num == 1 && !mat.get(cur-3).visit){
search(cur-3, mat,result, results);
haha = true;
}
}
if(down >=0 && down < 3){
if(mat.get(cur+3).num-mat.get(cur).num == 1 && !mat.get(cur+3).visit){
search(cur+3, mat,result, results);
haha=true;
}
}
if(!haha){
results.add(result);
}
}
This is O(n)
public class LaregSeq{
int arr[][] = {{1,5,9},{2,3,8},{4,6,7}};
int st, len;
boolean visited[][];
public static void main(String args[]){
st = 0;
len = 0;
visited = new boolean[arr.length][arr.length];
for(r =0;r<n;r++)
for(c=0;c<n;c++)
if(!visited[r][c])
printLarge(0,0,arr[r][c]-1,arr[r][c]);
for(int i =st;i<st+len;i++)
System.out.println(i);
}
public void printLarge(int r, int c,int prev,int st){
if(r < 0 || r > =arr.length || c < 0 || c >= arr.length)
return;
if(arr[r][c] !=prev+1){
if( prev-st+1 > len){
len = prev -st+1;
st = st;
}
return;
}
visited[r][c] = true;
printLarge(r+1,c,arr[r][c],st);
printLarge(r,c+1,arr[r][c],st);
printLarge(r-1,c,arr[r][c],st);
printLarge(r,c-1,arr[r][c],st);
}
}
#include "stdio.h"
void longest_seq(int n, int data[][3])
{
int **flag;
flag = new int*[n];
for (int i=0; i<n; i++) {
flag[i] = new int[n];
}
int offset[][2] = {{0,0}, {0,1}, {1,0}, {0,-1}, {-1,0}};
// init
for (int i=0; i<n; i++) {
for (int j=0; j<n; j++) {
if (j+1<n && data[i][j]==data[i][j+1]-1) {
flag[i][j] = 1;
}
else if (i+1<n && data[i][j]==data[i+1][j]-1) {
flag[i][j] = 2;
}
else if (j-1>=0 && data[i][j]==data[i][j-1]-1) {
flag[i][j] = 3;
}
else if (i-1>=0 && data[i][j]==data[i-1][j]-1) {
flag[i][j] = 4;
}
else
flag[i][j] = 0;
}
}
// do the computation
int best_i=0, best_j=0, max_len=1;
for (int i=0; i<n; i++) {
for (int j=0; j<n; j++) {
if (flag[i][j]==0) {
continue;
}
int cur_len=1;
int f = flag[i][j];
int n_i = i;
int n_j = j;
while(f>0) {
n_i += offset[f][0];
n_j += offset[f][1];
f = flag[n_i][n_j];
cur_len++;
}
if (cur_len > max_len) {
best_i = i;
best_j = j;
max_len = cur_len;
}
}
}
// print the seq..
int f = flag[best_i][best_j];
printf("%d", data[best_i][best_j]);
int n_i = best_i;
int n_j = best_j;
while (f>0) {
n_i += offset[f][0];
n_j += offset[f][1];
f = flag[n_i][n_j];
printf(" %d", data[n_i][n_j]);
}
printf("\n");
// release the space
for (int i=0; i<n; i++) {
delete[] flag[i];
}
delete[] flag;
}
// ./ex1
int main()
{
const int n = 3;
int data[][n] = {{1,5,9}, {2,3,8}, {4,6,7}};
longest_seq(n, data);
return 0;
}
Anyone else thinks that the Union-Find data structure would be perfect for this problem? O(2n) space requirements, O(log n) time to "connect" the numbers, constant time to check if 2 numbers are connected. O(n) time to find the largest set.
Th only problem with this and the above solutions is that their next question will probably be something along the lines of: "Well, what if the matrix is so big that it doesn't fit into memory?" :)
Fairly brute force, O(n) scan with recursion on adjacent cells that are one value higher. Then sort of all possible answers to find longest (with largest sum, if more than one of same length):
python n_by_n_sequence.py matrix.in
[6, 7, 8, 9]
import sys
def max_sequence(vals, ndx, size):
# find the maximum sequential sequence starting from ndx
# vals is size * size list of unique numbers
# first check next right or left ndx +/- 1
# then up or down ndx +/- size
# and recurse, accounting for borders
is_left = ndx % size == 0
is_right = ndx % size == size-1
is_top = ndx / size == 0
is_bottom = ndx / size == size-1
seq = [vals[ndx]]
if not is_right:
if vals[ndx+1] == 1 + vals[ndx]:
return seq + max_sequence(vals, ndx+1, size)
if not is_bottom:
if vals[ndx+size] == 1 + vals[ndx]:
return seq + max_sequence(vals, ndx+size, size)
if not is_top:
if vals[ndx-size] == 1 + vals[ndx]:
return seq + max_sequence(vals, ndx-size, size)
if not is_left:
if vals[ndx-1] == 1 + vals[ndx]:
return seq + max_sequence(vals, ndx-1, size)
return seq
if __name__ == '__main__':
# expects an input file that looks like:
# 159
# 238
# 437
# for example
with open(sys.argv[1]) as fd:
matrix = fd.readlines()
size = len(matrix[0].strip())
flattened = ''.join([line.strip() for line in matrix]).strip()
flattened = [int(val) for val in flattened]
vals = []
for i in range(len(flattened)):
vals.append(max_sequence(flattened, i, size))
# find the longest by sorting, use maximum sum if more than one of same length
answers = [(answer, len(answer), sum(answer)) for answer in vals]
sorted_answers = sorted(answers, lambda v1, v2: v1[2] - v2[2] if v1[1] == v2[1] else v1[1] - v2[1])
print str(sorted_answers[-1][0])
#include <list>
#include <iostream>
using namespace std;
const int N = 3;
void checkNeighbour(int arr[N][N], int i, int j, list<int> & snake)
{
if(arr[i + 1][j] - arr[i][j] == 1 && i + 1 < N)
{
snake.push_back(arr[i + 1][j]);
checkNeighbour(arr, i + 1, j, snake);
}
if(arr[i - 1][j] - arr[i][j] == 1 && i - 1 >= 0)
{
snake.push_back(arr[i - 1][j]);
checkNeighbour(arr, i - 1, j, snake);
}
if(arr[i][j - 1] - arr[i][j] == 1 && j - 1 >= 0)
{
snake.push_back(arr[i][j - 1]);
checkNeighbour(arr, i, j - 1, snake);
}
if(arr[i][j + 1] - arr[i][j] == 1 && j + 1 < N)
{
snake.push_back(arr[i][j + 1]);
checkNeighbour(arr, i, j + 1, snake);
}
return;
}
int main()
{
int arr[N][N] = {1, 5, 9, 2, 3, 8, 4, 6, 7}, max_length = 0;
list<list<int>> list_of_snakes;
list<int> snake, //final snake
t_snake; //temporary snake
for(int i = 0; i < N; i++)
{
for(int j = 0; j < N; j++)
{
t_snake.push_back(arr[i][j]);
checkNeighbour(arr, i, j, t_snake);
if(t_snake.size() == 1)
{
t_snake.clear();
continue;
}
else list_of_snakes.push_back(t_snake);
t_snake.clear();
}
}
for(list<list<int>>::iterator i = list_of_snakes.begin(); i != list_of_snakes.end(); i++)
{
if(max_length < i->size())
{
max_length = i->size();
snake = *i;
}
}
for(list<int>::iterator i = snake.begin(); i != snake.end(); i++)
cout << *i << " ";
return 0;
}
Since all the content is exactly 1..N*N, create a map from these to the right cell (i,j).
Iterate, say with i, from 1 to N^2-1 - if the map.get(i) has distance of exactly 1 from map.get(i+1), augment this pair (say in List), when the above is false, if the List is not empty, print it out and empty.
(O(NXN)) memory and time
I can only find a way to calculate the length of the substring, can anyone help me to print out the string?
public class longestContinousSubInMatrix_Ski {
int[][] longest= new int[3][3];
int[][] original= {{1,5,6},{2,8,7},{3,9,4}};
public int findLongestGoogle(int i,int j){
int max = 0;
if(longest[i][j]!=0) return longest[i][j];
//up
if(j>0 && original[i][j] == original[i][j-1]+1){
if(max < findLongestGoogle(i,j-1)){
max = findLongestGoogle(i,j-1);
}
}
//down
if(j<2 && original[i][j] == original[i][j+1]+1){
if(max < findLongestGoogle(i,j+1)){
max = findLongestGoogle(i,j+1);
}
}
//left
if(i>0 && original[i][j] == original[i-1][j]+1){
if(max < findLongestGoogle(i-1,j)){
max = findLongestGoogle(i-1,j);
}
}
//right
if(i<2 && original[i][j] == original[i+1][j]+1){
if(max < findLongestGoogle(i+1,j)){
max = findLongestGoogle(i+1,j);
}
}
longest[i][j] = max + 1;
return longest[i][j];
}
public static void main(String args[]){
longestContinousSubInMatrix_Ski test = new longestContinousSubInMatrix_Ski();
//int re = test.find();
int max = 0;
for(int i=0;i<3;i++){
for(int j=0;j<3;j++){
test.findLongestGoogle(i,j);
}
}
for(int i=0;i<3;i++){
for(int j=0;j<3;j++){
max = Math.max(max, test.longest[i][j]);
}
}
System.out.print(max);
}
}
I can only find a way to calculate the length of the substring, can anyone help me to print out the string?
public class longestContinousSub{
int[][] longest= new int[3][3];
int[][] original= {{1,5,6},{2,8,7},{3,9,4}};
public int findLongestGoogle(int i,int j){
int max = 0;
if(longest[i][j]!=0) return longest[i][j];
//up
if(j>0 && original[i][j] == original[i][j-1]+1){
if(max < findLongestGoogle(i,j-1)){
max = findLongestGoogle(i,j-1);
}
}
//down
if(j<2 && original[i][j] == original[i][j+1]+1){
if(max < findLongestGoogle(i,j+1)){
max = findLongestGoogle(i,j+1);
}
}
//left
if(i>0 && original[i][j] == original[i-1][j]+1){
if(max < findLongestGoogle(i-1,j)){
max = findLongestGoogle(i-1,j);
}
}
//right
if(i<2 && original[i][j] == original[i+1][j]+1){
if(max < findLongestGoogle(i+1,j)){
max = findLongestGoogle(i+1,j);
}
}
longest[i][j] = max + 1;
return longest[i][j];
}
public static void main(String args[]){
longestContinousSub test = new longestContinousSub();
//int re = test.find();
int max = 0;
for(int i=0;i<3;i++){
for(int j=0;j<3;j++){
test.findLongestGoogle(i,j);
}
}
for(int i=0;i<3;i++){
for(int j=0;j<3;j++){
max = Math.max(max, test.longest[i][j]);
}
}
System.out.print(max);
}
}
I can only find a way to calculate the length of the substring, can anyone help me to print out the string?
public class longestContinousSub{
int[][] longest= new int[3][3];
int[][] original= {{1,5,6},{2,8,7},{3,9,4}};
public int findLongestGoogle(int i,int j){
int max = 0;
if(longest[i][j]!=0) return longest[i][j];
//up
if(j>0 && original[i][j] == original[i][j-1]+1){
if(max < findLongestGoogle(i,j-1)){
max = findLongestGoogle(i,j-1);
}
}
//down
if(j<2 && original[i][j] == original[i][j+1]+1){
if(max < findLongestGoogle(i,j+1)){
max = findLongestGoogle(i,j+1);
}
}
//left
if(i>0 && original[i][j] == original[i-1][j]+1){
if(max < findLongestGoogle(i-1,j)){
max = findLongestGoogle(i-1,j);
}
}
//right
if(i<2 && original[i][j] == original[i+1][j]+1){
if(max < findLongestGoogle(i+1,j)){
max = findLongestGoogle(i+1,j);
}
}
longest[i][j] = max + 1;
return longest[i][j];
}
public static void main(String args[]){
longestContinousSub test = new longestContinousSub();
//int re = test.find();
int max = 0;
for(int i=0;i<3;i++){
for(int j=0;j<3;j++){
test.findLongestGoogle(i,j);
}
}
for(int i=0;i<3;i++){
for(int j=0;j<3;j++){
max = Math.max(max, test.longest[i][j]);
}
}
System.out.print(max);
}
}
I can only find a way to calculate the length of the substring, can anyone help me to print out the string?
public class longestContinousSub{
int[][] longest= new int[3][3];
int[][] original= {{1,5,6},{2,8,7},{3,9,4}};
public int findLongestGoogle(int i,int j){
int max = 0;
if(longest[i][j]!=0) return longest[i][j];
//up
if(j>0 && original[i][j] == original[i][j-1]+1){
if(max < findLongestGoogle(i,j-1)){
max = findLongestGoogle(i,j-1);
}
}
//down
if(j<2 && original[i][j] == original[i][j+1]+1){
if(max < findLongestGoogle(i,j+1)){
max = findLongestGoogle(i,j+1);
}
}
//left
if(i>0 && original[i][j] == original[i-1][j]+1){
if(max < findLongestGoogle(i-1,j)){
max = findLongestGoogle(i-1,j);
}
}
//right
if(i<2 && original[i][j] == original[i+1][j]+1){
if(max < findLongestGoogle(i+1,j)){
max = findLongestGoogle(i+1,j);
}
}
longest[i][j] = max + 1;
return longest[i][j];
}
public static void main(String args[]){
longestContinousSub test = new longestContinousSub();
//int re = test.find();
int max = 0;
for(int i=0;i<3;i++){
for(int j=0;j<3;j++){
test.findLongestGoogle(i,j);
}
}
for(int i=0;i<3;i++){
for(int j=0;j<3;j++){
max = Math.max(max, test.longest[i][j]);
}
}
System.out.print(max);
}
}
I can only find a way to calculate the length of the substring, can anyone help me to print out the string?
public class longestContinousSub{
int[][] longest= new int[3][3];
int[][] original= {{1,5,6},{2,8,7},{3,9,4}};
public int findLongestGoogle(int i,int j){
int max = 0;
if(longest[i][j]!=0) return longest[i][j];
//up
if(j>0 && original[i][j] == original[i][j-1]+1){
if(max < findLongestGoogle(i,j-1)){
max = findLongestGoogle(i,j-1);
}
}
//down
if(j<2 && original[i][j] == original[i][j+1]+1){
if(max < findLongestGoogle(i,j+1)){
max = findLongestGoogle(i,j+1);
}
}
//left
if(i>0 && original[i][j] == original[i-1][j]+1){
if(max < findLongestGoogle(i-1,j)){
max = findLongestGoogle(i-1,j);
}
}
//right
if(i<2 && original[i][j] == original[i+1][j]+1){
if(max < findLongestGoogle(i+1,j)){
max = findLongestGoogle(i+1,j);
}
}
longest[i][j] = max + 1;
return longest[i][j];
}
public static void main(String args[]){
longestContinousSub test = new longestContinousSub();
//int re = test.find();
int max = 0;
for(int i=0;i<3;i++){
for(int j=0;j<3;j++){
test.findLongestGoogle(i,j);
}
}
for(int i=0;i<3;i++){
for(int j=0;j<3;j++){
max = Math.max(max, test.longest[i][j]);
}
}
System.out.print(max);
}
}
I can only find a way to calculate the length of the substring, can anyone help me to print out the string?
public class longestContinousSub{
int[][] longest= new int[3][3];
int[][] original= {{1,5,6},{2,8,7},{3,9,4}};
public int findLongestGoogle(int i,int j){
int max = 0;
if(longest[i][j]!=0) return longest[i][j];
//up
if(j>0 && original[i][j] == original[i][j-1]+1){
if(max < findLongestGoogle(i,j-1)){
max = findLongestGoogle(i,j-1);
}
}
//down
if(j<2 && original[i][j] == original[i][j+1]+1){
if(max < findLongestGoogle(i,j+1)){
max = findLongestGoogle(i,j+1);
}
}
//left
if(i>0 && original[i][j] == original[i-1][j]+1){
if(max < findLongestGoogle(i-1,j)){
max = findLongestGoogle(i-1,j);
}
}
//right
if(i<2 && original[i][j] == original[i+1][j]+1){
if(max < findLongestGoogle(i+1,j)){
max = findLongestGoogle(i+1,j);
}
}
longest[i][j] = max + 1;
return longest[i][j];
}
public static void main(String args[]){
longestContinousSub test = new longestContinousSub();
//int re = test.find();
int max = 0;
for(int i=0;i<3;i++){
for(int j=0;j<3;j++){
test.findLongestGoogle(i,j);
}
}
for(int i=0;i<3;i++){
for(int j=0;j<3;j++){
max = Math.max(max, test.longest[i][j]);
}
}
System.out.print(max);
}
}
I can only find a way to calculate the length of the substring, can anyone help me to print out the string?
public class longestContinousSub{
int[][] longest= new int[3][3];
int[][] original= {{1,5,6},{2,8,7},{3,9,4}};
public int findLongestGoogle(int i,int j){
int max = 0;
if(longest[i][j]!=0) return longest[i][j];
//up
if(j>0 && original[i][j] == original[i][j-1]+1){
if(max < findLongestGoogle(i,j-1)){
max = findLongestGoogle(i,j-1);
}
}
//down
if(j<2 && original[i][j] == original[i][j+1]+1){
if(max < findLongestGoogle(i,j+1)){
max = findLongestGoogle(i,j+1);
}
}
//left
if(i>0 && original[i][j] == original[i-1][j]+1){
if(max < findLongestGoogle(i-1,j)){
max = findLongestGoogle(i-1,j);
}
}
//right
if(i<2 && original[i][j] == original[i+1][j]+1){
if(max < findLongestGoogle(i+1,j)){
max = findLongestGoogle(i+1,j);
}
}
longest[i][j] = max + 1;
return longest[i][j];
}
public static void main(String args[]){
longestContinousSub test = new longestContinousSub();
//int re = test.find();
int max = 0;
for(int i=0;i<3;i++){
for(int j=0;j<3;j++){
test.findLongestGoogle(i,j);
}
}
for(int i=0;i<3;i++){
for(int j=0;j<3;j++){
max = Math.max(max, test.longest[i][j]);
}
}
System.out.print(max);
}
}
I can only find a way to calculate the length of the substring, can anyone help me to print out the string?
public class longestContinousSub{
int[][] longest= new int[3][3];
int[][] original= {{1,5,6},{2,8,7},{3,9,4}};
public int findLongestGoogle(int i,int j){
int max = 0;
if(longest[i][j]!=0) return longest[i][j];
//up
if(j>0 && original[i][j] == original[i][j-1]+1){
if(max < findLongestGoogle(i,j-1)){
max = findLongestGoogle(i,j-1);
}
}
//down
if(j<2 && original[i][j] == original[i][j+1]+1){
if(max < findLongestGoogle(i,j+1)){
max = findLongestGoogle(i,j+1);
}
}
//left
if(i>0 && original[i][j] == original[i-1][j]+1){
if(max < findLongestGoogle(i-1,j)){
max = findLongestGoogle(i-1,j);
}
}
//right
if(i<2 && original[i][j] == original[i+1][j]+1){
if(max < findLongestGoogle(i+1,j)){
max = findLongestGoogle(i+1,j);
}
}
longest[i][j] = max + 1;
return longest[i][j];
}
public static void main(String args[]){
longestContinousSub test = new longestContinousSub();
//int re = test.find();
int max = 0;
for(int i=0;i<3;i++){
for(int j=0;j<3;j++){
test.findLongestGoogle(i,j);
}
}
for(int i=0;i<3;i++){
for(int j=0;j<3;j++){
max = Math.max(max, test.longest[i][j]);
}
}
System.out.print(max);
}
}
I can only find a way to calculate the length of the substring, can anyone help me to print out the string?
public class longestContinousSub{
int[][] longest= new int[3][3];
int[][] original= {{1,5,6},{2,8,7},{3,9,4}};
public int findLongestGoogle(int i,int j){
int max = 0;
if(longest[i][j]!=0) return longest[i][j];
//up
if(j>0 && original[i][j] == original[i][j-1]+1){
if(max < findLongestGoogle(i,j-1)){
max = findLongestGoogle(i,j-1);
}
}
//down
if(j<2 && original[i][j] == original[i][j+1]+1){
if(max < findLongestGoogle(i,j+1)){
max = findLongestGoogle(i,j+1);
}
}
//left
if(i>0 && original[i][j] == original[i-1][j]+1){
if(max < findLongestGoogle(i-1,j)){
max = findLongestGoogle(i-1,j);
}
}
//right
if(i<2 && original[i][j] == original[i+1][j]+1){
if(max < findLongestGoogle(i+1,j)){
max = findLongestGoogle(i+1,j);
}
}
longest[i][j] = max + 1;
return longest[i][j];
}
public static void main(String args[]){
longestContinousSub test = new longestContinousSub();
//int re = test.find();
int max = 0;
for(int i=0;i<3;i++){
for(int j=0;j<3;j++){
test.findLongestGoogle(i,j);
}
}
for(int i=0;i<3;i++){
for(int j=0;j<3;j++){
max = Math.max(max, test.longest[i][j]);
}
}
System.out.print(max);
}
}
I can only find a way to calculate the length of the substring, can anyone help me to print out the string?
public class longestContinousSub{
int[][] longest= new int[3][3];
int[][] original= {{1,5,6},{2,8,7},{3,9,4}};
public int findLongestGoogle(int i,int j){
int max = 0;
if(longest[i][j]!=0) return longest[i][j];
//up
if(j>0 && original[i][j] == original[i][j-1]+1){
if(max < findLongestGoogle(i,j-1)){
max = findLongestGoogle(i,j-1);
}
}
//down
if(j<2 && original[i][j] == original[i][j+1]+1){
if(max < findLongestGoogle(i,j+1)){
max = findLongestGoogle(i,j+1);
}
}
//left
if(i>0 && original[i][j] == original[i-1][j]+1){
if(max < findLongestGoogle(i-1,j)){
max = findLongestGoogle(i-1,j);
}
}
//right
if(i<2 && original[i][j] == original[i+1][j]+1){
if(max < findLongestGoogle(i+1,j)){
max = findLongestGoogle(i+1,j);
}
}
longest[i][j] = max + 1;
return longest[i][j];
}
public static void main(String args[]){
longestContinousSub test = new longestContinousSub();
//int re = test.find();
int max = 0;
for(int i=0;i<3;i++){
for(int j=0;j<3;j++){
test.findLongestGoogle(i,j);
}
}
for(int i=0;i<3;i++){
for(int j=0;j<3;j++){
max = Math.max(max, test.longest[i][j]);
}
}
System.out.print(max);
}
}
I can only find a way to calculate the length of the substring, can anyone help me to print out the string?
public class longestContinousSub{
int[][] longest= new int[3][3];
int[][] original= {{1,5,6},{2,8,7},{3,9,4}};
public int findLongestGoogle(int i,int j){
int max = 0;
if(longest[i][j]!=0) return longest[i][j];
//up
if(j>0 && original[i][j] == original[i][j-1]+1){
if(max < findLongestGoogle(i,j-1)){
max = findLongestGoogle(i,j-1);
}
}
//down
if(j<2 && original[i][j] == original[i][j+1]+1){
if(max < findLongestGoogle(i,j+1)){
max = findLongestGoogle(i,j+1);
}
}
//left
if(i>0 && original[i][j] == original[i-1][j]+1){
if(max < findLongestGoogle(i-1,j)){
max = findLongestGoogle(i-1,j);
}
}
//right
if(i<2 && original[i][j] == original[i+1][j]+1){
if(max < findLongestGoogle(i+1,j)){
max = findLongestGoogle(i+1,j);
}
}
longest[i][j] = max + 1;
return longest[i][j];
}
public static void main(String args[]){
longestContinousSub test = new longestContinousSub();
//int re = test.find();
int max = 0;
for(int i=0;i<3;i++){
for(int j=0;j<3;j++){
test.findLongestGoogle(i,j);
}
}
for(int i=0;i<3;i++){
for(int j=0;j<3;j++){
max = Math.max(max, test.longest[i][j]);
}
}
System.out.print(max);
}
}
I can only find a way to calculate the length of the substring, can anyone help me to print out the string?
public class longestContinousSub{
int[][] longest= new int[3][3];
int[][] original= {{1,5,6},{2,8,7},{3,9,4}};
public int findLongestGoogle(int i,int j){
int max = 0;
if(longest[i][j]!=0) return longest[i][j];
//up
if(j>0 && original[i][j] == original[i][j-1]+1){
if(max < findLongestGoogle(i,j-1)){
max = findLongestGoogle(i,j-1);
}
}
//down
if(j<2 && original[i][j] == original[i][j+1]+1){
if(max < findLongestGoogle(i,j+1)){
max = findLongestGoogle(i,j+1);
}
}
//left
if(i>0 && original[i][j] == original[i-1][j]+1){
if(max < findLongestGoogle(i-1,j)){
max = findLongestGoogle(i-1,j);
}
}
//right
if(i<2 && original[i][j] == original[i+1][j]+1){
if(max < findLongestGoogle(i+1,j)){
max = findLongestGoogle(i+1,j);
}
}
longest[i][j] = max + 1;
return longest[i][j];
}
public static void main(String args[]){
longestContinousSub test = new longestContinousSub();
//int re = test.find();
int max = 0;
for(int i=0;i<3;i++){
for(int j=0;j<3;j++){
test.findLongestGoogle(i,j);
}
}
for(int i=0;i<3;i++){
for(int j=0;j<3;j++){
max = Math.max(max, test.longest[i][j]);
}
}
System.out.print(max);
}
}
I can only find a way to calculate the length of the substring, can anyone help me to print out the string?
public class longestContinousSub{
int[][] longest= new int[3][3];
int[][] original= {{1,5,6},{2,8,7},{3,9,4}};
public int findLongestGoogle(int i,int j){
int max = 0;
if(longest[i][j]!=0) return longest[i][j];
//up
if(j>0 && original[i][j] == original[i][j-1]+1){
if(max < findLongestGoogle(i,j-1)){
max = findLongestGoogle(i,j-1);
}
}
//down
if(j<2 && original[i][j] == original[i][j+1]+1){
if(max < findLongestGoogle(i,j+1)){
max = findLongestGoogle(i,j+1);
}
}
//left
if(i>0 && original[i][j] == original[i-1][j]+1){
if(max < findLongestGoogle(i-1,j)){
max = findLongestGoogle(i-1,j);
}
}
//right
if(i<2 && original[i][j] == original[i+1][j]+1){
if(max < findLongestGoogle(i+1,j)){
max = findLongestGoogle(i+1,j);
}
}
longest[i][j] = max + 1;
return longest[i][j];
}
public static void main(String args[]){
longestContinousSub test = new longestContinousSub();
//int re = test.find();
int max = 0;
for(int i=0;i<3;i++){
for(int j=0;j<3;j++){
test.findLongestGoogle(i,j);
}
}
for(int i=0;i<3;i++){
for(int j=0;j<3;j++){
max = Math.max(max, test.longest[i][j]);
}
}
System.out.print(max);
}
}
simple my version
public class LongContSeqMatrix {
/*
* Given a NxN matrix which contains all distinct 1 to n^2 numbers, write code to print
* sequence of increasing adjacent sequential numbers.
*
*/
static int [][] array = {{5,4,9},{6,3,2},{7,8,1}};
static String contSeq = "";
static int N = 3;
public static void main(String[] args) {
String finalLong = "";
for(int i=0;i<N*N;i++){
int row = i / N;
int col = i % N;
contSeq = "" + array[row][col];
getContSeq(i);
if(finalLong.length() < contSeq.length())
finalLong = contSeq;
}
System.out.println("finalLong-"+finalLong);
}
static void getContSeq(int currentIndx){
if(currentIndx >= 0 && currentIndx < N*N){
int row = currentIndx / N;
int col = currentIndx % N;
if(col < (N-1) && (array[row][col] + 1) == array[row][col+1] ){
contSeq = contSeq + array[row][col+1];
getContSeq(currentIndx+1);
}
if(row < (N-1) && (array[row][col] + 1) == array[row+1][col] ){
contSeq = contSeq + array[row+1][col];
getContSeq(currentIndx+N);
}
if(row > 0 && (array[row][col] + 1) == array[row-1][col] ){
contSeq = contSeq + array[row-1][col];
getContSeq(currentIndx-N);
}
if(col > 0 && (array[row][col] + 1) == array[row][col-1] ){
contSeq = contSeq + array[row][col-1];
getContSeq(currentIndx-1);
}
}
}
}
Could anyone please explain the question a bit in detail? My confusion stems from the concept that matrices are usually read 1 row at a time - top down. I am unable to see 6 7 8 9 as adjacent numbers, unless seen visually. matrix [row] [column] is the general declaration i have seen till now. A lot of folks are attempting the question means I am missing something here. Appreciate any help. Thanks!
Here is another solution.
First we construct a graph, one node for each element in the matrix.
Then we add directed edges for every pair of adjacent nodes (a-->b) where b-1 == a.
Finally, we re-loop over all nodes checking the maximum length run by following the edges of each child node until no more exist.
When this final loop finishes we've noted the maximum length run and we return it.
We are looping over the input 3 times, but I belive the running time is O(n) where n is the size of the matrix.
def get_adjacent_increasing_run(matrix):
# Build Graph
graph = Graph()
# Add nodes
for rIdx in xrange(0, len(matrix)):
for cIdx in xrange(0, len(matrix[rIdx])):
nodeIdx = matrixCoords2GraphIdx(matrix, rIdx, cIdx)
graph.addNode(Node(nodeIdx, data=matrix[rIdx][cIdx]))
# Add directed edges for consecutive neighbors
for rIdx in xrange(0, len(matrix)):
for cIdx in xrange(0, len(matrix[rIdx])):
myNodeIdx = matrixCoords2GraphIdx(matrix, rIdx, cIdx)
# Locate neighbors values in matrix: [left, right, top, bottom]
for neighbor in [ (rIdx-1,cIdx), (rIdx+1,cIdx), (rIdx,cIdx-1), (rIdx,cIdx+1)]:
(neighborRIdx, neighborCIdx) = neighbor
if neighborRIdx < 0 or neighborRIdx >= len(matrix):
continue
if neighborCIdx < 0 or neighborCIdx >= len(matrix[neighborRIdx]):
continue
if matrix[neighborRIdx][neighborCIdx] - 1 == matrix[rIdx][cIdx]:
neighborNodeIdx = matrixCoords2GraphIdx(matrix, neighborRIdx, neighborCIdx)
graph.addEdge(myNodeIdx, neighborNodeIdx)
break # Only one value can be chosen
# Find longest run
curLongestRun = []
for node in graph.nodes:
thisRun = getRun(graph, node)
if len(thisRun) > len(curLongestRun):
curLongestRun = thisRun
return curLongestRun
def getRun(graph, node):
run = []
while True:
run.append(node.data)
edges = graph.getEdges(node)
if not edges:
break
node = graph.nodes[edges[0].dstNodeIdx]
return run
def matrixCoords2GraphIdx(matrix, rIdx, cIdx):
return rIdx*len(matrix[rIdx]) + cIdx
/*
Given a NxN matrix which contains all distinct 1 to n^2 numbers, write code to print sequence of increasing adjacent sequential numbers.
ex:
1 5 9
2 3 8
4 6 7
should print
6 7 8 9
for visual c++ 2005
*/
#include "stdafx.h"
#include <iostream>
#include <conio.h>
#include <algorithm>
#include <map>
#include <vector>
#include <list>
#include <iterator>
#include <math.h>
#include <numeric>
#include <sstream>
#include <stack>
#include <string>
using namespace std;
map<pair<int, int>, bool> mapIsNeighbor;
class Solution
{
public:
static void SetNeighbor( int i, int j)
{
if ( i < j )
mapIsNeighbor[ make_pair( i, j ) ] = true;
else
mapIsNeighbor[ make_pair( j, i ) ] = true;
}
static bool IsNeighbor( int i, int j)
{
if ( i < j )
return mapIsNeighbor.end() != mapIsNeighbor.find(make_pair( i, j ));
else
return mapIsNeighbor.end() != mapIsNeighbor.find(make_pair( j, i ));
}
static vector<int> FindIncNumbers(vector<vector<int>> vecInput)
{
vector<int> vecResult;
size_t N = vecInput.size();
for ( size_t i = 0; i < N; i ++)
for( size_t j = 0; j < N; j ++)
{
if ( j + 1 < N )
SetNeighbor( vecInput[i][j], vecInput[i][j + 1]);
if ( i + 1 < N )
SetNeighbor( vecInput[i][j], vecInput[i + 1][j]);
}
int nLength = 1;
vecResult.push_back(1);
int nFirstInt = 2;
while ( nFirstInt <= static_cast<int>( N * N ) )
{
int nInt = nFirstInt;
int nLenghTemp = 1;
while ( IsNeighbor( nInt - 1, nInt ) )
{
if ( nInt <= static_cast<int>( N * N ) )
nInt ++;
}
nLenghTemp = nInt - nFirstInt + 1;
if ( nLenghTemp > nLength )
{
nLength = nLenghTemp;
vecResult.clear();
for ( int i = nFirstInt - 1; i < nInt; i ++ )
vecResult.push_back( i );
}
if ( nFirstInt != nInt )
nFirstInt = nInt;
else
nFirstInt ++;
}
return vecResult;
}
};
int _tmain(int argc, _TCHAR* argv[])
{
// prepare input data
int arrLine1[] = {1,5,9};
int arrLine2[] = {2,3,8};
int arrLine3[] = {4,6,7};
vector< vector< int > > vecInput;
vecInput.push_back( vector<int>( arrLine1, arrLine1 + sizeof( arrLine1 ) / sizeof( int ) ));
vecInput.push_back( vector<int>( arrLine2, arrLine2 + sizeof( arrLine2 ) / sizeof( int ) ));
vecInput.push_back( vector<int>( arrLine3, arrLine3 + sizeof( arrLine3 ) / sizeof( int ) ));
vector<int> vecResult = Solution::FindIncNumbers( vecInput );
// output result
copy( vecResult.begin(), vecResult.end(), ostream_iterator<int>( cout, " ") );
_getch();
return 0;
}
#include <stdio.h>
#include <iostream>
using namespace std;
bool** check;
int searchLongestAdjaSeq(int**, int*, int);
int searchLongestAdjaSeqInv(int**, int*, int, int, int);
int main() {
int i, j, N, len;
int **matrix, *seq;
cout << "size of matrix: ";
cin >> N;
matrix = new int *[N];
check = new bool *[N];
for(i=0; i<N; i++) {
matrix[i] = new int [N];
check[i] = new bool [N];
}
cout << "fill NXN matrix: ";
for(i=0; i<N; i++) {
for(j=0; j<N; j++) {
cin >> matrix[i][j];
check[i][j] = false;
}
}
seq = new int [N*N];
len = searchLongestAdjaSeq(matrix, seq, N);
cout << "seq: ";
for(i=0; i<len; i++)
printf("%d ", seq[i]);
return 0;
}
int searchLongestAdjaSeq(int** matrix, int* seq, int N)
{
int i, j, k, ret, len;
int *tmpseq;
ret = 0;
for(i=0; i<N; i++) {
for(j=0; j<N; j++) {
if(check[i][j])
continue;
tmpseq = new int [N*N];
len = searchLongestAdjaSeqInv(matrix, tmpseq, N, i, j);
if(len > ret) {
for(k=0; k<len; k++)
seq[k] = tmpseq[k];
ret = len;
}
delete [] tmpseq;
}
}
return ret;
}
int searchLongestAdjaSeqInv(int** matrix, int* seq, int N, int i, int j)
{
int ret, k;
int *tmpseq;
ret = 0;
check[i][j] = true;
tmpseq = new int [N*N];
if (i!=0 && matrix[i][j]+1 == matrix[i-1][j])
ret = searchLongestAdjaSeqInv(matrix, tmpseq, N, i-1, j);
else if (i!=N-1 && matrix[i][j]+1 == matrix[i+1][j])
ret = searchLongestAdjaSeqInv(matrix, tmpseq, N, i+1, j);
else if (j!=0 && matrix[i][j]+1 == matrix[i][j-1])
ret = searchLongestAdjaSeqInv(matrix, tmpseq, N, i, j-1);
else if (j!=N-1 && matrix[i][j]+1 == matrix[i][j+1])
ret = searchLongestAdjaSeqInv(matrix, tmpseq, N, i, j+1);
ret++;
seq[0] = matrix[i][j];
for(k=1; k<ret; k++)
seq[k] = tmpseq[k-1];
return ret;
}
#include <stdio.h>
#include <iostream>
using namespace std;
bool** check;
int searchLongestAdjaSeq(int**, int*, int);
int searchLongestAdjaSeqInv(int**, int*, int, int, int);
int main() {
int i, j, N, len;
int **matrix, *seq;
cout << "size of matrix: ";
cin >> N;
matrix = new int *[N];
check = new bool *[N];
for(i=0; i<N; i++) {
matrix[i] = new int [N];
check[i] = new bool [N];
}
cout << "fill NXN matrix: ";
for(i=0; i<N; i++) {
for(j=0; j<N; j++) {
cin >> matrix[i][j];
check[i][j] = false;
}
}
seq = new int [N*N];
len = searchLongestAdjaSeq(matrix, seq, N);
cout << "seq: ";
for(i=0; i<len; i++)
printf("%d ", seq[i]);
return 0;
}
int searchLongestAdjaSeq(int** matrix, int* seq, int N)
{
int i, j, k, ret, len;
int *tmpseq;
ret = 0;
for(i=0; i<N; i++) {
for(j=0; j<N; j++) {
if(check[i][j])
continue;
tmpseq = new int [N*N];
len = searchLongestAdjaSeqInv(matrix, tmpseq, N, i, j);
if(len > ret) {
for(k=0; k<len; k++)
seq[k] = tmpseq[k];
ret = len;
}
delete [] tmpseq;
}
}
return ret;
}
int searchLongestAdjaSeqInv(int** matrix, int* seq, int N, int i, int j)
{
int ret, k;
int *tmpseq;
ret = 0;
check[i][j] = true;
tmpseq = new int [N*N];
if (i!=0 && matrix[i][j]+1 == matrix[i-1][j])
ret = searchLongestAdjaSeqInv(matrix, tmpseq, N, i-1, j);
else if (i!=N-1 && matrix[i][j]+1 == matrix[i+1][j])
ret = searchLongestAdjaSeqInv(matrix, tmpseq, N, i+1, j);
else if (j!=0 && matrix[i][j]+1 == matrix[i][j-1])
ret = searchLongestAdjaSeqInv(matrix, tmpseq, N, i, j-1);
else if (j!=N-1 && matrix[i][j]+1 == matrix[i][j+1])
ret = searchLongestAdjaSeqInv(matrix, tmpseq, N, i, j+1);
ret++;
seq[0] = matrix[i][j];
for(k=1; k<ret; k++)
seq[k] = tmpseq[k-1];
return ret;
}
void increasing_adjacent_sequential_numbers_kernel(int* m, int i, int j, int nrow, int ncol, int &length) {
// reject condition1, outreach the bounds, condition2:
bool up = false;
bool down = false;
bool left = false;
bool right = false;
if(i >= nrow || j >= ncol || i < 0 || j < 0) return;
if(j-1 >= 0) {
if(m[i*nrow+j-1]-m[i*nrow+j] == 1) left = true;
}
if(j+1 <= ncol) {
if(m[i*nrow+j+1]-m[i*nrow+j] == 1) right = true;
}
if(i-1 >= 0) {
if(m[(i-1)*nrow+j]-m[i*nrow+j] == 1) up = true;
}
if(i+1 <= nrow) {
if(m[(i+1)*nrow+j]-m[i*nrow+j] == 1) down = true;
}
printf("visiting:%d\n",m[i*nrow+j]);
//accept
length++;
if(up) {
increasing_adjacent_sequential_numbers_kernel(m, i-1, j, nrow, ncol, length);
}
if(down) {
increasing_adjacent_sequential_numbers_kernel(m, i+1, j, nrow, ncol, length);
}
if(right) {
increasing_adjacent_sequential_numbers_kernel(m, i, j+1, nrow, ncol, length);
}
if(left) {
increasing_adjacent_sequential_numbers_kernel(m, i, j-1, nrow, ncol, length);
}
}
void increasing_adjacent_sequential_numbers() {
int m[9] = {1,5,9,
2,3,8,
4,6,7};
int max = 0;
for(int i = 0; i < 3; i++) {
for(int j = 0; j <3; j++) {
int length = 0;
increasing_adjacent_sequential_numbers_kernel(m, i, j, 3, 3, length);
printf("length:%d\n", length);
}
}
}
To explain my code above, I'm using the backtracking techniques to recursively find the adjacent numbers. Precisely, I'm looking for the number which is 1 bigger than current stand in the up, down, left, right spots. If there exists such number than go that direction.
This algorithm will not work well since it only consider the increasing scenario. For example, the worst case should be:
{1,2,3,
6,5,4,
7,8,9} it will traverse all the previous numbers at each step. To improve the algorithm, we need additional space to trade off time which I have not gave a through thought yet.
static int[][] cache;
//find biggest value in cache
static int max = -1;
static int max_i = -1;
static int max_j = -1;
public static void main(String[] args)
{
int array[][] = {{1, 5, 9},
{2, 3, 8},
{4, 6, 7}};
solve(array);
System.out.println();
}
static void solve(int[][] mat)
{
cache = new int[mat.length][mat.length];
for (int i = 0; i < mat.length; i++)
{
for (int j = 0; j < mat.length; j++)
{
cache[i][j] = -1;
}
}
for (int i = 0; i < mat.length; i++)
{
for (int j = 0; j < mat.length; j++)
{
findSeqLength(mat, i, j);
}
}
int start = mat[max_i][max_j];
//walk the result.
for (int i = 0; i <= max + 1; i++)
{
System.out.print(start + i);
}
}
static void findSeqLength(int[][] mat, int i, int j)
{
//out of bound
if (i < 0 || i > mat.length - 1 || j < 0 || j > mat.length - 1)
{
return;
}
//checked
if (cache[i][j] != -1)
{
return;
}
//check
peek(mat, i, j, i, j + 1);
peek(mat, i, j, i + 1, j);
peek(mat, i, j, i - 1, j);
peek(mat, i, j, i, j - 1);
}
static void peek(int[][] mat, int i, int j, int target_i, int target_j)
{
if (target_i < 0 || target_i > mat.length - 1 || target_j < 0 || target_j > mat.length - 1)
{
return;
}
if (mat[target_i][target_j] - 1 == mat[i][j])
{
int temp = cache[target_i][target_j];
if (temp == -1)
{
findSeqLength(mat, target_i, target_j);
}
temp = cache[target_i][target_j];
if (cache[i][j] <= temp)
{
cache[i][j] = temp + 1;
if (cache[i][j] > max)
{
max = cache[i][j];
max_i = i;
max_j = j;
}
}
}
}
Fully testable code
Recursive JavaScript solution - returns an array of the longest sequence:
var matrixSequence = function(matrix) {
var n = matrix.length;
var result = [matrix[0][0]];
var findSequence = function(position, visited, sequence) {
visited = visited || {};
visited[position] = true;
sequence = sequence || [];
var value = matrix[position[0]][position[1]];
sequence.push(value);
var nextPosition = [];
// move up
nextPosition[0] = position[0] - 1;
nextPosition[1] = position[1];
if ( nextPosition[0] >= 0 && !visited[nextPosition] ) {
if ( value + 1 === matrix[nextPosition[0]][nextPosition[1]] ) {
visited[position] = true;
findSequence(nextPosition, visited, sequence, value);
}
}
// move down
nextPosition[0] = position[0] + 1;
nextPosition[1] = position[1];
if ( nextPosition[0] < n && !visited[nextPosition] ) {
if ( value + 1 === matrix[nextPosition[0]][nextPosition[1]] ) {
visited[position] = true;
findSequence(nextPosition, visited, sequence, value);
}
}
// move left
nextPosition[0] = position[0];
nextPosition[1] = position[1] - 1;
if ( nextPosition[1] >= 0 && !visited[nextPosition] ) {
if ( value + 1 === matrix[nextPosition[0]][nextPosition[1]] ) {
visited[position] = true;
findSequence(nextPosition, visited, sequence, value);
}
}
// move right
nextPosition[0] = position[0];
nextPosition[1] = position[1] + 1;
if ( nextPosition[1] < n && !visited[nextPosition] ) {
if ( value + 1 === matrix[nextPosition[0]][nextPosition[1]] ) {
visited[position] = true;
findSequence(nextPosition, visited, sequence, value);
}
}
if ( sequence.length > result.length ) {
result = sequence;
}
};
for ( var i = 0; i < n; i++ ) {
for ( var j = 0; j < n; j++ ) {
findSequence([i,j]);
}
}
return result;
};
O(n)
void print_longest_adj(const vector<vector<int>>& matrix) {
const int DUMMY = -2;
const int N = matrix.size();
vector<bool> adjacent(N * N + 1);
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
int a = matrix[i][j];
int b = i+1 < N ? matrix[i+1][j] : DUMMY;
int c = j+1 < N ? matrix[i][j+1] : DUMMY;
if (a+1 == b || a+1 == c)
adjacent[a] = true;
if (b+1 == a)
adjacent[b] = true;
if (c+1 == a)
adjacent[c] = true;
}
}
int max_length = 0, max_first = 0, length = 0, first = 0;
for (int i = 0; i < adjacent.size(); i++) {
if (adjacent[i]) {
length++;
if (length == 1)
first = i;
if (length > max_length) {
max_length = length;
max_first = first;
}
} else {
length = 0;
}
}
for (int i = 0; i <= max_length; i++)
printf("%d\n", max_first+i);
}
Basic idea:
use DFS. use another array, the initial values of it is 1. For an element array[i][j], if the value is larger than 1, then continue to check another element. Or recursively DFS to its adjacency, which the adjacency has its next number. The DFS will return the longest steps the adjacency can reach. So, the value of array[i][j] is DFS result plus 1.
time O(n^2), space O(n^2)
Here's a very simple way to do it. Make an array of booleans (or bits) of size N^2, where arr[i-1] indicates whether i+1 is adjacent to i. Then, iterate over the matrix, checking for each cell the four neighbors and populating the relevant entry in the boolean array. Then just look for the longest run of "true" values in the boolean array, which can be done with one pass.
- eugene.yarovoi July 15, 2014This approach is linear in time and space with the size of the input. The space needed is only 1 bit per element, so the constant factor is really low for space. The constant factor for time should be reasonably good as well because we only do a few array accesses and comparisons for each element in the input.