# Tag: Dynamic Programming

## 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 : 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 : Non-negative Integers without Consecutive Ones

Problem Statement Solution: The brute force approach is to scan all the integers less than equals to N, compute their binary representation and check if the binary representation has consecutive ones or not. The run-time complexity of this approach is O(N*logN) because scanning all the integers less than N is O(N) and scanning the binary representation for each integer is O(logN), because binary representation of an integer M is of […]

## Leetcode : Longest Valid Parentheses

Problem Statement Solution: Most of us must have encountered a similar problem of finding the maximum number of valid parentheses pairs, which is pretty straightforward and quite commonly asked in many programming interviews. This is one variant where we need to find the longest sub-string which is a valid parentheses. The sub-string may contain any number of parenthesis pairs. One naive approach is to check for all pair of indices […]

## Leetcode : Count The Repetitions

Problem Statement Solution: One naive approach is to estimate the value of M from the fact that the maximum value of M possible is: Q=(n1*len(s1))/(n2*len(s2)) Let s(x) denote the string s repeated 'x' times. Using binary search between 0 to Q, check if the string s2(n2*m) is present in the string s1(n1) for some m. If s2(n2*m) is present in s1(n1), then search to the right half of m else to the left […]

## LeetCode: Three Equal Parts

Problem Statement Solution: The problem can be approached in multiple different ways. One trivial approach is to find the decimal representation for all binary sequences [i, j], where j >= i. Once we find the decimal representations for all [i, j], we can then find the indices i' and j' such that the decimal representation [0, i'], [i'+1, j'-1] and [j', N-1] are equal where N is the length of […]

## LeetCode: Minimum Refuel Stops

Problem Statement Solution: At first, this looks like a classic graph traversal problem. For example, I might be tempted to use BFS approach to find the minimum number of steps to reach the target. But one important distinction this problem has from a standard BFS is that in a standard BFS problem, the car can either directly reach a station Y from station X or they cannot depending whether there […]

## LeetCode : Unique Letters

Problem Statement Solution : Let's try to build a 'bad' solution first. By 'bad', I mean the approach may not be the most optimal but will return correct results every time. One such approach is to list down all possible substrings and count the unique letters in each of them and then take their sum. This approach is perfectly reasonable approach but why it is not optimal ?

## LeetCode : Maximal Rectangle

Problem Statement Solution : A simple brute force approach would require for each pair of points in the matrix, whether the points form the top left and bottom right corner of a rectangle (all 1's) and compute its area. Since there are O(N2) points, thus there are O(N4) pairs of points. Checking whether there is a rectangle between them and computing its area takes O(N2) comparisons. Thus the total run-time is O(N6), […]

## LeetCode : Dungeon Game

Problem Statement Solution : This problem is probably towards high medium difficulty level but below the hard level of problems. At one glance, one can conclude that we can solve this problem using the dynamic programming technique and it is correct. The only difficulty is in identifying what value to memoize at each step during the King's journey towards the Princess. So this is how it works. The initial health […]