kill -9
BAN USERWe need to sort the array to be able to achieve O(n^2) performance.
void findTriplets(int *input, int size)
{
int a, b, c, i;
for (c = 0; c < size; c++)
{
int result = input[c] * input[c];
a = 0;
b = size - 1;
while (a <= b)
{
if ((input[a] * input[a]) + input[b] * input[b]) < result) /* a^2 + b^2 < c^2 */
a++;
else if (input[a] * input[a]) + input[b] * input[b]) > result) /* a^2 + b^2 > c^2 */
b--;
else
printf("triplet found: %d %d %d \n", input[a], input[b], input[c]);
}
}
}
}}}
Time: O(n^2) Space: O(1)
We can solve this problem with two temporary arrays, one for positive elements and one for negative elements in O(n) time.
Scan the input array if you hit a negative element store it in the negative array, if its a positive element store it in the positive array.
In the end simply scan these two arrays and copy the elements back to our original array
void sort(int *input, int n)
{
int *negative = malloc(sizeof(int) * n);
int negativeIndex = 0;
int *positive = malloc(sizeof(int) * n);
int positiveIndex = 0;
int zero = 0;
int i, temp;
for (i = 0; i < n; i++)
{
if (intput[i] < 0)
negative[negativeIndex++] = intput[i];
else if (intput[i] > 0)
positive[positiveIndex++] = input[i]
else
zero++;
}
for (i = 0; i < negativeIndex; i++)
input[i] = negative[i]; /* copy negative elements */
for (temp = 0; temp < zero; temp++, i++)
input[i] = 0; /* copy zeroes */
for (temp = 0; temp < positiveIndex; temp++, i++)
input[i] = positive[temp]; /* copy the positive elements */
}
We can also have an array maxVal[height] which is sized according to the height of the tree. Each entry in the array represents the maximum value at the level. Pseudocode looks like this
void findMaxLevels(tree *root, int level, int *maxVal)
{
if (!root)
return;
findMaxLevels(root->left, level+1, maxVal);
maxVal[level] = (maxVal[level] > root->data ? maxVal[level] : root->data);
findMaxLevels(root->right, level+1, maxVal);
}
We can simply print the array maxVal to get the maximum value at each level.
Instead of a hash table you can also use a bit vector to save space.
- kill -9 September 12, 2013Read input and set the corresponding bit in the bit vector
If bit is already set skip the input value as its a duplicate (because the bit set indicates we've seen the exact value before)