# Tag: Leetcode

## 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 […]

## 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 […]

## Leetcode : The Skyline Problem Problem Statement Solution: It was actually difficult for me to come up with the brute force approach to solve the skyline problem. But that does not mean that getting to the efficient solution was easy. I struggled a lot in order to come to the efficient solution because there were so many scenarios that I was missing out on initially. Coming to think of it, the brute force approach would […]