Find next greater number with same set of digits

Problem:
Given a number n, find the smallest number that has same set of digits as n and is greater than n. If x is the greatest possible number with its set of digits, then print “not possible”.

Solution:
I) Traverse the given number from rightmost digit, keep traversing till you find a digit which is smaller than the previously traversed digit. For example, if the input number is “534976″, we stop at 4 because 4 is smaller than next digit 9. If we do not find such a digit, then output is “Not Possible”.

II) Now search the right side of above found digit ‘d’ for the smallest digit greater than ‘d’. For “534976″, the right side of 4 contains “976″. The smallest digit greater than 4 is 6.

III) Swap the above found two digits, we get 536974 in above example.

IV) Now sort all digits from position next to ‘d’ to the end of number. The number that we get after sorting is the output. For above example, we sort digits in bold 536974. We get “536479” which is the next greater number for input 534976.

Optimizations:
1) We can use binary search in step II instead of linear search.
2) In step IV, instead of doing simple sort, we can apply some clever technique to do it in linear time. Hint: We know that all digits are linearly sorted in reverse order except one digit which was swapped.

Complexity:

time - O(n)
space - O(1)

Links and credits:
http://www.geeksforgeeks.org/find-next-greater-number-set-digits/

Reverse alternate levels of a binary tree

Problem:
Given a Binary Tree, reverse the alternate level nodes of the binary tree.

Given tree: 
               a
            /     \
           b       c
         /  \     /  \
        d    e    f    g
       / \  / \  / \  / \
       h  i j  k l  m  n  o 

Modified tree:
          a
            /     \
           c       b
         /  \     /  \
        d    e    f    g
       / \  / \  / \  / \
      o  n m  l k  j  i  h

Solution:

A simple solution is to do following steps.
1) Access nodes level by level.
2) If current level is odd, then store nodes of this level in an array.
3) Reverse the array and store elements back in tree.

A tricky solution is to do two inorder traversals. Following are steps to be followed.
1) Traverse the given tree in inorder fashion and store all odd level nodes in an auxiliary array. For the above example given tree, contents of array become {h, i, b, j, k, l, m, c, n, o}

2) Reverse the array. The array now becomes {o, n, c, m, l, k, j, b, i, h}

3) Traverse the tree again inorder fashion. While traversing the tree, one by one take elements from array and store elements from array to every odd level traversed node.
For the above example, we traverse ‘h’ first in above array and replace ‘h’ with ‘o’. Then we traverse ‘i’ and replace it with n.

Note that the solution works for complete binary trees only. Perhaps it could be modified to work with incomplete trees too, by storing "empty" elements in the array on step #1.

Complexity:

time - O(n)
space - O(n)

Links and credits:
http://www.geeksforgeeks.org/reverse-alternate-levels-binary-tree/

Maximum and minimum of an array using minimum number of comparisons

Problem:
Find maximum and minimum of an array using minimum number of comparisons.

Solution:
http://www.geeksforgeeks.org/maximum-and-minimum-in-an-array/

1. Linear: 1 + 2*(n - 2)
2. Divide and conqure: 1.5*n - 2 (if n is a power of 2, otherwise more comparisions are required)
3. Compare in pairs: also ~1.5*n.

Complexity:

time - O(n)
space - O(1) or O(log n) (for method #2)

Links and credits:
http://www.geeksforgeeks.org/maximum-and-minimum-in-an-array/

Jump game

Problem:
Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Determine if you are able to reach the last index.

For example:
A = [2,3,1,1,4], return true.

A = [3,2,1,0,4], return false.

Solution:

bool canJump(int A[], int n) {
    int reach = 1;
    for (int i = 0; i < reach && reach < n; ++i)
        reach = max(reach, A[i] + i + 1);
    return reach >= n;
}

Complexity:

time - O(n)
space - O(1)

Links and credits:
http://discuss.leetcode.com/questions/232/jump-game

Replace each element with its Next Larger Element on the right

Problem:
Given an Array, replace each element in the Array with its Next Element(To its RHS) which is Larger than it. If no such element exists, then no need to replace.
Ex:

i/p: {2,12,8,6,5,1,2,10,3,2}
o/p:{12,12,10,10,10,2,10,10,3,2}

Solution:

Naive solution is O(n^2) as it requires two nested loops.

A more optimal solution is to traverse the array from the right and put all elements in a BST, replacing each element in the array with its immediate in-order successor in the BST. This will take O(n log n) time to complete and require O(n) space.

The best solution also requires O(n) space but runs in O(n) time. We traverse the array from the left and keep pushing elements' indexes to a stack, ensuring that all the elements in the stack are always stored in decreasing order. Once the order is not decreasing, we pop the element from the stack (remember, it's an index) and replace the corresponding element in the array with an element currently being processed in the main loop:

