Path Sum II

Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.

For example:

Given the below binary tree and sum = 22,

              5
             / \
            4   8
           /   / \
          11  13  4
         /  \    / \
        7    2  5   1

return

[
   [5,4,11,2],
   [5,8,4,5]
]





Solution :

The idea is to use DFS. If in a path from root to a leaf the sum is found, the path

is entered into a result vector. If not, we backtrack and look for other paths.



Code :



Do comment and share!

Partition List

Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.
You should preserve the original relative order of the nodes in each of the two partitions.
For example,
Given 1->4->3->2->5->2 and x = 3,
return 1->2->2->4->3->5.

Solution :
The list can be traveled once to get the count of nodes and place a pointer at the last node.
In the next step, the  list is traveled again from head, and each node having value greater than x is placed at the end of the list.

Code :


Please comment to suggest a better method.

Remove Duplicates from Sorted List

Given a sorted linked list, delete all duplicates such that each element appear only once.
For example,
Given 1->1->2, return 1->2.
Given 1->1->2->3->3, return 1->2->3.

Solution :
Delete intermediate nodes that are same as the previous node. This works because the list is already sorted.

Code :

Best Time to Buy and Sell Stock

Say you have an array for which the i^th element is the price of a given stock on day i.
If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Solution :
The only thing to keep in my mind is that you cannot sell a stock before buying it.
We need to find max(Aj - Ai) where i
Code:

Permutations

Given a collection of numbers, return all possible permutations.
For example,
[1,2,3] have the following permutations:
[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], and [3,2,1].


Solution :
This is done recursively by making permutations resulting from swapping of two elements. The below diagram can make it clear.

We start with k=0 and swap the element at ith index with element at kth index.

At the first level for k = 0, we swap num[k] with num[i] where i varies from k to number of elements in the array. We do this at all levels where value of k increases till it is equal to the number of elements in the array.

Here is the program for it :

Please comment to add something.

Binary Tree Level Order Traversal

Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).
For example:
Given binary tree {3,9,20,#,#,15,7},

    3
   / \
  9  20
    /  \
   15   7

return its level order traversal as:

[
  [3],
  [9,20],
  [15,7]
]

Solution:

This is solved using BFS. One way to print in levels is to keep 

2 queues.Current queue and a nextlevel queue. nextlevel queue 

has left and right children of the node popped from current 

queue.Once the current queue is empty we swap current queue 

with nextlevel queue.Another solution is to use only 1 queue and

keep track of level using variables. nodesInCurrentLevel & 

nodesInNextLevel.

Here is the source code.  

Do comment if you would like to add something to it.

Next Permutation

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.
If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).
The replacement must be in-place, do not allocate extra memory.
Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

Solution :

We first find the digit starting from unit's place that is less than the preceding digit. In an Array A start with i = n-2. compare A[n-2] with A[n-1] and keep decrementing i till we find A[i]
For eg: in 1,3,2 we get i=0;
In another example 1,2,4,3,1,1 we get i =1. Hence the value 0 to i-1 need not be disturbed. We now need to find the next permutation of number starting from i.
We now need to find the next digit which is the least digit greater than A[i].
For that we move from the end of array and stop at k=3 (A[k]=3). We now swap A[i] and A[k]. So the array now is 1,3,4,2,1,1. Now we reverse the array starting from i+1. We now get 1,3,1,1,2,4 which is the next permutation.

Code: 

Minimum Path Sum

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.
Note: You can only move either down or right at any point in time.

Solution : 

This can be done by in place dynamic programming. The idea is to replace matrix[i][j] values with the minimum value that can be achieved (among two paths) to reach matrix[i][j].
We can reach matrix[i][j] through one of 
matrix[i-1][j] or
matrix[i][j-1]
We record the minimum of these two at matrix[i][j].

Code:
class Solution {
public:
    int minPathSum(vector > &grid) {
    int i,j;
     for(i=0;i
        for(j=0;j
        {
           if(!(i==0 && j==0))
            {
                if(i==0 && j>0)
                  grid[i][j] += grid[i][j-1];
              else  if(i> && j==0)
                 grid[i][j]  += grid[i-1][j];
               else
                 grid[i][j] += min(grid[i][j-1], grid[i-1][j]); 
             }
         }
         return grid[i][j];
}
};