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 :

	class Solution {
	public:
	vector<vector<int> > pathSum(TreeNode *root, int sum) {
	vector<vector<int>> vec;
	vector<int> ivec;
	findSumPath (root, sum, vec, ivec);
	return vec;
	}
	public:
	void findSumPath (TreeNode *root, int sum, vector<vector<int>> &vec, vector<int> &ivec) {
	if(!root) return;
	ivec.push_back(root->val);
	if(root->left == NULL && root->right== NULL && sum == root->val)
	{
	vec.push_back(ivec);
	ivec.pop_back();
	return;
	}
	if (root->left) findSumPath(root->left, sum-root->val, vec, ivec);
	if (root->right) findSumPath(root->right, sum-root->val, vec, ivec);
	ivec.pop_back();
	}
	};

view raw PathSumII hosted with ❤ by GitHub

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 :

	class Solution {
	public:
	ListNode *partition(ListNode *head, int x) {
	if(head==NULL || head->next==NULL) return head;
	int n=0;
	ListNode *p = new ListNode(0);
	p->next=head;
	head = p;
	ListNode *last = p;
	while(last->next!=NULL) {last=last->next;n++;}
	while(n>0){
	if(p->next->val<x){
	p=p->next;
	n--;
	}
	else{
	last->next = new ListNode(p->next->val);
	last=last->next;
	p->next=p->next->next;
	n--;
	}
	}
	return head->next;
	}
	};

view raw PartitionList hosted with ❤ by GitHub

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 :

	class Solution {
	public:
	ListNode *deleteDuplicates(ListNode *head) {
	ListNode *p = head;
	if (p==NULL) return NULL;
	while(p->next!=NULL){
	if (p->val == p->next->val) p->next = p->next->next;
	else
	p=p->next;
	}
	return head;
	}
	};

view raw RemoveDuplicatesFromList hosted with ❤ by GitHub

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:

	class Solution {
	public:
	int maxProfit(vector<int> &prices) {
	int n= prices.size();
	int min =0;
	int greatDiff =0;
	for(int i=0; i<n;++i){
	if (prices[i]<prices[min]) min = i;
	if((prices[i]-prices[min])>greatDiff)
	greatDiff = prices[i]-prices[min];
	}
	return greatDiff;
	}
	};

view raw BestTImeToBuyandSellStock hosted with ❤ by GitHub

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 :

	class Solution {
	public:
	vector<vector<int> > permute(vector<int> &num) {
	vector<vector<int>> result;
	perm(num, 0, num.size()-1, result);
	return result;
	}
	void perm( vector<int> &num, int k, int n, vector<vector<int>> &result)
	{
	int i,t;
	if (k==n) result.push_back(num);
	else{
	for(i=k; i<=n;i++)
	{
	t=num[k]; num[k]=num[i]; num[i]=t;
	perm (num, k+1, n, result);
	t=num[k]; num[k]=num[i]; num[i]=t;
	}
	}
	}
	};

view raw permutaions.cpp hosted with ❤ by GitHub

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.  

	class Solution {
	public:
	vector<vector<int> > levelOrder(TreeNode *root) {
	vector<vector<int>> res;
	vector<int> temp;
	if(root==NULL) return res;
	int nodesInCurrentLevel = 1;
	int nodesInNextLevel =0;
	TreeNode *current;
	queue<TreeNode *> currentnode;
	currentnode.push(root);
	while(!currentnode.empty()){
	current = currentnode.front();
	currentnode.pop();
	nodesInCurrentLevel--;
	if(current){ temp.push_back(current->val);
	if(current->left) {currentnode.push(current->left); nodesInNextLevel++;}
	if(current->right){currentnode.push(current->right); nodesInNextLevel++;}}
	if(nodesInCurrentLevel==0){
	res.push_back(temp);
	nodesInCurrentLevel = nodesInNextLevel;
	nodesInNextLevel=0;
	temp.clear();
	}
	}
	return res;
	}
	};

view raw levelorder.cpp hosted with ❤ by GitHub

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