void ReplaceNextLargest ( int * Arr, int N ) {
    stack<int> stk;
    stk.push(0);

    for( int idx = 1; idx < N; idx++ ) {
        while( !stk.empty() && (Arr[idx] > Arr[stk.top()]) ) {
            Arr[stk.top()] = Arr[idx];
            stk.pop();
        }
        stk.push(idx);
    }
}

Complexity:

time - O(n)
space - O(n)

Links and credits:
http://www.careercup.com/question?id=6311825561878528
http://www.geeksforgeeks.org/next-greater-element/

Find number of ways to go n steps with 1 or 2 steps

Problem:
Frog can jump 1 or 2 steps write the code to find out number of ways to go up to n steps.

Solution:

The number of ways to jump to n steps is the n-th Fibonacci number!

F[n] = F[n-1] + F[n-2]; 
F1 = 1; F2 = 2;

Example:

F[3] = F[2] + F[1]
1 1 1 part of F[2]
2 1 part of F[2]
1 2 part of F[1]

F[2]
1 1 
2

F[1]
1

Complexity:

time - O(n)
space - O(1) (for iterative approach)

Links and credits:
http://www.careercup.com/question?id=5950229446656000

Inorder traversal of binary tree w/o recursion

Problem:
Inorder traversal of binary tree w/ recursion

Solution:

/* Iterative method using stack */
Inordertraversal(struct btree *root)   
{
 while(1)
 {   
  while( root )
  {
   push(root);
   root = root->left;
  }
  if(Isstackempty(S))
   return;
  printf( S(top)->data);
  root = pop(S);
  root = root->right;
 }
}

Complexity:

time - O(n)
space - O(n)

Links and credits:
http://www.careercup.com/question?id=5198302274387968

Sort n numbers in range from 0 to n^2 – 1 in linear time

Problem:
Given an array of numbers of size n. It is also given that the array elements are in range from 0 to n2 – 1. Sort the given array in linear time.

Examples:
Since there are 5 elements, the elements can be from 0 to 24.
Input: arr[] = {0, 23, 14, 12, 9}
Output: arr[] = {0, 9, 12, 14, 23}

Since there are 3 elements, the elements can be from 0 to 8.
Input: arr[] = {7, 0, 2}
Output: arr[] = {0, 2, 7}

Solution:
The idea is to use Radix Sort. Following is standard Radix Sort algorithm.

Do following for each digit i where i varies from least significant digit to the most significant digit: Sort input array using counting sort (or any stable sort) according to the i’th digit.

Let there be d digits in input integers. Radix Sort takes O(d*(n+b)) time where b is the base for representing numbers, for example, for decimal system, b is 10. Since n2-1 is the maximum possible value, the value of d would be O(\log_b(n)). So overall time complexity is O((n+b)*\log_b(n)). Which looks more than the time complexity of comparison based sorting algorithms for a large k. The idea is to change base b. If we set b as n, the value of O(\log_b(n)) becomes O(1) and overall time complexity becomes O(n).

arr[] = {0, 10, 13, 12, 7}

Let us consider the elements in base 5. For example 13 in
base 5 is 23, and 7 in base 5 is 12.
arr[] = {00(0), 20(10), 23(13), 22(12), 12(7)}

After first iteration (Sorting according to the last digit in 
base 5),  we get.
arr[] = {00(0), 20(10), 12(7), 22(12), 23(13)}

