A Boolean Matrix Question

Source

Given a boolean matrix mat[M][N] of size M X N, modify it such that if a matrix cell mat[i][j] is 1 (or true) then make all the cells of ith row and jth column as 1.

Example 1 

The matrix 
 1 0 
 0 0 
 should be changed to following 
 1 1
 1 0
   Example 2
 The matrix
 0 0 0
 0 0 1
 should be changed to following
 0 0 1
 1 1 1
   Example 3
 The matrix
 1 0 0 1
 0 0 1 0
 0 0 0 0
 should be changed to following
 1 1 1 1
 1 1 1 1
 1 0 1 1
  

(A Space Optimized Version of Method 1)

This method is a space optimized version of above method 1. This method uses the first row and first column of the input matrix in place of the auxiliary arrays row[] and col[] of method 1. So what we do is: first take care of first row and column and store the info about these two in two flag variables rowFlag and colFlag. Once we have this info, we can use first row and first column as auxiliary arrays and apply method 1 for submatrix (matrix excluding first row and first column) of size (M-1)*(N-1).

1) Scan the first row and set a variable rowFlag to indicate whether we need to set all 1s in first row or not.
2) Scan the first column and set a variable colFlag to indicate whether we need to set all 1s in first column or not.
3) Use first row and first column as the auxiliary arrays row[] and col[] respectively, consider the matrix as submatrix starting from second row and second column and apply method 1.
4) Finally, using rowFlag and colFlag, update first row and first column if needed.

Time Complexity: O(M*N)
Auxiliary Space: O(1)

Tries - implement insert and search

Source

Trie is an efficient information retrieval data structure. Using trie, search complexities can be brought to optimal limit (key length). If we store keys in binary search tree, a well balanced BST will need time proportional to M * log N, where M is maximum string length and N is number of keys in tree. Using trie, we can search the key in O(M) time. However the penalty is on trie storage requirements.

Every node of trie consists of multiple branches. Each branch represents a possible character of keys. We need to mark the last node of every key as leaf node. A trie node field value will be used to distinguish the node as leaf node (there are other uses of the value field). A simple structure to represent nodes of English alphabet can be as following,

struct trie_node

{

int value; /* Used to mark leaf nodes */

trie_node_t *children[ALPHABET_SIZE];

};

Inserting a key into trie is simple approach. Every character of input key is inserted as an individual trie node. Note that the children is an array of pointers to next level trie nodes. The key character acts as an index into the array children. If the input key is new or an extension of existing key, we need to construct non-existing nodes of the key, and mark leaf node. If the input key is prefix of existing key in trie, we simply mark the last node of key as leaf. The key length determines trie depth.

Searching for a key is similar to insert operation, however we only compare the characters and move down. The search can terminate due to end of string or lack of key in trie. In the former case, if thevalue field of last node is non-zero then the key exists in trie. In the second case, the search terminates without examining all the characters of key, since the key is not present in trie.

Insert and search costs O(key_length), however the memory requirements of trie isO(ALPHABET_SIZE * key_length * N) where N is number of keys in trie. There are efficient representation of trie nodes (e.g. compressed trie, ternary search tree, etc.) to minimize memory requirements of trie.

#include #include #include #define ARRAY_SIZE(a) sizeof(a)/sizeof(a[0]) // Alphabet size (# of symbols) #define ALPHABET_SIZE (26) // Converts key current character into index // use only 'a' through 'z' and lower case #define CHAR_TO_INDEX(c) ((int)c - (int)'a') // trie node typedef struct trie_node trie_node_t; struct trie_node { int value; trie_node_t *children[ALPHABET_SIZE]; }; // trie ADT typedef struct trie trie_t; struct trie { trie_node_t *root; int count; }; // Returns new trie node (initialized to NULLs) trie_node_t *getNode(void) { trie_node_t *pNode = NULL; pNode = (trie_node_t *)malloc(sizeof(trie_node_t)); if( pNode ) { int i; pNode->value = 0; for(i = 0; i < ALPHABET_SIZE; i++) { pNode->children[i] = NULL; } } return pNode; } // Initializes trie (root is dummy node) void initialize(trie_t *pTrie) { pTrie->root = getNode(); pTrie->count = 0; } // If not present, inserts key into trie // If the key is prefix of trie node, just marks leaf node void insert(trie_t *pTrie, char key[]) { int level; int length = strlen(key); int index; trie_node_t *pCrawl; pTrie->count++; pCrawl = pTrie->root; for( level = 0; level < length; level++ ) { index = CHAR_TO_INDEX(key[level]); if( pCrawl->children[index] ) { // Key current character already present // skip the node pCrawl = pCrawl->children[index]; } else { // Add new node pCrawl->children[index] = getNode(); pCrawl = pCrawl->children[index]; } } // mark last node as leaf pCrawl->value = pTrie->count; } // Returns non zero, if key presents in trie int search(trie_t *pTrie, char key[]) { int level; int length = strlen(key); int index; trie_node_t *pCrawl; pCrawl = pTrie->root; for( level = 0; level < length; level++ ) { index = CHAR_TO_INDEX(key[level]); if( !pCrawl->children[index] ) { return 0; } pCrawl = pCrawl->children[index]; } return (0 != pCrawl && pCrawl->value); } // Driver int main() { // Input keys (use only 'a' through 'z' and lower case) char keys[][8] = {"the", "a", "there", "answer", "any", "by", "bye", "their"}; trie_t trie; char output[][32] = {"Not present in trie", "Present in trie"}; initialize(&trie); // Construct trie for(int i = 0; i < ARRAY_SIZE(keys); i++) { insert(&trie, keys[i]); } // Search for different keys printf("%s --- %s\n", "the", output[search(&trie, "the")] ); printf("%s --- %s\n", "these", output[search(&trie, "these")] ); printf("%s --- %s\n", "their", output[search(&trie, "their")] ); printf("%s --- %s\n", "thaw", output[search(&trie, "thaw")] ); return 0; }