AlgChamp
BAN USER
Comments (8)
Reputation 35
Page:
1
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0
of 0 vote
You dont actually need a heap - can do in O(N^2). Idea is very similar to k-way merge on rows, but uses additional property that cols are sorted as well.
First merge row 0, col 0
Then move to [1][1], merge row 1, col1
Then move to [2][2], merge row 2, col2
O(N^2).
Pseudo code:
int onedarr[] = new int[N*N];
int ctr = 0;
for(int step = 0; step < N; ++step)
{
int rowIndex = step;
int colIndex = step;
onedarr[++ctr] = arr[rowIndex][colIndex];
for(int i = step+1; i < N; ++i)
{
if(rowIndex == N-1 || arr[i][colIndex] < arr[rowIndex][i])
{
onedarr[++ctr] = arr[i][colIndex++];
}
else
{
onedarr[++ctr] = arr[rowIndex++][i];
}
}
}
Page:
1
CareerCup is the world's biggest and best source for software engineering interview preparation. See all our resources.
Here is the dynamic programming recurrence for above soln:
- AlgChamp June 10, 2014IsValid(i): Is string ending at i valid
IsValid(0): false
IsValid(1): Lookup(str.Substring(0, 1))
IsValid(i): Lookup(str.Substring(0, i) OR
For j in 0..i-1 (IsValid(j) AND Lookup(str.Substring(j, i-j+1))