After second iteration, we get
arr[] = {00(0), 12(7), 20(10), 22(12), 23(13)}

How to sort if range is from 1 to n2?
If range is from 1 to n n2, the above process can not be directly applied, it must be changed. Consider n = 100 and range from 1 to 10000. Since the base is 100, a digit must be from 0 to 99 and there should be 2 digits in the numbers. But the number 10000 has more than 2 digits. So to sort numbers in a range from 1 to n2, we can use following process.
1) Subtract all numbers by 1.
2) Since the range is now 0 to n2, do counting sort twice as done in the above implementation.
3) After the elements are sorted, add 1 to all numbers to obtain the original numbers.

How to sort if range is from 0 to n^3 -1?
Since there can be 3 digits in base n, we need to call counting sort 3 times.


PS. Note: the counting sort for the radix sort for base n requires O(n) memory. We could try to use a bit-set for sorting if all the numbers are unique.

Complexity:

time - O(n)
space - O(n) (for counting sort)

Links and credits:
http://www.geeksforgeeks.org/sort-n-numbers-range-0-n2-1-linear-time/

Circular right shift by n

Problem:
Given an integer array. Perform circular right shift by n.
Give the best solution.

Solution:

O(n)/O(1):

void reverse(int A[], int start, int end)
{
 while(start < end)
  swap(A[start++], A[end--]);
}

//shift A[0…sz-1] by n (n>0)
void shiftArray(int A[], int sz, int n)
{
 n = n%sz;
 reverse(A, 0, sz-1);
 reverse(A, 0, n-1);
 reverse(A, n, sz-1);
 return;
}

But the above solution performs too many swaps. There's an alternative O(n)/O(1) solution that swaps each element only once. We start with the first element at index 0 and put it to its final position (at index [n % length]). The former element at index [0 + n % length] will now be saved in a temporary variable. Now, on the next loop iteration we put the temporary element to its final position (at index [(n + n) % length]) and similarly store the element from that new position to a temporary variable. We continue the process until we put an element at index 0, after which the array is rotated. As an example, consider the following example with an array of 5 elements that needs to be shifted by 3:

1 2 3 4 5

Shift it by 3:

x 2 3 1 5 - 4
x 4 3 1 5 - 2
x 4 3 1 2 - 5
x 4 5 1 2 - 3
3 4 5 1 2

Each line above represents the state of the array on each iteration of the loop. A number after the '-' sign is the temporary storage used for an element currently being shifted. The 'x' represents a position that doesn't contain a valid data and needs to be filled last. So, the loop would look like this:

int i = 0;
int temp = array[0];
do {
   int k = i + n % length;
   int t = array[k];
   array[k] = temp;
   temp = t;
   i = (i + n) % length;
} while (i != 0);
// Finally, fill the index 0:
array[0] = temp;

Complexity:

time - O(n)
space - O(1)

Links and credits:
http://www.careercup.com/question?id=6282862240202752

Find elements with sum equal to the sum of their indexes

Problem:
Write a method which takes an array input and returns true if the sum of any two elements is equal to the sum of the corresponding indices. Like if for an array the sum of values at any two indices i and j is equal to the sum of i and j.

Solution:
Since we know we are looking for pairs where x+y = A[x] + A[y], by simple algebra, you can also look for x-A[x] = A[y]-y

public static ArrayList<ArrayList<Integer>> findSums(int[] A) {
  // Look for pairs where  x - A[x] == A[y] - y
  ArrayList<ArrayList<Integer>> soln = new ArrayList<ArrayList<Integer>>();
  HashMap<Integer,Integer> h = new HashMap<Integer,Integer>();
  
  for (int x = 0; x < A.length; x++) {
   h.put(x-A[x],x);
  }
  
  for (int y = 0; y < A.length; y++) {
   if (h.containsKey(A[y]-y)) {
    int x = h.get(A[y]-y);
    if (y != x) {
     ArrayList<Integer> pair= new ArrayList<Integer>();
     pair.add(x);
     pair.add(y);
     soln.add(pair);
    }
   }
  }
  
  return soln;
}

Complexity:

time - O(n)
space - O(n)

