@nishanth Groups are defined by the count of each digit, not the length of the number. 123 has one 1, one 2, and one 3, thus it would not fit Group 3 in the example given by the OP.
Posts made by Ellest
RE: Subtree of Another Tree
@luckygirl - I think the author of this article may of taken string concatenation into account. I agree it should be O(m + n) for the serialization (preorder traversal) given we're optimizing the concatenation (i.e. StringBuilder in Java, string array then concatenation at end for Python, etc.)
Note that comparison can also be reduced to O(m) as we could use KMP string comparison to check if the serialization of t is a substring of the serialization of s
Python Recursive Delete Clean & Concise
def deleteNode(self, root, key): if not root: return if key == root.val: if not root.right: return root.left itr = root.right while itr.left: itr = itr.left root.val, itr.val = itr.val, root.val # swap value with next greatest root.right = self.deleteNode(root.right, key) # recursively delete elif key < root.val: root.left = self.deleteNode(root.left, key) else: root.right = self.deleteNode(root.right, key) return root
RE: Design a Data Structure that supports get(int idx), set(int idx, int val), and setAll(int val) all in constant time.
I don't think we even have to consider the garbage collector. The foreach block loops through each key. This alone will be a O(n) operation.
Concise Python DP O(mn) O(m) space with clear explanation
We can utilize DP as this problem has an optimal sub-structure. There are only two "direct" ways to reach a coordinate (r,c), from the left (r,c-1) and from above (r-1, c). This means that if we know the minimum HP needed to reach a certain coordinate (r,c), we can also deduce what minimum HP we need to start with for the direct left (r,c-1) and direct above coordinates (r-1, c). Using this notion, we can start a DP from the end coordinate (N-1, M-1) as there aren't any spaces left to traverse after we reach the ending coordinate, meaning the ending coordinate do not have any subproblems (i.e. if the end coordinate has a value of -5, we know we need at least 6 HP at either the direct left and direct above coordinates in order to reach the end coordinate).
With this in mind our DP equation is as follows:
dp[c] = min(dp[c+1], dp[c]) - dungeon[r][c]
We need to make sure that we at least have 1 HP at each coordinate. This can be enforced by setting the start of the DP (end coordinate) to be 1 if the value at the ending coordinate is positive.
We can optimize the dp solution further by using a rolling array as we only need subproblems from the level directly below to solve the problem at the current level.
def calculateMinimumHP(self, dungeon): M, N = len(dungeon), len(dungeon) row = [0 for _ in dungeon[-1]] row[-1] = max(1, -dungeon[-1][-1] + 1) for c in range(M-2, -1, -1): row[c] = max(row[c+1] - dungeon[-1][c], 1) for r in range(N-2, -1, -1): nxt, row[-1] = row[-1], max(row[-1] - dungeon[r][-1], 1) for c in range(M-2, -1, -1): nxt, row[c] = row[c], max(min(row[c+1], row[c]) - dungeon[r][c], 1) return row
Python O(n) Time O(1) Space. Extendable to the Longest Subsequence problem.
If you replace the while loop with a binary search, get rid of the if statement, and increase the size of vals to the length of the array, you have a O(nlogn) solution for the "Longest Subsequence" problem.
def increasingTriplet(self, nums): vals = [float('inf')] * 2 for n in nums: i = 1 while i >= 0 and vals[i] >= n: i -= 1 if i == 1: return True vals[i+1] = n return False
RE: Python Easy O(n) Solution
@borus I believe the OP's algorithm is similar to the "Longest Increasing Sub-sequence" problem. First, second, and third actually represent the lowest ending value of increasing sub-sequences of length one, two, and three respectively.
RE: most efficiently reverse the order of words in the sentence