Posts

Prefix Count: Hashtable

-
Image
Usually there are two approaches to deal with prefixes (or suffixes) in strings: either using a Trie, or a Hashtable. The former saves space while the latter consumes more but it is an easier implementation. Both have the relative save time complexity. For this problem below, given the small constraints, I decided to go with a Hashtable. No caveats, just follow the instructions given in the problem description. Cheers, ACC. Number of Prefix Connected Groups - LeetCode You are given an array of strings  words  and an integer  k . Two words  a  and  b  at  distinct indices  are  prefix -connected  if  a[0..k-1] == b[0..k-1] . A  connected group  is a set of words such that each pair of words is prefix-connected. Return the  number of connected groups  that contain  at least  two words, formed from the given words. Note: Words with length less than  k  cannot join any group and are ignored. ...
Post a Comment
Read more

Non-Recursive Tree Navigation

-
Image
In this problem you need to find all elements at a given level in a BST. I realized that unfortunately my solution doesn't take into account the BST property, hence in order to make it slightly faster (as a compromise), I decided to navigate the tree using a Stack. Runs in NLogN which still makes the cut. Code is down below, cheers, ACC. Median of a Binary Search Tree Level - LeetCode You are given the  root  of a  Binary Search Tree (BST)  and an integer  level . The root node is at level 0. Each level represents the distance from the root. Return the  median value  of all node values present at the given  level . If the level does not exist or contains no nodes, return -1. The  median  is defined as the middle element after sorting the values at that level in  non-decreasing  order. If the number of values at that level is even, return the  upper  median (the larger of the two middle elements after sorting).   ...
Post a Comment
Read more