Links and credits:
http://www.careercup.com/question?id=5705699820568576

LCA or Lowest Common Ancestor of a Binary Tree

Problem:
Given a binary tree, find the lowest common ancestor of two given nodes in the tree.

E.g.:

        _______3______
       /              \
    ___5__          ___1__
   /      \        /      \
   6      _2       0       8
         /  \
         7   4

In this tree, an LCA for 6 and 4 is 5. For 5 and 4 it is 5,too. For 7 and 1 it is 3. And so on.

Solution:
A Bottom-up Approach:
We traverse from the bottom, and once we reach a node which matches one of the two nodes, we pass it up to its parent. The parent would then test its left and right subtree if each contain one of the two nodes. If yes, then the parent must be the LCA and we pass its parent up to the root. If not, we pass the lower node which contains either one of the two nodes (if the left or right subtree contains either p or q), or NULL (if both the left and right subtree does not contain either p or q) up.

Node *LCA(Node *root, Node *p, Node *q) {
  if (!root) return NULL;
  if (root == p || root == q) return root;
  Node *L = LCA(root->left, p, q);
  Node *R = LCA(root->right, p, q);
  if (L && R) return root;  // if p and q are on both sides
  return L ? L : R;  // either one of p,q is on one side OR p,q is not in L&R subtrees
}

Complexity:

time - O(n)
space - O(log n)

Links and credits:
http://leetcode.com/2011/07/lowest-common-ancestor-of-a-binary-tree-part-i.html

Search in a matrix sorted by rows and columns

Problem:
Search in a row wise and column wise sorted matrix

Solution:
Assuming both sorted in strictly increasing order:

M[row][column] < M[row+1][column] and M[row][column] < M[row][column+1]

Start from the top-right corner of the matrix. If the matrix element is larger than the target, move to the column on the left; if smaller, move to the row below.

Complexity if O(#rows + #columns)

public Position searchSortedMatrix(int x, int[][] M) {
 if (M.length==0 || M[0].length==0) return Position(-1,-1);
 int row = 0, column = M[0].length-1, curVal;
 while (row<M.length && column>=0) {
  curVal = M[row][column];
  if (curVal == x) return Position(row,column);
  if (curVal > x) column--;
  else row++;
 }
 return Position(-1,-1);
}

Note that binary search won't work because the element being searched can be located virtually anywhere, so we can't choose the "right" row or column beforehand.


There's also a divide and conqure solution exist:
1) Find the middle element.
2) If middle element is same as key return.
3) If middle element is lesser than key then
….3a) search submatrix on lower side of middle element
….3b) Search submatrix on right hand side.of middle element
4) If middle element is greater than key then
….4a) search vertical submatrix on left side of middle element
….4b) search submatrix on right hand side.

If given a n x n matrix, the time complexity of the divide and conqure solution is O(n^1.58) (follows from a recurrence: T(n) = 3T(n/2) + O(1), see geeksforgeeks link for details).

Complexity:

time - O(n)
space - O(1)

Links and credits:
http://www.careercup.com/question?id=6448780970819584
http://www.geeksforgeeks.org/divide-conquer-set-6-search-row-wise-column-wise-sorted-2d-array/

Find longest subarray with equal sum

Problem:
Given 2 binary arrays A and B i.e. containing only 0s and 1s each of size N.
Find indices i,j such that Sum of elements from i to j in both arrays is equal and j-i (i.e. the length of the set i,j) is the maximum possible value.

Solution:
This is same as finding the longest subarray with sum zero in the array C[i] = A[i] - B[i].

Prefix sums + hashtable should give it.

Complexity:

time - O(n)
space - O(n)

Links and credits:
http://www.careercup.com/question?id=25036663

Find a subarray divisible by 7

Problem:
WAP a program to find a contineous subset whose sum is divisible by 7. We are given a array of number (negative+positive).
calculate the complexity of your algorithm

Solution:
So, we want to find sub-set [i, j], such that

a[i]+a[i+1]+ ... a[j] ) % k = 0

with k == 7, that really does not matter
________________________________________________
Let's calculate the sum of elements from 1 to i by mod k for each i:

