krantboy
BAN USERGuess the while loop should run until k>0
public class MergeArrays {
public static void main(String args[]){
int a[]={1,3,5,0,0,0};
int [] b={2,4,6};
merge (a,3,b,3);
print (a);
}
public static void merge(int[] a,int m,int[] b,int n){
int i=m-1;
int j=n-1;
int k=m+n-1;
while(k>0){
if(a[i]<b[j]){
a[k]=b[j];
k--;
j--;
}
else{
a[k]=a[i];
k--;
i--;
}
}
}
public static void print(int[] a){
for(int i=0;i<a.length;i++){
System.out.print(a[i]+",");
}
}
}
You can do binary search on each row.. TC: O(nlogn) and SC:O(1)
Or else eliminate the rows/columns by comparing the last elements of rows/columns.. Start from the upper right / lower left corner and eliminate the respective row with a single comparisons. No of comparisons would be less than 2n -1
TC: O(n) SC: O(1)
I would traverse the list with slow and fast pointers , with slow pointer visiting every node and fast pointer visiting alternative node.The slow pointer data is stored in a stack until the fast pointer(odd case) or its next reaches null(even case).Now compare the slow poniter data with the element popped from stack.If all the comparisons are true until the stack is empty, then it is a palindrome.
TC- Order of N
SC- O(N)
We can also think of an alternative solution without using the extra space.
No it should be longest common substring. Just do a check when returning the longest common substring whether it is a palindrome.. If it isn't then the original string doesn't contain a palindrome
- krantboy November 03, 2011