Category: PROBLEM SOLVING

Leetcode : Longest Duplicate Substring Problem Statement Solution: The brute force approach for this problem would be to scan for all substrings of length L for each possible value of L from 1 to N-1. Store the substrings in a set() and whenever we encounter a substring which is already present in the set then it is a duplicated substring of length L. Repeat this for all L until we find some L' for which […]

Leetcode : Redundant Connections 2 Problem Statement Solution: The brute force approach for this problem would be to do a DFS or BFS starting from each node after removing edge Ei in the input 'edges' array. At each position i from right to left, after removing Ei, do BFS from each node in the graph. If for BFS from any node, we cover all the nodes from 1 to N without any cycle, then return […]

Leetcode : Course Schedule 3 Problem Statement Solution: An obvious brute force approach is to enumerate all possible scenarios i.e. all possible valid sequence of courses and take the answer as the sequence with the maximum length. For an input size of N and a sequence of length M, the number of possible sequences is exponential in N i.e. NM. Obviously this is a bad choice, but can we think of a better solution. We […]

Leetcode : Design O(1) data structure for insertion, deletion and get random Problem Statement Solution: It is pretty obvious that O(1) insertion and removal can be designed using a Set or Hash-Map or a Doubly Linked List. When duplicates are prohibited, using a Set() data structure is very convenient, but when duplicates are allowed we cannot use Set. Instead we can use Hash-Map. The key of the Hash-Map are the unique integers while the values are the count of each integer. While […]

Leetcode : Cutoff Trees for Golf Problem Statement Solution : There is no trick that reduces the worst case run-time complexity for this problem. The brute-force approach is to first sort the tree heights from lowest to highest (ignoring the tree heights with height < 1) and then for each successive pair (A, B) of sorted tree heights, do a BFS from A to B and compute the minimum length path required to travel from A […]

Leetcode : Self Crossing Problem Statement Solution: The brute force approach would be to store the starting and the ending co-ordinates for each line segment in an array A and then for the current segment, check if it intersects or "touches" any one of the previous line segments present in the array A. The run-time and space complexity of this approach is O(N2) where N is the number of line segments. Can we do […]

Leetcode : Number of digit one Problem Statement Solution: The brute force approach would be iterate through all numbers from 0 to N and then for each number count the number of 1's and add them up. For a number N, the number of digits it contains is O(log10N). Thus the brute force approach has a time complexity of O(N*log10N). Can we do better than this ? The proposed solution achieves a O(log10N) run-time complexity. The […]

Fast Nearest Neighbour Search - KD Trees In a few of my earlier posts "designing Q&A retrieval system" and "designing e-commerce system for similar products using deep learning", one of the primary goals was to retrieve the most similar answers (responses) and the most similar e-commerce products respectively in a fast and scalable way. The later post was pretty much generic i.e. find dense representations for each item (questions, product images etc.) using un-supervised and supervised learning […]

Leetcode : Remove Duplicate Letters Problem Statement Solution: The problem looks to be easy on the outside but gets 'tricky' when we have to find the smallest possible string (alphabetically) with all unique letters. Removing duplicates is a very common problem that we usually encounter in our day to day software engineering. But in most use-cases it is sufficient to remove any one of the duplicates (first, last or randomly picked). Let's analyze the brute […]

Leetcode : Minimum Cost To Merge Stones Problem Statement Solution: It might be 'tempting' to think that the problem can be solved using a greedy approach, i.e. merge the K consecutive stones with the minimum cost in each step. But the greedy approach is not optimal, for e.g. if the stones array is [6,4,4,6] and K=2, then the greedy approach would result in a minimum cost of 42 whereas the optimal cost is 40. The greedy approach […]