s[i] = (a[1] + a[2] + ... + a[i]) % k

And we can note that, if there is such [i, j] that we are looking for, then:

s[j]-s[i] == (a[1]+...+a[j]) - (a[1]+...+a[i]) == (a[i]+...+a[j]) == 0

So, for each s[i] == s[j], sum of sub-set [i, j] is divisible by k.

Complexity:

time - O(n)
space - O(n)

Links and credits:
http://www.careercup.com/question?id=5812734516002816

Reverse Nodes in k-Group

Problem:
Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.

If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.

You may not alter the values in the nodes, only nodes itself may be changed.

Only constant memory is allowed.

For example,
Given this linked list: 1->2->3->4->5

For k = 2, you should return: 2->1->4->3->5

For k = 3, you should return: 3->2->1->4->5

Solution:
It's easy to reverse the whole linked list (i.e. consider k === list length). Now, the definition of the "whole list" is only a matter of how we define its head and tail. We should just traverse the original list and treat each k-group as a separate list and reverse it one by one until we reach a group of size less than k.

ListNode *reverseKGroup(ListNode *head, int k) {
    if (!head || k <= 1) return head;

    ListNode dummy(0);
    dummy.next = head;
    ListNode *pre = &dummy;

    int i = 0;
    while (head) {
        i++;
        if (i % k == 0) {
            pre = reverse(pre, head->next);                
            head = pre->next;
        } else {
            head = head->next;   
        }
    }

    return dummy.next;
}

ListNode *reverse(ListNode *pre, ListNode *next) {
    ListNode *last = pre->next;
    ListNode *cur = last->next;
    while (cur != next) {
        last->next = cur->next;
        cur->next = pre->next;
        pre->next = cur;

        cur = last->next;
    }
    return last;
}

Complexity:

time - O(n)
space - O(1)

Links and credits:
http://discuss.leetcode.com/questions/206/reverse-nodes-in-k-group

Binary Tree Zigzag Level Order Traversal

Problem:
Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between).

Solution:
This problem can be solved easily using two stacks (one called currentLevel and the other one called nextLevel). You would also need a variable to keep track of the current level's order (whether it is left->right or right->left).

You pop from stack currentLevel and print the node's value. Whenever the current level's order is from left->right, you push the node's left child, then its right child to stack nextLevel. Remember a Stack is a Last In First OUT (LIFO) structure, so the next time when nodes are popped off nextLevel, it will be in the reverse order.

On the other hand, when the current level's order is from right->left, you would push the node's right child first, then its left child. Finally, don't forget to swap those two stacks at the end of each level (ie, when currentLevel is empty).

void printLevelOrderZigZag(BinaryTree *root) {
    stack<BinaryTree*> currentLevel, nextLevel;
    bool leftToRight = true;
    currentLevel.push(root);
    while (!currentLevel.empty()) {
        BinaryTree *currNode = currentLevel.top();
        currentLevel.pop();
        if (currNode) {
            cout << currNode->data << " ";
            if (leftToRight) {
                nextLevel.push(currNode->left);
                nextLevel.push(currNode->right);
            } else {
                nextLevel.push(currNode->right);
                nextLevel.push(currNode->left);
            }
        }
        if (currentLevel.empty()) {
            cout << endl;
            leftToRight = !leftToRight;
            swap(currentLevel, nextLevel);
        }
    }
}

Complexity:

time - O(n)
space - O(n)

Links and credits:
http://discuss.leetcode.com/questions/52/binary-tree-zigzag-level-order-traversal

Print Left View of a Binary Tree

Problem:
Given a Binary Tree, print left view of it. Left view of a Binary Tree is set of nodes visible when tree is visited from left side. Left view of following tree is 12, 10, 25.

          12
       /     \
     10       30
            /    \
          25      40

Solution:
The left view contains all nodes that are first nodes in their levels. A simple solution is to do level order traversal and print the first node in every level.

The problem can also be solved using simple recursive traversal. We can keep track of level of a node by passing a parameter to all recursive calls. The idea is to keep track of maximum level also. Whenever we see a node whose level is more than maximum level so far, we print the node because this is the first node in its level (Note that we traverse the left subtree before right subtree).

