Avinash
BAN USERFlawless code ... Enjoy!!
Time O(n) .... Space O(1)
Below code also takes care of multiple space characters between two words...
void removeWords(char * str, char ch)
{
if(!str)
return;
int i = 0, j = 0;
while(str[j])
{
if(str[j] == ch)
{
while(str[j] && str[j] != ' ')
j++;
while(str[j] && str[j] == ' ')
j++;
}
else
{
while(str[j] && str[j] != ' ')
str[i++] = str[j++];
while(str[j] && str[j] == ' ')
str[i++] = str[j++];
}
}
str[i] = '\0';
}
Flawless Code...Enjoy!!!
Time O(n) ... Space (1)
Note: For simplicity I have not made these functions generic. After a little tweaking below code can sort list with 0 1 2 3 also.
Here we go:
void append(node* &head, node* &tail, node* n)
{
if(!head)
head = n;
else
tail->next = n;
tail = n;
}
void join(node*& a, node*& alast, node* b, node* blast)
{
if(!a)
{
a = b;
alast = blast;
}
else if(b)
{
alast->next = b;
alast = blast;
}
}
int sort123(node* &head)
{
if(!head)
return -1;
node* start[3] = {NULL,NULL,NULL};
node* end[3] = {NULL,NULL,NULL};
for(node* n = head; n; n = n->next)
{
int index = n->data;
if(index < 0 || index > 2)
return -1;
append(start[index],end[index],n);
}
head = start[0];
node* tail = end[0];
join(head,tail,start[1],end[1]);
join(head,tail,start[2],end[2]);
tail->next = NULL;
return 0;
}
First of all, thanks for pointing out the Time complexity... Below goes the code with O(n) ...
Secondly, there is nothing to laugh about NULL check. What if caller passes a NULL pointer ( acceptable in C++ )?
O(n) code...
void putZerosInFront(int arr[], int len)
{
if(!arr || len < 1)
return;
int i = len-1;
for(int j = i-1; j >=0; j--)
{
if(arr[i] == 0)
{
if(arr[j] != 0)
{
swap(arr[i],arr[j]);
i--;
}
}
else
{
i--;
}
}
}
Flawless code... Enjoy!!!
Time O(n) ... Space(1)
----------------------------------
Keep two pointers, one at lower end another at higher end ... similar when doing it for sorted array.
----------------------------------
I am using stack for simplicity of the algorithm, but you can use Morris traversal to achieve Space(1)... If you are not able to figure out to do it with Morris traversal, then let me know. I can provide the code for that too... but that would be a bit complex to understand... so better right your own :) ....
Here we go..... CHEERS!!!
void findPair(node* root, int sum, int &a, int &b)
{
a = -1;
b = -1;
// Base case '0' or '1' node in tree.
if((!root) || (!root->left && !root->right))
return;
node* n1 = root, *n2 = root;
stack<node*> p,q;
while(true)
{
if(n1)
{
p.push(n1);
n1 = n1->left;
}
else if(n2)
{
q.push(n2);
n2 = n2->right;
}
else if(!p.empty() && !q.empty())
{
n1 = p.top();
n2 = q.top();
// tree is already traversed
if(n1->data > n2->data)
return;
int cur_sum = n1->data + n2->data;
if(cur_sum == sum)
{
// found desired numbers
a = n1->data;
b = n2->data;
return;
}
else if(cur_sum < sum)
{
// move in forward direction
p.pop();
n1 = n1->right;
n2 = NULL;
}
else
{
// move in backward direction
q.pop();
n2 = n2->left;
n1 = NULL;
}
}
else
return;
}
}
Using a constant hash table...Here you go...
- Avinash September 20, 2012