Sudheesh Singanamalla
BAN USEROne way to solve this with time complexity less than O(n^2) is to use a self balancing BST. AVL, Redblack etc.., can be used to get the solution in O(n Log n) time complexity
Initially we traverse the given array from right to left and insert all elements one by one in an AVL tree. While inserting a new key in an AVL tree, we first compare the key with root. We add it to the left / right accordingly and count the number of elements that are greater. We recursively follow the same approach for all nodes down the root.
#include <stdio.h>
#include <stdlib.h>
struct node {
int key;
struct node *left;
struct node *right;
int height;
int size;
};
int min(int a, int b);
int height(struct node *N) {
if (N == NULL)
return 0;
return N->height;
}
int size(struct node *N) {
if (N == NULL)
return 0;
return N->size;
}
int min(int a, int b) {
return (a < b)? a : b;
}
struct node* newNode(int key) {
struct node* node = (struct node*)
malloc(sizeof(struct node));
node->key = key;
node->left = NULL;
node->right = NULL;
node->height = 1;
node->size = 1;
return(node);
}
struct node *rightRotate(struct node *y) {
struct node *x = y->left;
struct node *T2 = x->right;
x->right = y;
y->left = T2;
y->height = min(height(y->left), height(y->right))+1;
x->height = min(height(x->left), height(x->right))+1;
y->size = size(y->left) + size(y->right) + 1;
x->size = size(x->left) + size(x->right) + 1;
return x;
}
struct node *leftRotate(struct node *x) {
struct node *y = x->right;
struct node *T2 = y->left;
y->left = x;
x->right = T2;
x->height = min(height(x->left), height(x->right))+1;
y->height = min(height(y->left), height(y->right))+1;
x->size = size(x->left) + size(x->right) + 1;
y->size = size(y->left) + size(y->right) + 1;
return y;
}
int getBalance(struct node *N) {
if (N == NULL)
return 0;
return height(N->left) - height(N->right);
}
struct node* insert(struct node* node, int key, int *count) {
if (node == NULL)
return(newNode(key));
if (key > node->key)
node->left = insert(node->left, key, count);
else
{
node->right = insert(node->right, key, count);
*count = *count + size(node->left) + 1;
}
node->height = min(height(node->left), height(node->right)) + 1;
node->size = size(node->left) + size(node->right) + 1;
int balance = getBalance(node);
if (balance > 1 && key > node->left->key)
return rightRotate(node);
if (balance < -1 && key < node->right->key)
return leftRotate(node);
if (balance > 1 && key < node->left->key)
{
node->left = leftRotate(node->left);
return rightRotate(node);
}
if (balance < -1 && key > node->right->key)
{
node->right = rightRotate(node->right);
return leftRotate(node);
}
return node;
}
void constructHigherArray (int arr[], int countHigherElements[], int n) {
int i, j;
struct node *root = NULL;
for (i = 0; i < n; i++)
countHigherElements[i] = 0;
for (i = n-1; i >= 0; i--)
{
root = insert(root, arr[i], &countHigherElements[i]);
}
}
void printArray(int arr[], int size) {
int i;
printf("\n");
for (i=0; i < size; i++)
printf("%d ", arr[i]);
}
int main() {
// int arr[] = {3,4,5,9,2,1,3};
int arr[] = {10, 6, 15, 20, 30, 5, 7, 3, 4, 5, 9, 2, 1, 3};
int n = sizeof(arr)/sizeof(arr[0]);
int *low = (int *)malloc(sizeof(int)*n);
constructHigherArray(arr, low, n);
printf("Following is the constructed larger count array");
printArray(low, n);
return 0;
}
Here's a JavaScript implementation
function sort(A,B) {
var newA = [];
for (var i=0; i<B.length; i++) {
var x = B.indexOf(i);
newA.push(A[x]);
}
return newA;
}
var A = ['C','D','E','F','G'];
var B = [3,0,4,1,2]
A = sort(A,B);
Here's a python implementation. Assuming that the source word and destination word needn't be of the same size, transformation could involve (+) adding / (-) removing a character from the word for the transformation too.
Considering all the words in the dictionary to be nodes in a graph, process the whole dictionary once and create the graph. Then given two words initiate a BFS from source to destination and we'll have the shortest chain of transformations required.
In the worst case, we might have to traverse the whole graph to find a transformation or a transformation may not exist at all. This function returns the list / array of the transformation strings, using len(returnedArray) we can get the required result.
One problem with this is that if there's no transformation it returns an empty transformation list [ ] and the len([ ]) is 0, but rather has to be shown as null, a simple if statement would resolve this.
- Sudheesh Singanamalla October 28, 2015