A common type of problem is to find all possible sets of numbers that sum to a target. Here's an example of this:
Problem: Print out all positive integers a
, b
, and c
that sum to the number 10.
You might think to do a brute force solution like this:
Time Complexity O(n3). We have a triple for-loop.
Space Complexity O(1).
But you can actually do much better than brute-force. Whenever you see a problem like this, you can always write one of the variables using the other variables. Here, you can subtract a and b from both sides of the equation to solve for c, like this:
This equation tells you that the value of c
is completely determined by the values of a
and b
. This is because c = 10 - a - b
. This means we don't need to loop over it. Here's the above code, but where we removed the for-loop over c:
Time Complexity O(n2). We have a double for-loop.
Space Complexity O(1).
TreeNode.of
function can be used to create an entire binary tree using 1 line of code. The input is a BFS traversal of the tree including nulls, and the output is the root node of the tree.TreeNode.of([1, None, 2, None, 3])
ListNode.of
function lets you create an entire Linked List using 1 line of code. The input is an array, and the output is the head of the Linked List.ListNode.of([1, 2, 3])
ListNode.of([1, 2, 3], 1)
GraphNode.of
function lets you create an entire Graph using 1 line of code. The input is an Adjacency Matrix, and the output is the first node in the matrix.GraphNode.of([ ['A', 1, 2], ['B', 2], ['C', 0] ])
[['__init__', 15], ['add', 16], ['get']]
c = MyClass(15) c.add(16) c.get()