Note: the same procedure can be used to get the "right view" of a tree if we first traverse the right sub-tree in the recursive algorithm.

// Recursive function to print left view of a binary tree.
void leftViewUtil(struct node *root, int level, int *max_level)
{
    // Base Case
    if (root==NULL)  return;
 
    // If this is the first node of its level
    if (*max_level < level)
    {
        printf("%d\t", root->data);
        *max_level = level;
    }
 
    // Recur for left and right subtrees
    leftViewUtil(root->left, level+1, max_level);
    leftViewUtil(root->right, level+1, max_level);
}
 
// A wrapper over leftViewUtil()
void leftView(struct node *root)
{
    int max_level = 0;
    leftViewUtil(root, 1, &max_level);
}

Complexity:

time - O(n)
space - O(n)

Links and credits:
http://www.geeksforgeeks.org/print-left-view-binary-tree/

Find the equilibrium position of an array

Problem:
write a code to find the equilibrium position of the array.

given an array: 3,-3,8,6,-1,-5

equilibrium position should be 2(element 8) sum of lower index(3+-3)=sum of higher index(6+(-1)+(-5))

Solution:
For any index i, if we know the sum of items 0..i, we can find the sum of items i+1..n-1 by subtracting it from the sum of all elements. So:
1. Find the total sum of the array
2. For each element in the array
2.a. keep contSum, which is the sum up to the point in the array
2.b. if the (sum - A[i] - contSum) == contSum, return index (This is the point where the leftSum and the rightSum equals)
3. Return -1 if not found

public static int equilibriumIndex(int[] A) {
 int sum = 0;
 int i = 0;
 for (i = 0; i < A.length; i++) 
  sum += A[i];
  
 int contSum = 0;
 for (i = 0; i < A.length; i++) {
  if ( (sum - A[i] - contSum) == contSum) return i;
   
  contSum += A[i];
 }
  
 return -1; // not found
}

Complexity:

time - O(n)
space - O(1)

Links and credits:
http://www.careercup.com/question?id=23088665

Find a missing number

Problem:
Given you an array of 100 Elements with one number missing, how will you find the missing number?

Ex.: Array 1 to 100 with 55 missing.

Solution:
Just do sum of all the numbers from 1 to 100 : (n * (n+1))/2 and find sum of all the elements from actual array. Just take the difference and you will get missing number.
If numbers start with n > 1, then normalize them by subtracting n-1.

Complexity:

time - O(n)
space - O(1)

Links and credits:
http://www.careercup.com/question?id=23092662
See also: Find two missing numbers

Find tree height

Problem:
A tree, (NOT NECESSARILY BINARY), has nodes numbered 0 to N-1. An array has indices ranging from 0 to N-1. The indices denote the node ids and values denote the ids of parents. A value of -1 at some index k denotes that node with id k is the root. For ex:

3 3 3 -1 2
0 1 2 3 4

In the above, nodes with ids 0, 1 & 2 have 3 as parent. 3 is the root as its parent = -1 and 2 is the parent of node id 4.

Given such an array, find the height of the tree.

Solution:
A straightforward approach is to find the root, then find all its children, etc. (i.e. perform a BFS), and find out the maximum depth. This is a O(n^2) solution, although it requires only O(1) memory.

Using dynamic programming we can do this in O(n) time using O(n) memory:

public int countDepth(int[] tree) {
    int[] height = new int[tree.length];
    for (int i = 0; i < tree.length; i++)
        height[i] = -1;
    int maxHeight = -1;
    for (int i = 0; i < tree.length; i++) {
        if (height[i] == -1)
            maxHeight = max(maxHeight, findHeight(i, height, tree));
    }
    return maxElement(height);
}

private int findHeight(int i, int[] height, int[] tree) {
    if (height[i] != -1)
        return height[i];
    if (tree[i] == -1) {
        height[i] = 0;
    else
        height[i] = 1 + findHeight(tree[i], height, tree);
    return height[i];
}

Complexity:

time - O(n)
space - O(n)

Links and credits:
http://www.careercup.com/question?id=22809662